Un pgcd

Tyoussef

Bonjour ou bonsoir (voir l'heure).

Soit $a$ un entier relatif, montrer que pour tout entier naturels $n$ et $m$ , on a :   $$ (a^n − 1 )∧ (a^m − 1) = a^{n∧m } − 1  . $$ Des idées.
Merci d'avance.

JLapin

Utilise l'algorithme d'Euclide.

Tu peux commencer par vérifier l'invariance du résultat en remplaçant $(n,m)$ par $\ m,n \pmod m$.

Tyoussef

Apparemment, on a deux  cas.

Cas 1 : Si $n$ divise $m$ ou l'inverse.
Cas 2 : Sinon ???

Réponse, de Cas 1.
Si $n$ divise $m$ , alors  il existe un $k$ dans $Z$ ; tel que $m=kn$
D’où :      \begin{eqnarray*}
a^m - 1 &=& (a^{kn} - 1) \\
 &=& \left( \left( a^{n}\right)^k - 1  \right) \\
 &=& \left( a^n - 1 \right) \left( a^{(k-1)n} +  a^{(k-2)n} + ... + a^{2n} +a^n +1 \right)
\end{eqnarray*}
Donc:  $$  (a^n - 1 ) / (a^m - 1 )  $$ signifie que : $$   (a^n - 1 )   ∧   (a^m - 1 )  =  (a^n - 1 )   =  a^{ n∧m } − 1.$$ Car dans ce cas : $$ m ∧ n=n .$$

Tyoussef

@ JLapin
Je n'arrive pas à vous suivre.
Cordialement.

gerard0

L'algorithme d'Euclide donne le pgcd de deux nombres, ou de deux polynômes. Regarde-le de près.
Cordialement.

JLapin

On note $r$ le reste de la division euclidienne de $n$ par $m$.
Démontre que les diviseurs communs de $a^n-1$ et $a^m-1$ sont exactement les diviseurs communs de $a^m-1$ et $a^r-1$.

Math Coss

Pour préciser l'indication de @gerard0, dans le cas 2, on écrit la division euclidienne $m=kn+r$ avec $0\le r<n$ et on effectue une espèce de factorisation sur $a^{m}-1=a^{kn+r}-a^r+a^r-1$ semblable à celle de ce message.

Une fois qu'on a fini on s'aperçoit qu'il ne sert à rien de considérer le cas 1...

raoul.S

Sans l'algorithme d'Euclide on peut également utiliser le fait qu'il existe deux entiers $k,l$ tels que $kn+lm=pgcd(m,n)$.
Puis $a^{pgcd(m,n)}-1=a^{kn+lm}-1=...$

gebrane

raoul.S a dit :

Sans l'algorithme d'Euclide ...

Tu n'y échappes pas d'Euclide, ce que tu écris vient justement de l'algorithme d'Euclide étendu.

JLapin

Ça peut venir aussi de la description des sous-groupes de $\Z$.

raoul.S

Non gebrane, pas d'algorithme d'Euclide ici. Une division euclidienne pour démontrer que tout idéal de $\Z$ est principal mais pas d'algo.