Nombre premier et division Euclidienne (question)

par **Rouvire** » 30 Juil 2015, 18:45

Bonjour,

Si on prend un nombre premier p, alors il existera toujours une base, dans laquelle on pourra exprimer p, telle que la division euclidienne 1:p donnera des boucles de p-1 restes différents.

Par exemple en base 10 si on fait la division de 1 par 7 on obtient les restes 1, 3, 2, 6, 4, 5, 1, 3 ... on a la boucle des 6 restes différents (1, 3, 2, 6, 4, 5) qui se répète indéfiniment.
Pour 5 si on l'exprime en base 2 on a 1:101 qui donne les restes 1, 10, 100, 11, 1, 10, ...

Et-ce-que c'est caractéristique des nombres premiers et est-ce qu'il y a une démonstration?

Merci.

par **zygomatique** » 30 Juil 2015, 20:24

salut

vu qu'un rationnel a une écriture décimale périodique à partir d'un certain rang ça reste vrai dans toute base .... et pour tout quotient 1/q que q soit premier ou non ...

excepté le cas où q est un produit de facteur 2 et 5 en base 10 .... où si q = 98 en base 14 ... où q = 12 en base 6 ....

par **Rouvire** » 30 Juil 2015, 23:35

Bonjour,

J'ai du mal m'exprimer. Si on reprend l'exemple avec 7 en base 10

1 : 7 ==> 0 x 7 reste 1
10 : 7 ==> 1 x 7 reste 3
30 : 7 ==> 4 x 7 reste 2
20 : 7 ==> 2 x 7 reste 6
60 : 7 ==> 8 x 7 reste 4
40 : 7 ==> 5 x 7 reste 5
50 : 7 ==> 7 x 7 reste 1

On obtient bien 6 restes différents (et 6 est égal à 7-1) avant de retomber sur 1.

Par contre si on prend un nombre N qui n'est pas premier avec les divisions euclidiennes successives comme ci-dessus on n'arrivera jamais à N-1 restes différents.

Par exemple si je prends 21 (en base 10) j'obtiens les restes 1, 10, 16, 13, 4, 19 avant de retomber sur 1. J'en n'obtiens que 6 (et pas 20)

par **nodjim** » 31 Juil 2015, 07:40

Attention, pour un nombre premier p, ce n'est pas une règle d'avoir les p-1 restes. Exemple p=11, 1/11 n'a comme reste que 1 et 10. En revanche, le nombre de restes d'une fraction est un diviseur de p-1.
Pour un nombre composé, la longueur de la séquence est un diviseur de phi(n), la fonction indicatrice d'Euler.

par **zygomatique** » 31 Juil 2015, 12:57

oui tout à fait ...

essaie aussi avec 13 par exemple ....

la longueur de la période est un diviseur de p - 1 ....

par **ffpower** » 31 Juil 2015, 13:19

Nodjim: ce qu'il conjecture, c'est qu'il existe une base b ou on obtient les p-1 restes, mais b peut être différent de 10.

Et effectivement: la suite considérée est la suite des restes de b^k modulo p. On veut donc montrer qu'il existe b tel que la suite 1,b,...,b^(p-1) donne les p-1 restes possibles. Ce qui est juste une reformulation du résultat classique: le groupe

est cyclique

par **zygomatique** » 31 Juil 2015, 13:37

si je prends 21 (en base 10) j'obtiens les restes 1, 10, 16, 13, 4, 19 avant

d'où vient le reste 16 ?

par **Rouvire** » 31 Juil 2015, 18:10

zygomatique a écrit:d'où vient le reste 16 ?

Bonjour,

Si je prends 21 (en base 10) j'obtiens les restes 1, 10, 16, 13, 4, 19 avant de retomber sur 1.

1 : 21 ==> 0 x 21 reste 1
10 : 21 ==> 0 x 21 reste 10
100 : 21 ==> 4 x 21 reste 16 ==> (4 x 21) + 16 = 100
160 : 21 ==> 7 x 21 reste 13
130 : 21 ==> 6 x 21 reste 4
40 : 21 ==> 1 x 21 reste 19
190 : 21 ==> 9 x 21 reste 1

Est-ce-que le fait que le groupe (Z/pZ)x avec p premier soit cyclique est suffisant pour dire que ce groupe à p-1 éléments?

Est-ce-que le "x", la loi de composition qu'on utilise dans ce groupe, c'est la multiplication modulo p?

Merci

par **zygomatique** » 31 Juil 2015, 20:45

c'est vraiment pas clair !!!

un coup c'est

J'ai du mal m'exprimer. Si on reprend l'exemple avec 7 en base 10

1 : 7 ==> 0 x 7 reste 1
10 : 7 ==> 1 x 7 reste 3
30 : 7 ==> 4 x 7 reste 2
20 : 7 ==> 2 x 7 reste 6
60 : 7 ==> 8 x 7 reste 4
40 : 7 ==> 5 x 7 reste 5
50 : 7 ==> 7 x 7 reste 1

un coup c'est

Si je prends 21 (en base 10) j'obtiens les restes 1, 10, 16, 13, 4, 19 avant de retomber sur 1.

1 : 21 ==> 0 x 21 reste 1
10 : 21 ==> 0 x 21 reste 10
100 : 21 ==> 4 x 21 reste 16 ==> (4 x 21) + 16 = 100
160 : 21 ==> 7 x 21 reste 13
130 : 21 ==> 6 x 21 reste 4
40 : 21 ==> 1 x 21 reste 19
190 : 21 ==> 9 x 21 reste 1

c'est donc du grand n'importe quoi ....

par **bolza** » 31 Juil 2015, 22:04

zygomatique a écrit: c'est donc du grand n'importe quoi ....

? :hum:? Pourtant il a bien utilisé le même procédé algorithmique dans les deux cas.

par **zygomatique** » 31 Juil 2015, 22:08

ha bon ?

pour le premier je lis 1 10 30 20 ...
pour le deuxième je lis 1 10 100 160 ...

:hum:

par **Rouvire** » 31 Juil 2015, 22:26

@zygomatique

J'essayais de répondre à ta question "d'où vient le reste 16 ?". Ben 16 c'est le troisième reste de la division euclidienne de 1 par 21.

Maintenant je dis que quand on fait la division euclidienne de 1 par 7 on obtient 6 restes différents ce qui (d'après moi) prouve que 7 est premier car 6 = 7-1. Et quand on fait la division de 1 par 21 on obtient aussi 6 restes différents ce qui ne prouve rien sur la primalité de 21 (quoique comme 6 ne divise pas 20 j'en sais rien puisque d'après les autres échanges il semble que le nombre de restes différents pour p premier doit diviser p-1).

Ensuite la question est: étant donné un nombre premier p est-ce qu'on peut toujours trouver une base b dans laquelle la division euclidienne de 1 par p donnera p-1 restes différents (à mon avis oui)?

par **bolza** » 01 Aoû 2015, 00:03

zygomatique a écrit:ha bon ?

pour le premier je lis 1 10 30 20 ...
pour le deuxième je lis 1 10 100 160 ...

:hum:

Oui, à chaque fois, c'est le reste précédent multiplier par 10 (la base)

édit: en fait il considère la suite des b^k (mod p) donc en gros sa question est si p est premier, existe-il un générateur de (Z/pZ, *) ?

et tout est expliqué ici

par **zygomatique** » 01 Aoû 2015, 13:15

ha ok !!!

merci beaucoup ... car j'avais pas compris ....

et donc j'avais raison d'écrire ce que j'ai écrit dans mon premier post !!! justifié par le post de nodjim ....

Nombre premier et division Euclidienne (question)

Nombre premier et division Euclidienne (question)

Qui est en ligne