Pgcd a^n -1

Bonjour,
Voici un exercice que j'ai débuté hier. Je ne parviens pas à avancer davantage (et je suis consciente de ne pas avoir fait grand chose...)

Voici l'énoncé:
Soit un entier $a$ non nul et $m, n$ des entiers positifs. Montrer que
$pgcd (a^m -1, a^n -1)= a^pgcd(m,n) -1$

J'ai commencé à répondre comme ceci:
Si m=n, alors $p g c d (m, n) = m = n$ et $a^m -1 = a^n -1$ .
$pgcd(a^m -1, a^n -1) = a^m -1 =a^n -1 = a^pgcd(m,n) -1$

Ce résultat est évident (j'ai seulement l'impression d'essayer de noyer le poisson...)

On suppose à présent que m ≠n et on pose $p g c d (m, n) = d$ .
$d$ divise donc m et n et on peut écrire $m = d b$ et $n = d c, b$ et $c$ deux entiers .
On veut montrer que $a^d -1$ divise $a^{dc}$ -1 et $a^{bc}$ -1 (et qu'il s'agit de leur plus grand diviseur commun).

Là, je ne sais pas quel chemin emprunter. Faut-il factoriser $a^{dc}$ -1 et $a^{bc}$ -1 afin de mettre en valeur $a^d -1$ ?
J'ai trouvé hier à la BU un exercice semblable mais sa résolution ne me satisfait pas. Elle faisait intervenir des suites, je crois...

Qu'en pensez vous? (je suis presque gênée de demander de l'aide, un lycéen pourrait faire mieux que moi, là...)
Merci d'avance,
Bon après midi,
Aïda

Correction: je précise qu'il s'agit de a $^{ pgcd(m,n)}$ -1, et que -1 n'est pas en "exposant"

Bonjour,
Pour a = 1, le résultat est évident et sans intérêt.
Tu l'as établi pour m = n.
Plus généralement, c'est évident aussi si m|n ( ou le contraire).
Commence par établir le résultat général suivant :
Si k|h alors $a^k$ -1| $a^h$ -1

Faut pas abandonner.
Je t'aide :
si k|h, il existe un entier q tel que h = kq
De plus, $a^h$ ≡ 1 modulo $a^h$ -1 (évident par définition)
Donc ...

Bonsoir Mathtous,
Merci de m'avoir répondu!
Je viens de penser à quelque chose:

Si k l h, il existe un entier q tel que h=kq
$a^k$ ≡1 $a^k$ -1]
D'où, $(a$ ^k $^q$ ≡ $1^q$ $a^k$ -1]
c'est à dire $a^h$ ≡1 $a^k$ -1]
qu'on peut écrire : $a^h$ -1 $n(a^k$ -1), n un entier.
Si klh alors $a^k$ -1 divise $a^h$ -1

Bien, je ne sais absolument pas si j'ai le droit de faire ça. Ca fait quatre ans que je n'ai pas touché aux congruences, j'ai surement oublié plein de choses...
En tous cas, merci,
Bonne soirée,
Aïda

Bonjour,
Oui.
On a donc le résultat : pour tout entier a (on peut exclure 0 si ça te gêne), pour tout entier k et pour tout entier h positifs, tels que k|h, alors $a^k$ -1 divise $a^h$ -1.
Ce résultat est tellement important que tu peux l'ériger en théorème.

Ensuite, fais appel à la propriété de Bachet (Bézout) pour traduire que d est le PGCD de m et n.

Bonsoir mathtous,
Merci de m'avoir répondu.
Bien, je pense que je me souviendrai de ce résultat.
Par contre je ne comprends pas trop comment me servir du théorème de Bezout.
Il est dit:
Citation
Pour que deux entiers relatifs a et b soient premiers entre eux, il faut et il suffit qu'il existe deux entiers relatifs x et y tel que:
ax+by=1
Mais je ne veux pas montrer que $a^m$ -1 et $a^n$ -1 sont premiers entre eux... ?
Bonne soirée

Bonsoir mathtous,
Merci de m'avoir répondu.
Bien, je pense que je me souviendrai de ce résultat.
Par contre je ne comprends pas trop comment me servir du théorème de Bezout.
Il est dit:
Citation
Pour que deux entiers relatifs a et b soient premiers entre eux, il faut et il suffit qu'il existe deux entiers relatifs x et y tel que:
ax+by=1
Mais je ne veux pas montrer que $a^m$ -1 et $a^n$ -1 sont premiers entre eux... ?
Bonne soirée

Bonjour,
Le théorème est plus général :

Si d est le PGCD de a et b, il existe deux entiers x et y tels que
ax+by = d
De façon plus précise : si a et b sont des entiers positifs, il existe deux entiers positifs x et y tels que ax - by = d
La réciproque est fausse sauf si on précise ceci :
Si ax + by = d et que d est un diviseur de a et b, alors c'est leur PGCD.

Utilise le th direct pour m et n, puis tu chercheras ensuite à utiliser la réciproque pour $a^m$ -1 et $a^n$ -1

Bonjour,
Merci de m'avoir indiqué le théorème, j'avais oublié cette version ci.
Je cherche encore à exprimer $a^d$ -1 en fonction de $a^m$ -1 et $a^n$ -1, sachant que $a$ ^d $- 1 = a$ ^{mx-ny} $- 1 = a$ ^{mx} $a^{ny}$ -1.
Je finirai bien par trouver...
Merci encore,
Aïda

Evite les quotients : tu n'aurais plus des nombres entiers.
Sinon, j'ai rédigé une solution ICI.
Clique sur le lien bleu (ICI).

Oh! je n'avais pas pensé à ça! je vais attendre un peu avant de refaire l'exercice, histoire d'oublier un peu la solution...
Merci vraiment pour votre aide (à ce propos, j'aime beaucoup votre site, je pense que j'en imprimerai quelques pages afin de redévelopper mes réflexes et ma logique, ca peut aider).
Bonne soirée
Aïda

Oui, fais attention à n'avoir que des entiers positifs, d'où le remplacement de la soustraction par une addition (équivalente).
Bonne soirée.
A+

D'accord, j'y penserai.
Bonne soirée,
Aïda

Bonne soirée.