Un pgcd

Tyoussef · April 2023

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 · April 2023

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 · April 2023

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 · April 2023

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

gerard0 · April 2023

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

JLapin · April 2023

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 · April 2023

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 · April 2023

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=...$