Nombres premiers

all1 · July 2006

Bonjour a tous

Comment prouver l'affirmation suivante?
Soient $a$, $c$ et $m$ des entiers naturels. on definit $x_0$ un autre entier compris entre $0$ et $m-1$ et la suite $x_n$ telle que $x_{n+1}= (a.x_n + c)[m]$. Alors la suite $x_n$ a une periode egale a $m$ ssi les entiers $c$ et $m$ sont premiers entre eux.
J'ai completement oublie quelles sont les methodes pour resoudre ce genre de probleme.
Merci,

All

jean0 · July 2006

Arme suprême: Bezout. Deux nombres x et y sont premiers si et seulement si il existe a, b entiers tels que ax + by = 1.

all1 · July 2006

Bonjour Jean,

Effectivement deux nombre x et y sont premiers ENTRE EUX ssi il existe ...
Bon, supposons c et m premiers entre eux. Alors, il existe x et y tels que
$xc + ym = 1$ donc $xc \equiv 1[m]$. Mais je ne vois pas (plus) comment la suite des restes va etre de periode $m$, ni comment je vais resoudre mon probleme. Je regarde encore un peu.

All

egoroff · July 2006

Tu peux aussi regarder du côté des générateurs de $\Z / n\Z$.

all1 · July 2006

Bonjour Egoroff,

Ca commence a revenir un peu. Les generateurs de $\mathbb{Z}/m\mathbb{Z}$ sont les $p$ compris entre $0$ et $m-1$ tels que $p$ est premier avec $m$.

Pour ma demo, on voit d'abord que la suite des restes ne peut pas etre de periode superieure a $m$ sinon, on aurait quelque part un reste lui-meme superieur a $m$. Essayons de prouver par l'absurde que la periode est exactement $m$.
supposons, il existe $k < m$ tel que $r_k = r_1$.
... bon je ne vois pas encore comment je vais caser l'hypothese que $c$ et $m$ sont premiers entre eux, ni comment je vais utiliser Bezout ou les generateurs de $\mathbb{Z}/m\mathbb{Z}$ pour prouver mon enonce... je continue...

All

SadYear · July 2006

Voici un début de réflexion (aux erreurs de calculs près)...

Le cas $a = 1 [m]$ est clair.
Si $a \neq 1 [m]$ alors la relation (suite arithmético-géométrique) :
$(*)$ : $(1 - a)x_{n+m} = a^m((1 - a)x_{n} - c) + c$
permet de conclure dans le cas où $m$ est premier. En effet, si $m$ est premier alors $a^m = a [m]$ et $(1-a)$ est inversible modulo $m$, et il suffit alors de regarder l'égalité $(*)$ modulo $m$ pour obtenir $x_{n+m} = x_{n} [m]$. (Le fait que $m$ et $c$ soient premiers entre eux ne joue ici aucun rôle).

Je me demande si on ne pourrait pas encore utiliser $(*)$ de manière astucieuse pour le cas où $m$ n'est pas premier. En fait si $r$ est une période ($x_0 = x_r [m]$) alors nécessairement $(*)$ entraine que :
$(**)$ : $(a^r - 1) ((1 - a)x_0 - c) = 0 [m]$
Mais je ne vois pas comment tirer parti de $(**)$ pour le moment. Peut-être n'est-ce tout simplement pas la bonne piste...

SadYear

17'5 n1c3 70 83 1mp0r74n7, 8u7 17'5 m0r3 1mp0r74n7 70 83 n1c3.

Jérémypaslogué · July 2006

Bonjour,

à première vue, ça ressemble à de la génération de bits pseudo-aléatoires (en fait non), c'est pas une suite de Lehmer?

Si tel est le cas, la démo n'est pas si courte...

Pour l'instant, je suis pas chez moi, mais éventuellement (et si c'est du Lehmer) je pourrais peut-être t'aider!

A +

Jérémy

all1 · July 2006

Oui, c'est bien une suite de nombre pseudo-aléatoire. En revanche je ne sais pas si ça s'appelle suite de Lehmer ou non.
Bonne nuit,

All

SadYear · July 2006

En fait après une bonne nuit de sommeil et quelques tests bien choisis je me suis aperçu que l'énoncé initial est faux :
 
 <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img1.png" ALT="$ (1)$"> <IMG WIDTH="41" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img2.png" ALT="$ a = 1$">, <IMG WIDTH="39" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img3.png" ALT="$ c = 2$">, <IMG WIDTH="46" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img4.png" ALT="$ m = 3$"> : <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img5.png" ALT="$ x_0 = 0$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img6.png" ALT="$ x_1 = 2$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img7.png" ALT="$ x_2 = 1$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img8.png" ALT="$ x_3 = 0$">
 On obtient une suite <IMG WIDTH="11" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img9.png" ALT="$ 3$"> périodique.
 
 <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img10.png" ALT="$ (2)$"> <IMG WIDTH="41" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img11.png" ALT="$ a = 2$">, <IMG WIDTH="39" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img3.png" ALT="$ c = 2$">, <IMG WIDTH="46" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img4.png" ALT="$ m = 3$"> : <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img5.png" ALT="$ x_0 = 0$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img6.png" ALT="$ x_1 = 2$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img12.png" ALT="$ x_2 = 0$">
 On obtient une suite <IMG WIDTH="11" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img13.png" ALT="$ 2$"> périodique.
 
 <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img14.png" ALT="$ (3)$"> <IMG WIDTH="41" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img11.png" ALT="$ a = 2$">, <IMG WIDTH="39" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img15.png" ALT="$ c = 1$">, <IMG WIDTH="46" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img16.png" ALT="$ m = 2$"> : <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img5.png" ALT="$ x_0 = 0$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img17.png" ALT="$ x_1 = 1$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img7.png" ALT="$ x_2 = 1$">
 On obtient une suite <IMG WIDTH="11" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img18.png" ALT="$ 1$"> périodique à partir du rang 1.
 
 <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img19.png" ALT="$ (4)$"> <IMG WIDTH="49" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img20.png" ALT="$ a = 15$">, <IMG WIDTH="39" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img15.png" ALT="$ c = 1$">, <IMG WIDTH="46" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img21.png" ALT="$ m = 4$"> : <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img5.png" ALT="$ x_0 = 0$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img17.png" ALT="$ x_1 = 1$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img12.png" ALT="$ x_2 = 0$">
 On obtient une suite <IMG WIDTH="11" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img13.png" ALT="$ 2$"> périodique.
 
 <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img22.png" ALT="$ (5)$"> <IMG WIDTH="41" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img23.png" ALT="$ a = 4$">, <IMG WIDTH="39" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img3.png" ALT="$ c = 2$">, <IMG WIDTH="46" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img24.png" ALT="$ m = 7$"> : <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img5.png" ALT="$ x_0 = 0$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img6.png" ALT="$ x_1 = 2$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img25.png" ALT="$ x_2 = 3$">, <IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img8.png" ALT="$ x_3 = 0$">
 On obtient une suite <IMG WIDTH="11" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img9.png" ALT="$ 3$"> périodique.
 
 
 Je me permets donc de conjecturer que :
 
 <IMG WIDTH="27" HEIGHT="15" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/1/91982/cv/img1.png" ALT="$ \bullet\quad$">
Si <IMG WIDTH="63" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img26.png" ALT="$ a = 0[m]$"> la suite est <IMG WIDTH="11" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img18.png" ALT="$ 1$"> périodique à partir du rang 1.
 <IMG WIDTH="27" HEIGHT="15" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/1/91982/cv/img1.png" ALT="$ \bullet\quad$">
Si <IMG WIDTH="63" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img27.png" ALT="$ a = 1[m]$"> la suite est <IMG WIDTH="97" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img28.png" ALT="$ m/pgcd(c,m)$"> périodique.
 <IMG WIDTH="27" HEIGHT="15" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/1/91982/cv/img1.png" ALT="$ \bullet\quad$">
Si <IMG WIDTH="63" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img29.png" ALT="$ a \neq 1[m]$"> et <IMG WIDTH="63" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img30.png" ALT="$ a \neq 0[m]$"> et si <IMG WIDTH="17" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img31.png" ALT="$ m$"> est premier alors la suite est au plus <IMG WIDTH="57" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img32.png" ALT="$ (m-1)$"> périodique (au sens où elle possède peut-être une période plus petite (qui est alors un diviseur de <IMG WIDTH="57" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img32.png" ALT="$ (m-1)$">, cf. ex. <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img22.png" ALT="$ (5)$">).
 Et l'exemple <IMG WIDTH="23" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img19.png" ALT="$ (4)$"> me laisse peu d'espoir d'obtenir mieux...
 
 J'en profite d'ailleurs pour corriger mon premier post : dans le cas <IMG WIDTH="63" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img29.png" ALT="$ a \neq 1[m]$"> et <IMG WIDTH="63" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img30.png" ALT="$ a \neq 0[m]$"> il fallait lire :
 <IMG WIDTH="295" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img33.png" ALT="$ (1 - a)x_{n+m-1} = a^{m-1} ((1 - a)x_{n} - c) + c$">
 <IMG WIDTH="281" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img34.png" ALT="$ (1 - a)x_{n+m-1} = ((1 - a)x_{n} - c) + c [m]$"> car alors <IMG WIDTH="92" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img35.png" ALT="$ a^{m-1} = 1[m]$">
 <IMG WIDTH="120" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img36.png" ALT="$ x_{n+m-1} = x_{n} [m]$"> car <IMG WIDTH="51" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img37.png" ALT="$ (1-a)$"> est inversible modulo <IMG WIDTH="17" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/22/93595/cv/img31.png" ALT="$ m$"> 
[Et voilà avec un peu de mise en forme

AD]

all1 · July 2006

Bonjour SadYear,

Oui, c'est de ma faute, j'ai oublié une hypothèse:

La suite xn+1 = (a xn + c) (modm) a une période égale à m si et seulement si :
1) les entiers c et m sont premiers entre eux.
2) Pour tout facteur premier p de m, a − 1 est un multiple de p et si m est un multiple de 4, alors a − 1 est un multiple de 4.

Avec les résultats que tu énonces, ça donne une bonne base de travail.
Merci et Désolé,

All

P.Fradin · July 2006

Si ma mémoire est bonne ces problèmes sont traités par D. Knuth dans un des tomes de "The Art of Computer Programming" (dans la partie consacrée aux générateurs de nombres aléatoires)

Nombres premiers

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 19