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$.
Réponses
-
Est-ce que tu as d'autres hypothèses ?
Écrit tel quel, on peut prendre $m=n=k=0$ et la proposition serait vraie même si $pgcd(a,b) =1$... -
Bonjour,
Il faut préciser ton énoncé. Tel qu'il est, le résultat est trivial : $m=n$ et $k=0$. -
En fait, même si on renforce avec l'hypothèse $m\neq n$, le résultat reste vrai même si $pgcd(a,b)=1$. Il suffit d'appliquer le principe des tiroirs à l'ensemble $\{ a^i \pmod b \ \mid i \in \mathbb N \}$.
-
Merci à vous Nahar et Seb Baumert;
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)\ ?$ -
Une période ne peut pas être nulle, donc il faudrait imposer $n \neq m$.
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$. -
Merci Seb Baumert pour ta réactivité et pour le temps que tu as consacré! Je n'ai pas encore fait la connaissance de Bézout car je suis au début de l'arithmétique que j'étudie à partir du livre de Tannery "Leçons d'arithmétique théorique et pratique"
-
Ok. Alors regarde en quoi $a^n = 1 + kb$ implique que $a$ et $b$ sont premiers entre eux. On pourra considérer un diviseur commun à $a$ et $b$.
Bon courage ! -
(tu) Merci
-
Bonjour Seb baumert, bonjour à tous
$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 -
Bonsoir.
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$. -
Merci encore Seb Baumert,
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 -
Il faut que tu trouves une puissance qui soit congrue à $1$ et non à $a$. Autrement, la suite ne serait pas périodique mais périodique à partir d'un certain rang.
É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. -
Thanks Seb Baumert vraiment beaucoup...merci merci
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 39
+27 Invités