Congruence
dans Arithmétique
Bonjour à tous, je suis débutant et je bloque sur si $\mathrm{pgcd}(a,b)\ne1,\ \exists (m,n)\in {N^2}, \ a^m-a^n=k.b$.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Écrit tel quel, on peut prendre $m=n=k=0$ et la proposition serait vraie même si $pgcd(a,b) =1$...
Il faut préciser ton énoncé. Tel qu'il est, le résultat est trivial : $m=n$ et $k=0$.
En fait, l'exercice commence par : démontrer que si $a$ et $b$ sont premiers entre eux, et si on divise les nombres ${a, 2a, 3a,\ldots,(b-1)a}$ par $b$ on obtiendra $(b-1)$ restes différents dont aucun n'est nul et qui ne sont autres que les nombres $1, 2, 3,\ldots,(b-1)$ rangés dans un certain ordre...
Ensuite on considère la suite géométrique $1,a, a^2, a^3,\ldots$ Si l'on divise tous les termes par $b$ premier à $a$, les restes se reproduisent périodiquement...
En fait la première partie est facile... la seconde partie où l'on considère la suite, j'ai voulu d'abord voir ou vérifier ou tester que si $a$ et $b$ ne sont pas premiers entre eux aura-t-on nécessairement une non périodicité des restes ? Autrement dit si $\mathrm{pgcd}(a,b)\ne1,\ \exists (m,n)\in {\N^2}, \ a^m-a^n=k b$.
En considérant $p:\mathrm{pgcd}(a,b)=1$ et $q$ : périodicités des restes.
Si $p\Rightarrow q$ a-t-on nécessairement $\neg (\neg p\Rightarrow q)\ ?$
Ensuite, on veut que la suite soit périodique, et non périodique à partir d'un certain rang.
Par conséquent, si ladite suite était périodique, il faudrait qu'il existe $n > 0$ tel que $a^n$ ait pour reste $1$. Or, d'après Bézout (si tu as vu le théôrème de Bézout...), cela implique que $a$ et $b$ sont premiers entre eux.
En fait, la difficulté c'est ce $1$ qui débute la suite géométrique. Si on s'intéressait à la suite $a,a^2,a^3,...$ plutôt, alors elle serait périodique même si $a$ et $b$ ne sont pas premiers entre eux.
Soit $a\in \mathbb Z$. Soient les propriétés $P \ : \ " a \in \mathbb N" $ et $Q \ : \ " a \in \mathbb Z "$.
$Q$ est donc vraie.
On a alors $P \Longrightarrow Q$ et $\neg P \Longrightarrow Q$.
Bon courage !
$a$ et $b$ sont premiers entre eux, si on divise les nombres ${a, 2a, 3a,\ldots,(b-1)a}$ par $b$ on obtiendra $(b-1)$ restes différents dont aucun n'est nul et qui ne sont autres que les nombres $1, 2, 3,\ldots,(b-1)$ donc si on suppose que $a=bq +r , r\ne 1$ alors $a^2=b.q.a+r.a$ et $r.a$ donnera un reste nécessairement différent de $r$ car $\forall (m,m')\in(1,2,3...b-1)^2 ma\not\equiv ma'$ [modulo $b$] ...en continuant les calculs en multipliant chaque reste par $a$ on tombera nécessairement sur un reste égal à $1$ et c'est la plus petite puissance de $a$ pour laquelle $a^p-1=b.k$... on est toujours sûr d'avoir $1$ comme reste... autrement dit la période sera égale à $p$ mais on peut atteindre cette première puissance sans passer par d'autres restes qui sont inférieurs à $b-1$, et donc aucune puissance de $a$ ne donne ces restes. le $1$ qui déclenche la suite $1,a, a^2, a^3...$ ne dérange pas car on aura $1, a, a^2,...a^{p-1}, a^p...$ ($1=b.0+1)$pour dire que la période est bien $p$... Peut-être que j'ai mal exprimé ce que je voulais dire mais je crois que c'est vrai. Merci de rectifier ou de corriger
Je pense que tu voulais imposer $m \neq m'$.
$a$ et $ra$ peuvent tout à fait avoir le même reste si $a=1$. Mais c'est ce que l'on veut.
L'étape "en continuant les calculs" peut être un peu délicate. Peut-être qu'on aura une certaine puissance $p$ tel que $a^p - a^{m} = b \cdot k$ avec $m \in \{ 1,2,3,...,p-2 \}$ sans retourner sur notre $1$.
Il faut formuler et démontrer la récurrence correctement.
Ce que je disais, c'est que si $a$ et $b$ sont premiers entre eux, on va pouvoir retomber sur $1$. Toutefois, si $a$ et $b$ ne sont pas premiers entre eux, on ne peut pas retomber sur $1$.
Par exemple, si $a=2$ et $b=4$, on aura $a^k \equiv 0 \pmod b$ pour tout $k \in \mathbb N \setminus \{ 0,1 \}$.
En fait, tu utilises le principe des tiroirs pour montrer qu'on aura forcément des entiers $p$ et $m\in \{ 1,2,3,...,p-2 \}$ tels que $a^p - a^{m} = b \cdot k$. Mais cela ne garantit pas que l'on puisse retomber sur $1$ comme le montre le cas $a=2$ et $b=4$.
Je crois qu'on n'a pas besoin de récurrence et qu'il s'agit juste de trouver la première puissance de a qui soit congrue à a...ainsi on a une période... Merci à vous
Écrit tel quel, tu montres qu'on retombera sur une puissance antérieure, mais comme je te l'ai expliqué, cette puissance ne sera pas forcément $1$ et il faut que $a$ et $b$ soient premiers entre eux pour retomber sur $1$, sinon c'est impossible.
Or tu n'as pas l'air d'exploiter cette primalité relative à ce moment de ta démonstration qui est assez vague, donc peut-être qu'il faudra formuler et démontrer proprement ce qui t'intéresse.
Les idées te seront plus claires en continuant d'apprendre et de travailler ce cours d'arithmétique. Comprendre la structure d'anneau de $\mathbb{Z/bZ}$ et ses inversibles te permettra de comprendre toutes les éventuelles difficultés de ton exercice.