Nombres premiers
dans Arithmétique
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
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
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
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.
à 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
Bonne nuit,
All
<BR>
<BR><SPAN CLASS="MATH"><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)$"></SPAN> <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN> : <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>
<BR>On obtient une suite <SPAN CLASS="MATH"><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$"></SPAN> périodique.
<BR>
<BR><SPAN CLASS="MATH"><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)$"></SPAN> <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN> : <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>
<BR>On obtient une suite <SPAN CLASS="MATH"><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$"></SPAN> périodique.
<BR>
<BR><SPAN CLASS="MATH"><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)$"></SPAN> <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN> : <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>
<BR>On obtient une suite <SPAN CLASS="MATH"><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$"></SPAN> périodique à partir du rang 1.
<BR>
<BR><SPAN CLASS="MATH"><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)$"></SPAN> <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN> : <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>
<BR>On obtient une suite <SPAN CLASS="MATH"><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$"></SPAN> périodique.
<BR>
<BR><SPAN CLASS="MATH"><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)$"></SPAN> <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN> : <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>, <SPAN CLASS="MATH"><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$"></SPAN>
<BR>On obtient une suite <SPAN CLASS="MATH"><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$"></SPAN> périodique.
<BR>
<BR>
<BR><B>Je me permets donc de conjecturer que :</B>
<BR>
<BR><SPAN CLASS="MATH"><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$"></SPAN>
Si <SPAN CLASS="MATH"><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]$"></SPAN> la suite est <SPAN CLASS="MATH"><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$"></SPAN> périodique à partir du rang 1.
<BR><SPAN CLASS="MATH"><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$"></SPAN>
Si <SPAN CLASS="MATH"><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]$"></SPAN> la suite est <SPAN CLASS="MATH"><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)$"></SPAN> périodique.
<BR><SPAN CLASS="MATH"><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$"></SPAN>
Si <SPAN CLASS="MATH"><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]$"></SPAN> et <SPAN CLASS="MATH"><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]$"></SPAN> et si <SPAN CLASS="MATH"><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$"></SPAN> est premier alors la suite est au plus <SPAN CLASS="MATH"><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)$"></SPAN> périodique (au sens où elle possède peut-être une période plus petite (qui est alors un diviseur de <SPAN CLASS="MATH"><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)$"></SPAN>, cf. ex. <SPAN CLASS="MATH"><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)$"></SPAN>).
<BR>Et l'exemple <SPAN CLASS="MATH"><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)$"></SPAN> me laisse peu d'espoir d'obtenir mieux...
<BR>
<BR>J'en profite d'ailleurs pour corriger mon premier post : dans le cas <SPAN CLASS="MATH"><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]$"></SPAN> et <SPAN CLASS="MATH"><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]$"></SPAN> il fallait lire :
<BR><SPAN CLASS="MATH"><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$"></SPAN>
<BR><SPAN CLASS="MATH"><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]$"></SPAN> car alors <SPAN CLASS="MATH"><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]$"></SPAN>
<BR><SPAN CLASS="MATH"><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]$"></SPAN> car <SPAN CLASS="MATH"><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)$"></SPAN> est inversible modulo <SPAN CLASS="MATH"><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$"></SPAN><BR><BR><BR>
[Et voilà avec un peu de mise en forme AD]
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