Mathématiques - suite périodique (MPSI)

suite périodique (MPSI)
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: Emmanuelle89

bonjour,
soit n un entier naturel tel que n>=2
a un entier relatif
n et a premiers entre eux
k un entier naturel, on note Rk le reste de la division euclidienne de a^k par n.
J'aimerais que vous me donniez une PISTE et non la REPONSE pour montrer que la suite Rk est périodique svp...

Posted by: Dominique Lefebvre

Citation:

Posté par Emmanuelle89

bonjour,
soit n un entier naturel tel que n>=2
a un entier relatif
n et a premiers entre eux
k un entier naturel, on note Rk le reste de la division euclidienne de a^k par n.
J'aimerais que vous me donniez une PISTE et non la REPONSE pour montrer que la suite Rk est périodique svp...

Bonsoir,
Tu peux partir de la définition d'une suite périodique: c'est généralement un bon point de départ! Définition qui est : ?

Posted by: Emmanuelle89

(Un) est périodique ssi Un+p=Un
Je vois très bien pourquoi (Rk) est périodique car 0<=Rk<n et les congruences sont toujours périodiques mais je n'arrive pas à faire une vraie démo...

Posted by: alben

Citation:

Posté par Emmanuelle89

(Un) est périodique ssi Un+p=Un
Je vois très bien pourquoi (Rk) est périodique car 0<=Rk<n

Soit n valeurs possibles
Oui, donc si tu prends n+1 termes successifs de ta suite...

Citation:

Posté par Emmanuelle89

et les congruences sont toujours périodiques

ça ne veut rien dire
Il te faut regarder ce qui se passe pour les successeurs si $R_{k}=R_{k+p}$

Posted by: Emmanuelle89

ça fait 3 jours que je tourne en rond :'(

Posted by: lapras

salut,
à ta place je regarderais du coté du petit théoreme de fermat !

Ca ne te donnera pas la plus courte période, mais une période.

Posted by: Emmanuelle89

Citation:

Posté par lapras

salut,
à ta place je regarderais du coté du petit théoreme de fermat !

Ca ne te donnera pas la plus courte période, mais une période.

Pour cela il faut que n soit premier et ce n'est pas le cas...

Posted by: abcd22

Bonjour,
Cherche le théorème d'Euler qui est plus général que le petit théorème de Fermat.

Posted by: Emmanuelle89

Citation:

Posté par abcd22

Bonjour,
Cherche le théorème d'Euler qui est plus général que le petit théorème de Fermat.

hum je vais chercher une démo de ce fameux théorème, je ne l'ai pas vu en cours mais peut-etre que la démo me débloquera...

Posted by: alben

Citation:

Posté par Emmanuelle89

ça fait 3 jours que je tourne en rond :'(

Je pense t'avoir tout indiqué dans ma réponse : 3 étapes;
- il existe deux termes de la suite qui prennent la même valeur
th. des bergers ou des tiroirs
-si deux termes sont égaux, leurs successeurs...
-la période commendès k=0 car....

Posted by: aviateurpilot

$a^{k}\equiv R_k[n]$
pour monter que $R_{k}$ est periodique il faux montrer l'existence d'un $p$ tel que $\forall k\in\mathbb{N}:\ R_{k+p}=R_{k}$ .
donc tu n'a que trouver un $p$ tel que $\forall k\in\mathbb{N}:\ a^{k+p}\equiv a^{k}[n]$ .(c'est tres facile si tu sais comment utiliser le fait que a est premier avec $n$ )

Citation:

$rappel:$
si x est premier avec y alors
i) $x^{\varphi(y)}\equiv 1[x]$
ii) $xh\equiv xn[y]$ <=> $h\equiv n[y]$

Posted by: Emmanuelle89

qu'est-ce que le théorème des tiroirs ou des bergers?

Posted by: Babe

Citation:

Posté par Emmanuelle89

qu'est-ce que le théorème des tiroirs ou des bergers?

si alben parle bien du principe des tiroirs, c'est:
si ta n chaussettes et m tiroirs, et n>m, alors au moins un tiroir doit contenir strictement plus d'une chaussette

Posted by: Emmanuelle89

Citation:

Posté par alben

Honnetement, j'ai du mal à comprendre.
Si k=0, $a^{0}=1\equiv1 [n]$
si $R_n=R_(n+p)$ alors $R_(n+1)=R_(n+p+1)$
mais le coup du th des bergers...
et je ne vois pas trop où cela mène

Posted by: aviateurpilot

Citation:

Posté par aviateurpilot

$a^{k}\equiv R_k[n]$
pour monter que $R_{k}$ est periodique il faux montrer l'existence d'un $p$ tel que $\forall k\in\mathbb{N}:\ R_{k+p}=R_{k}$ .
donc tu n'a que trouver un $p$ tel que $\forall k\in\mathbb{N}:\ a^{k+p}\equiv a^{k}[n]$ .(c'est tres facile si tu sais comment utiliser le fait que a est premier avec $n$ )

Emmanuelle89 tu n'a pas vu cela????

Posted by: alben

Ca devient pesant.
Emmanuelle89 a écrit 0<=Rk<n. Donc Rk peut prendre au plus n valeurs.
Principe des tiroirs : "si on met 11 chaussettes dans 10 tiroirs, un des tiroirs contient au moins 2 chaussettes".
En prenant, par exemple, les n+1 premiers termes de la suite, on est donc certain de trouver i et i+p tels que $R_i=R_{i+p}$ .
Par définition, $R_{i+1}=a^{i+1} mod(n)=[(a^i)mod(n)].[a mod(n)]=R_i.[a mod(n)]=R_{i+p}.[a mod(n)]=R_{i+p+1}$
et ainsi de suite.
La suite est donc périodique à partir de i. (sans utiliser le fait que a premier avec n)
On a besoin de a premier avec n pour montrer que la période commence dès Ro