Reste périodique
dans Arithmétique
Bonjour,
Soit $n \geq 2$ et $a \in \Z$ un entier premier avec $n$.
Pour $k \in \N$ on note $r_k$ le reste de la division euclidienne de $a^k$ par $n$.
Montrer que la suite $(r_k)$ est périodique.
Je n'arrive pas à savoir quelle sera la période donc je suis bloqué.
Soit $n \geq 2$ et $a \in \Z$ un entier premier avec $n$.
Pour $k \in \N$ on note $r_k$ le reste de la division euclidienne de $a^k$ par $n$.
Montrer que la suite $(r_k)$ est périodique.
Je n'arrive pas à savoir quelle sera la période donc je suis bloqué.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
As-tu essayé des applications numériques ?
Il suffit de montrer que la suite $(\bar{a}^k)_k$ à valeurs dans $\Z/n\Z$ est périodique (est-ce clair pour toi ?). Ensuite, $a$ étant premier avec $n$, que sait-on de $\bar{a}$ dans $\Z/n\Z$ ?
Non je n'ai pas compris votre remarque Calli mais les raisonnement avec le groupe $Z/nZ$ je n'ai pas les connaissances pour.
Je prends $a=11$ et $n=3$.
On a $1=3 \times 0 + 1$ donc $r_0=1$
$11=3 \times 3 +2$ donc $r_1=2$
$11^2=40 \times 3 +1$ donc $r_2=1$
Je ne vois pas la période de $r$ dans l'exemple.
Mais je ne vois pas en quoi ça m'aide pour trouver la période du reste.
Commence par prouver qu'il existe $k,k'$ distincts tels que $r_k=r_{k'}$.
$\Z$ est infini et $r_k \in [|0,n-1|]$ donc il y a un moment où $r_k =r_k'$
Édit : Attention, c'est $r_{k'}$, pas $r_k'$. Mais c'est probablement une coquille.
$n$ divise $a^k-r_k$ et $n$ divise $a^{k+T}-r_{k'}$
Mais après je ne vois pas.
Les notations sont-elles bien choisies ?
On doit montrer que $\forall k \in \N \ r_{k+T}=r_k$
Donc peut être prendre d'autres notation pour l'existence de $k_1 \ne k_2$ tel que $r_{k_1} =r_{k_2}$ non ?
Travaille modulo $n$, ce sera plus pratique. Tu as des règles pour l'addition et la multiplication des nombres modulo $n$. Et utilise :
Donc commence par traduire $r_{k_1}=r_{k_2} $ modulo $ n$, ainsi que $r_k=r_{k+T}$.
Si je note $r_{k_1}=r_{k_2}=r$ et $T=k_2-k_1$ alors : $a^{k_1} \equiv r[n]$ et $a^{k_1+T} \equiv r[n]$
J'aboutis à $r a^T \equiv r[n]$.
On a : $a \wedge n=1$.
1 est le dernier reste non nul et le $PGCD(a,n)=PGCD(n,r_i) \cdots$ donc $a \equiv 1 [n] \implies a^T \equiv 1[n]$
Mais $a^{T+k} \equiv r_k a^T [n] \equiv r_k [n]$ avec $a^{T+k} \equiv r_{k+T} [n]$
Par transitivité on a montré $\boxed{r_k = r_{k+T} }$
@OShine : je cherche avec toi.
D'abord, application numérique : $\displaystyle a=11$ et $\displaystyle n=3$ qui sont bien premiers entre-eux.
On écrit $\displaystyle 11^k = r_k + 3 p_k$ pour $\displaystyle k \in \N.$ On calcule : $\displaystyle r_0=1, r_1=2, r_2=1, r_3=2, r_4=1.$ On conjecture que la suite $r$ est périodique de période $2$ : pour tout $\displaystyle k \in \N$, $r_{k+2} = r_k.$
Voici une démonstration par le binôme de Newton :
On a $\displaystyle 11^k = (3.4 - 1)^k = \sum_{q=0}^k C_k^q (3.4)^q (-1)^{k-q} = (-1)^k+ \sum_{q=1}^k C_k^q (3.4)^q (-1)^{k-q} = (-1)^k \mod(3).$
On a donc, pour tout $\displaystyle k \in \N$, $\displaystyle r_{k+2} = (-1)^{k+2} \mod(3) = (-1)^k \mod(3) = r_k \mod(3).$
Encore une application numérique : $\displaystyle a=17$ et $\displaystyle n=5$ qui sont bien premiers entre-eux. On calcule : $\displaystyle r_0=1, r_1 = 2, r_2=4, r_3=3, r_4=1, r_5=2, r_6=4, r_7=3.$ On conjecture que la suite $r$ est périodique de période $4$ : pour tout $\displaystyle k \in \N$, $\displaystyle r_{k+4}=r_k.$
On tente encore une démonstration par le binôme de Newton :
On a $\displaystyle 17^k = (3.5+2)^k = \sum_{q=0}^k C_k^q (3.5)^q 2^{k-q} = 2^k + \sum_{q=1}^k C_k^q (3.5)^q 2^{k-q} =2^k \mod(5).$
On a donc, pour tout $\displaystyle k \in \N$, $\displaystyle r_{k+4} = 2^{k+4} \mod(5) = 2^k .16 \mod(5) = 2^k .(3.5+1) \mod(5) =2^k \mod(5) = r_k.$
Dans le cas général, on a $\displaystyle a=r+np$ et donc $\displaystyle a^k=r^k \mod(n) = r_k \mod(n).$ Il suffit donc de démontrer qu'il existe $T$ entier non nul tel que $\displaystyle r^T = 1 \mod(n)$ car alors, pour tout $\displaystyle k \in \N$, $\displaystyle r_{k+T} = r^{k+T} \mod(n) = r^k.r^T \mod(n) = r_k \mod(n) = r_k.$
La suite après le déjeûner.
Merci pour les exemples. Je n'ai pas trop compris ce que vous faites avec le binôme de Newton. Ça m'a l'air compliqué comme technique. C'est quoi ces $3.5$ et $3.4$ ?
Mais les questions 2 et 3 demandent des applications numériques. Je viens de les terminer et ça fonctionne parfaitement.
3.5=15 et 3.4=12
Indication pour finir le travail de @Yves.Meyer.
Exploiter le fait que a admet un inverse dans $\Z/n\Z$ c'est dire qu'il existe un entier b
tel que $a b= 1$ (mod n) et le fait qu'il existe $ k,j\in \N, j\neq 0$ tel que $a^{k}=a^{k+j} $ (mod n) .
Je n'ai pas vu Z/nZ ni les inverses dans cet anneau.
Dans le raisonnement des congruences ce que je ne comprends pas c'est à quel moment on utilise $PGCD(a,n)=1$ ni comment le traduire en congruences.
J'arrive à $r a^T \equiv r[n]$ et donc $a^{T+k} \equiv r_k a^{T} [n]$
Il faut montrer qu'il existe b tel que ab=1 (mod n) la congruence tu as vu.
Et pour montrer ça on utilise que pgcd(a,n)=1.
Il faut montrer que $a^T \equiv 1 [n]$
C'est ce point que me bloque.
Je me dis que j'aurais du raisonner sans congruence en utilisant le théorème de Gauss...
Il faut montrer qu'il existe b tq ab=1 mod (n) . !!!!!!!!
OShine, si je comprends bien tu es en mpsi donc tu n'as pas beaucoup de temps à perdre.
Alors je te conseille de bien revoir ton cours d'abord.
Par exemple sur cette question, il faudra que tu nous dise ce que tu sais:
1) les congruences sont-elles au programme.
2) si la réponse est oui, quelles propriétés sont au programme.
Sinon tu n'accepteras rien des précieux conseils qui te sont donnés par tout le monde.
Cordialement.
Le seule propriété c'est somme et produit de congruence.
Z/nZ n'est pas au programme. Je l'ai dit au départ mais on me dit d'utiliser l'inversibilité alors que je ne l'ai pas vu.
Le cours ça fait 3 semaines que je suis dessus.
Alors Calli t'as donné l'indication que tu as comprise.
En notant $r = r_{k_1} = r_{k_2}$
$a^{k_1} \equiv r [n]$ et $a^{k_1+T} \equiv r [n]$
Donc $r a^T \equiv r[n]$
Mais je n'arrive pas à montrer que $a^T \equiv 1 [n]$
Je ne sors pas de ce bourbier.
> Je n'ai pas compris qui est $b$ ni pourquoi on
> veut montrer ça.
ça me semble bizarre puisque dans un autre message @gb te donne la réponse et tu dis avoir compris.
a et premier avec n dont (Bezout) il existe deux entiers b et p tels que
ab +np=1 ce qui veut exactement dire que ab=1 mod n.
Ensuite soit deux entiers différents tels que $a^k = a ^j$ (mod n) . On suppose que k>j.
Alors $ a^k b^j= a^j b^j =(ab) ^j=1 $ (mod n)
Donc on a $a^{k-j}=1$ mod (n) . En posant T=k-j on a répondu à la question posée par Y.M
$n$ divise $a^{k_1}-r$ et $n$ divise $a^{k_1+T}-r = a^T (a^{k_1}-r)-r+ra^T$ donc $n$ divise $r(a^T-1)$
Or $PGCD(a^k,n)=PGCD(a^k,r_k)=1$ donc d'après le théorème de Gauss $n$ divise $a^T-1$
On a $n$ divise $a^k - r_k$ et $n$ divise $a^{T+k}-r_k = a^k (a^T-1)+a^k -r_k$
Finalement $n$ divise $a^{T+k}-r_k$.
Première propriété : il n'y a qu'un nombre fini de valeurs possibles pour les restes \(r_k\).
Conséquence : le principe des tiroirs assure l'existence de \(p\) et \(q\) avec \(p<q\) et \(r_p=r_q\).
Deuxième propriété : si \(r_k=r_l\), alors \(r_{k+1}=r_{l+1}\).
Consquence : une récurrence assure que, pour tout entier \(m\), \(r_{p+m}=r_{q+m}\), c'est-dire que la suite des restes est \(q-p\)-périodique à partir du rang \(p\).
Les résultats obtenus sont valables que \(a\) et \(n\) soient premiers entre eux ou non.
Exemple: avec \(a=4\) et \(n=40\) qui ne sont pas premiers entre eux.
\begin{align*} 4^0 &= 1 = 0 \times 40+1 & 4^1 &= 0 \times 40+4 \\
4^2 &= 16 = 0 \times 40 +16 & 4^3 &= 64= 1 \times40 +24\\
4^4 &= 256 = 6 \times 40 + 16 \end{align*}
donc \(r_2=r_4 = 16\) et la suite des restes est 2-périodique à partir du rang 2.
Lorsque \(a\) et \(n\) sont premiers entre eux, la suite est périodique et il faut établir qu'elle « repasse » par la valeur \(r_0=1\).
Pour y arriver, on peut envisager de « redescendre » à partir de \(r_p=r_q\) pour obtenir : \(r_0=r_{q-p}\) et pour ce faire d'établir l'implication : si \(r_k=r_l\), alors (r_{k-1}=r_{l-1}\). On a alors besoin d'un entier \(u\) tel que \(au \equiv 1 \pmod n\), c'est-à-dire d'un inverse de \(a\) dans \(\Z/n\Z\).
Je ne comprends pas votre démonstration.
Votre méthode m'embrouille, je vous ai dit que j'arrivais pas à montrer avec les congruences que $a^T \equiv 1[n]$ mais vous partez sur une autre méthode qui me fait tout mélanger j'y comprends plus rien.
Je pense que la démonstration par congruence n'est pas adaptée à mon niveau de conaissances.
Vous semblez utiliser l'inverse dans Z/nZ je n'ai pas vu ça.
Par ailleurs, j'ai donné une démonstration utilisant uniquement le théorème de Gauss.
Le passage $a^T \equiv 1[n]$ je n'arrive pas à le comprendre.
$au+nv=1$ je suis d'accord donc $au \equiv 1 [v]$ mais on sait même pas qui est $u$ :-S
Donc écrire que $au \equiv 1 [n]$ je ne vois pas comment je pourrais en déduire que $a^T \equiv 1 [n]$
Ca me donne uniquement $a^T u^T \equiv 1[n]$ et que je sais même pas qui est $u^T$
Pour mettre en œuvre ma démarche, on peut calculer les restes:
— soit en établissant des égalités de la division euclidienne ;
— soit en utilisant des congruences.
La seule différence est que l'utilisation de congruences soulage les écritures en occultant les multiples de \(n\) qui ne servent à rien.
On a besoin, dans la dernière partie, d'un entier \(u\), fourni par Bézout, que l'on utilise soit via l'égalité \(au+nv=1\), soit via la congruence \(au \equiv 1 \pmod n\).
Je ne vois pas le rapport avec l'exercice qui demandait de prouver $a^{k-j} \equiv 1[n]$
Ni comment à la fin vous obtenez $a^{k-j} \equiv 1 [n]$
Oui mais on ne connait pas $u$ c'est ça que je ne comprends pas. On a $au \equiv 1[n]$.
Comment arriver à $a^T \equiv 1[n]$ ?
\begin{align*}
a^k &= qn+r_k \\
a^ku &= (qu)n+ur_k\\
a^{k-1}(1-nv) &= (qu)n+ur_k \\
a^{k-1} &= (a^{k-1}v+qu)n+ur_k
\end{align*}
Je divise \(ur_k\) par \(n\) :
\begin{align*}
ur_k &= q'n+r \\
a^{k-1} &= (a^{k-1}v+qu+q')n+r
\end{align*}
Le reste \(r_{k-1}\) est donc me reste de la division de \(ur_k\) par \(n\), ce qui me permet d'affirmer : si \(r_k=r_l\), alors \(r_{k-1}=r_{l-1}\).
> Je ne comprends pas qui est votre $b$ ni pourquoi
> vous partez de $a^k \equiv b^j [n]$
> faux il faut lire
>
> Je ne vois pas le rapport avec l'exercice qui
> demandait de prouver $a^{k-j} \equiv 1[n]$
> c'est que je démontre ???
>
> Ni comment à la fin vous obtenez $a^{k-j} \equiv
> 1 [n]$
$a^T= 1$ mod n c'est que Y.M a expliqué!!!
T est une période (pas forcément la plus petite)
Et bien puisque à chaque explication pratiquement hyper détaillée on t'embrouille
et bien j'abandonne par KO.
Je ferai la remarque supplémentaire que le peu que je me suis permis d'affirmer et bien c'est parce que quelqu'un d'autre l'a déjà fait.
D'autre part je n'ai employé que de la congruence.
Je n'ai pas compris où on utilise $r_k=r_l$ dans la démonstration. $r_l$ n'apparaît jamais dans les lignes de calcul. Pareil pour $r_{l-1}$.
J'ai du mal à comprendre le principe de votre raisonnement.
Je comprends les lignes de calculs mais je ne vois pas où on utilise $r_k=r_l$ ni où on montre $r_{l-1} =r_{k-1}$
La méthode la plus simple est utiliser uniquement la divisibilité et Gauss. J'ai écrit la démonstration plus haut elle tient en 5 lignes.
Ok j'ai relu et l'unique point qui me bloque est la transition de $a^k b^j \equiv 1[n]$ à $a^{k-j} \equiv 1 [n]$
Je ne comprends pas comment vous faites.
@Gb
Votre méthode a l'air vraiment difficile.
Je continues après des tagliatelles au saumon...
Les restes $\displaystyle r_k$ de la division euclidienne de $\displaystyle a^k$ par $\displaystyle n>1$ peuvent être choisis positifs et donc dans $\displaystyle \{0,1,2,\cdots, n-1\}$ , ensemble de cardinal $n.$
Il existe au moins un couple d'entiers $\displaystyle j,k$ avec $\displaystyle k>j$ tels que $\displaystyle r_k=r_j.$
Pour le montrer, il suffit de commencer par calculer les puissances $\displaystyle a^p$ et les restes $\displaystyle r_p$ appartiennent à l'ensemble de cardinal $n.$ A chaque nouvelle puissance $\displaystyle p \leadsto p+1$, son reste est soit égal à un autre reste (et on a trouvé notre couple), soit est différent de tous les restes calculés jusqu'alors et les restes prennent alors toutes les $n$ valeurs possibles. Le prochain calcul fournit alors le couple.
Comme $a$ et $n$ sont premiers entre-eux, il existe deux entiers relatifs $u,v$ tels que $\displaystyle au+nv=1$ (par Bézout).
On a donc $\displaystyle au=1 \mod(n).$
Comme on a $\displaystyle a=r \mod(n)$, on a $\displaystyle ru = 1 \mod(n)$ par (*).
Comme on a $\displaystyle r_k=r_j$, on a $r^k = r^j \mod(n)$ (on l'a établi par le binôme de Newton).
On calcule alors $\displaystyle r^k u^j = r^j u^j = (ru)^j = 1 \mod (n).$
Enfin, on calcule $\displaystyle r^{k-j} r^j u^j = 1 \mod(n)$ c'est-à-dire $\displaystyle r^{k-j} (ru)^j = 1 \mod(n)$ et donc $\displaystyle r^{k-j} = 1 \mod(n)$ par (*).
On choisit alors $\displaystyle T=k-j>0$ : on a montré l'existence d'un entier non nul tel que $\displaystyle r^T=1 \mod (n).$
(*) Dans les calculs précédents, on a utilisé (avec des notations évidentes) :
Si $\displaystyle A=a \mod(n)$ ET $\displaystyle AB=p \mod(n)$ alors $\displaystyle aB=p \mod(n).$
En effet, $\displaystyle A=a+nX$ ET $\displaystyle AB=p+nY$ implique $\displaystyle (a+nX)B=p+nY$ puis $\displaystyle aB = p + n(Y-XB).$
> @Bd2017
>
> Ok j'ai relu et l'unique point qui me bloque est
> la transition de $a^k b^j \equiv 1[n]$ à
> $a^{k-j} \equiv 1 [n]$
>
> Je ne comprends pas comment vous faites.
>
$a^k b^j= a ^{k-j} a ^j b^j = a ^{k-j} (a b)^j =1 $
Justement parce que ab= 1 mod n
Merci monsieur c'est une démonstration très claire. J'ai néanmoins une interrogation :.
Le passage avec le binôme de Newton j'avoue que je sèche $r_k =r_j \implies r^k = r^j$.
Je ne vois pas d'où partir pour utiliser le binôme de Newton.
Vous pensez pas que c'est utiliser l'artillerie lourde pour tuer une mouche ?
Le théorème de Gauss et la divisibilité donne une solution élémentaire qui tient en 5 lignes compréhensible par un élève de terminale S.
Merci j'avais pas vu cette astuce d'écriture :-(
Avec $r$ le reste de la division euclidienne de $a$ par $n$, on a $\displaystyle a=x n + r.$ On a donc, pour tout $k$ entier, $\displaystyle a^k = (x n+r)^k = \sum_{q =0}^k C_k^q (x n)^q r^{k-q} = r^k + \sum_{q =1}^k C_k^q (x n)^q r^{k-q} =r^k \mod(n).$
On note $\displaystyle r_k$ le reste de la division euclidenne de $\displaystyle a^k$ par $n$ et donc $\displaystyle a^k = r_k \mod(n).$
On a donc $\displaystyle r^k = r_k \mod(n).$
Il suffit d'imposer que les tous les restes de la division euclidienne par $n >1$ soient dans $\displaystyle \{0,1, \cdots, n-1\}$ pour avoir $\displaystyle r^k = r_k.$
Je ne connais par l'arithmétique donc je ne sais pas si des théorèmes élémentaires permettent de conclure bien plus rapidement.
J'essaie de passer par les méthodes les plus simples pour résoudre les exercices sinon j'y passe des heures et sur les rapports du CAPES on demande juste d'être capable de rédiger des démonstrations simples rigoureusement.
Ici la méthode utilisant les congruences que m'a suggéré Calli n'était pas une méthode élémentaire.
Il était plus simple de passer par le théorème de Gauss et utiliser $PGCD(a^k,n)=(PGCD(n,r_k)$
Votre méthode était difficile.
Vous avez dit que ça simplifiait les congruence mais pas du tout.
Regardez ma démonstration plus haut qui prend 5 lignes avec le théorème de Gauss.
Et ce serait bien qu'un jour tu arrêtes de rejeter les notions que tu ne comprends pas. Ce n'est pas comme ça que tu vas progresser.
Et puis, tutoie-moi, stp. Je n'ai pas l'âge d'être vouvoyé comme un prof.
Juste que tu as dit que les congruences simplifiait alors que non. Il y a un passage délicat pour démontrer que $a^T \equiv 1[n]$. La démonstration d'Yves le prouve, utilisation du binôme plus plusieurs étapes de raisonnement pas évidentes à trouver seul.
J'essaie de trouver les méthodes de résolutions les plus simples des exercices sinon j'avancerai jamais je vais rester 5 jours sur un exercice et dans 3 ans j'aurais toujours pas terminé le programme de MPSI.
J'essaie de travailler efficacement.
Puis je ne rejette pas j'y arrive pas tout simplement. Exemple le raisonnement de @gb avec les $r_{k-1}=r_{l-1}$ je n'ai pas compris pourtant je suis resté 30 minutes à le relire ça veut pas. Y a un blocage.
Est-ce utile que j'y passe une journée ? A vous de me le dire.
Si j'ai bien compris toutes les explications et pour résumer:
1) il existe $k_1<k_2$ tel que $a^{k_1}\equiv a^{k_2} [n]$ et tu as posé $k_2=k_1+T$.
2) Bézout: il existe u tel que $ua\equiv 1 [n]$
3) Le 1) nous donne $a^{k_1}\equiv a^{k_1+T} [n]$; donc $u^{k_1}\times a^{k_1}\equiv u^{k_1}\times a^{k_1+T} [n]$.
Ainsi $(ua)^{k_1}\equiv (ua)^{k_1}\times a^T [n]$.
Le 2) te donnes alors $1\equiv a^T [n]$.
Sur quel point tu bloques?