PGCD en math Expert

[Gege29]

Bonjour,
J'ai un devoir à rendre pour la rentrée sur les PGCD et je sèche complètement depuis plusieurs jours. Quelqu'un pourrait-il m'aider svp ? Merci d'avance.
Voici l'exercice :
On considère les nombres entiers naturels a=n(2n+1) et b=n-1 où n désigne un entier naturel >= 2.
1- En discutant suivant le reste dans la division euclidienne par 3 de l'entier , montrer que :
a est un multiple de 3 si et seulement si n congru à 0 modulo 3 ou n congru à 1 modulo 3.
2- Montrer que d = a^b est un diviseur de 3
3- A quelle condition sur n, a et b sont-ils tous les deux des multiples de 3 ? Déterminer alors suivant les valeurs de n, la valeur de d.
4- Application numérique : déterminer, en utilisant l'étude précédente, le nombre :
d = 2 puissance 1000 (2 puissance 1001 + 1) ^2 puissance 1000 - 1

[Rdvn]

Le 1) c'est vraiment facile : modulo 3, n est congru à 0 ou 1 ou 2 , dans chaque cas on peut voir facilement à quoi sont congrus 2n+1 puis n(2n+1)
Le2) c'est un peu plus difficile :
on utilise la propriété ( pour u,v entiers non nuls , k entier relatif)
PGCD(u,v) = PGCD (v, u-kv)

ici PGCD(a,b) = PGCD(2n^2+n , n-1)= PGCD( n-1, 2n^2+n-2n(n-1) ) = PGCD(n-1,3n)
(on « élimine » n^2)
Selon ce modèle montrez PGCD(n-1,3n) =PGCD(n-1,3)
Puis on verra la suite
A vous

[Gege29]

Bonjour,
Merci beaucoup pour ce début de réponse.
J'avais réussi à faire le 1) aussi.
Pour le 2) je n'ai pas cette propriété dans mon cours. Elle porte un nom ?
Je ne vois pas trop non plus comment passer de PGCD(n-1,3n) à PGCD(n-1,3).
J'arrive à faire le 3) : n doit être congru à 1 modulo 3 pour que a et b soient multiples de 3 et d vaut soit 3 dans ce cas, soit 1 sinon.

[catamat]

Bonjour

La propriété utilisée est que le pgcd de deux nombres a et b divise toute combinaison linéaire de a et de b.

donc d divise a-2nb soit 3n

puis d divise toute combinaison linéaire de b et 3n.....

[Gege29]

Merci encore.
Pour le 4) c'est assez facile aussi. 2^k n'est jamais congru à 0 modulo 3 (pas multiple de3 forcément). Il est congru à 1 pour les puissances impaires et à 3 pour les puissances paires. Donc pour n=2^1000 d vaudra 3.
J'ai un autre exercice du même genre sur les PGCD. Si je me trouve bloqué, je ferai un autre messge.
En tout cas, merci pour l'aide !

[Rdvn]

Je n'ai pas souvenir que la propriété utilisée porte un nom particulier , mais elle est classique et
très utile. Si vous avez un livre de terminale spécialité, cela doit s'y trouver .

Deuxième exemple puisque vous manquez de cours à ce sujet : fin de la question
PGCD(n-1,3n) = PGCD(n-1,3n – 3(n-1)) = PGCD(n-1,3n-3n+3) = PGCD(n-1,3)
(on « élimine » n dans un des deux termes)

Le reste de votre raisonnement est correct pour la première réponse
Pour la deuxième c'est à reprendre :
Montrez 2^1000 = 1 [mod 3]
Par exemple 2^1000 = ( 2^2)^500
A vous

[Gege29]

Je pensais faire par récurrence .
Supposons : 2^k=2[3]
On a : 2^(k+1)=2x2^k=4[3]=1[3]
Et : 2^(k+2)=2x2x2^k=2[3] etc.
Or : 2^1=2[3]
Donc : 2^2=1[3], 2^3=2[3] etc.
Par récurrence, les puissances paires de k sont congrues à 1 [3]
1000 est paire donc 2^1000=1[3].
D'après 3) pour n=1[3] a et b sont multiples de 3 donc d=a^b=3

[Rdvn]

La récurrence me semble inutilement compliquée ici

Si k est pair , k = 2h et donc

2^k = 2^2h = (2^2)^h = 4^h = 1^h = 1 [mod 3 ]
Plus simple, non ?
A vous

[Gege29]

Oui en effet.