DM de math spé . Suite et périodicité

[invite781962c1]

Voila, j'ai un gros probleme .. Apres avoir chercher et trifouiller ce DM dans tous les sens , je n'arrive a aucune conclusion utilie.. Et c'est pour ce jeudi .. ( mon prof étant renommé pour faire des DM interminable .. ) mais je n'exclus pas l'idée que mon cerveau soit defaillant ..
J'espere que vous pourrez m'aider .

Sujet : Soient n un entier naturel non nul , et a un entier relatif. Pour tout entier naturel k , on note r indice k le reste de la division euclidienne de a puissance k ( soit a^k ) par n .

Question 1 ) Démontrer proprement que la suite ( r indice k) est periodique à partir d'un certain rang, c'est à dire qu'il existe un entier naturel non nul p (période) et un entier naturel k zero (k0) tels que :
Pour tout k superieur ou egal a k0, r indice k+p = r indice k

Question 2 ) On note p0 la plus petite periode de la suite ( r indice k ) . Démontrer que toutes les périodes de ( r indice k ) sont des multiples de p0. ( on dit que p0 est la periode principale de a^k modulo n ) .
On pourra par exemple prouver que le reste de la division euclidienne de p par p0 est nul
-----

[Jeanpaul]

Déjà voir que r(k) est <n, donc ne peut avoir que n valeurs différentes (de 0 à n-1)
a^k est congru à r(k) modulo n donc a^(k+1) congru à a r(k) modulo n qui est congru à r(k+1)
Forcément, au bout de p0, ça va boucler, quand a^p0 r(k) congru à r(k) modulo n.
Et ensuite ça recommence, ça devient périodique.

[invite781962c1]

Merci beaucoup pour ces pistes !
Maintenant , j'avoue n'avoir pas trop compris à partir de ' forcément ...'
M'enfin , je vais y réflechir et je vais surment finir par comprendre hein...
Merci d'avoir répondu aussi vite en tout cas .

[Jeanpaul]

Si tu alignes des nombres entre 0 et n-1, au pire au bout de n coups, tu trouveras une valeur déjà écrite, peut-être avant.

[A voir en vidéo sur Futura]

[invite781962c1]

Hum , oui en effet, c'est plutot logique .
Mais , je vois vraiment pas comment " démontrer proprement" ..
Si t'as d'autre idées , n'hésite pas
Et aussi , tu entends quoi par " si tu alignes .." ..

[Jeanpaul]

Tu écris que a^k congru à r(k) modulo n
a^(k+1) congru à a.r(k) et aussi à r(k+1)
et tu poursuis.
A un moment donné, forcément, on arrivera à
a^(k+p0) congru à a^p0 r(k) congru à r(k+p0) avec r(k+p0) = r(k)

On peut alors continuer et dire que
a^(k+p0+1) congru à a r(k)
et ainsi de suite jusqu'à k+2 p0 qui sera congru à r(k)
On a donc une périodicité.

p0 est le plus petit nombre pour lequel il y a répétition, on ne rencontrera donc r(k) qu'en k, k+p0, k+2 p0, etc... C'est la plus petite période.

[invite781962c1]

Ouaou , là je dis ' chapeau bas ' ..
Bon, et bien , je n'ai plus qu'à vous remercier .
Merci mille fois pour votre aide !