Nombre premier et division Euclidienne (question)

[Rouvire]

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.

[zygomatique]

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 ....

[Rouvire]

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)

[nodjim]

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.

[zygomatique]

oui tout à fait ...

essaie aussi avec 13 par exemple ....

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

[ffpower]

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

[zygomatique]

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

d'où vient le reste 16 ?

[Rouvire]

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

[zygomatique]

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 ....

[bolza]

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

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

[zygomatique]

ha bon ?

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

:hum:

[Rouvire]

@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)?

[bolza]

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

[zygomatique]

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 ....