R-HArithmétique

Congruences et PGCD le long d'une relation 5^n − 4y = 21

Idée directrice

Une relation du type $5^n-4y_n=21$ permet, par récurrence, de contrôler un PGCD : tout diviseur commun divise $21$ , puis des congruences modulo $7$ affinent la valeur exacte du PGCD.

Signature de reconnaissance — l'énoncé se trahit ainsi

« d' divise 21 »

« pgcd = 7 »

« pour tout n … = 21 »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

On admet (ou on montre par récurrence) que pour tout $n\in\mathbb{N}$ , $5^n-4y_n=21$ pour une suite d'entiers $(y_n)$ . Soit $d'=\mathrm{pgcd}(5^n,y_n)$ . Montrer que $d'$ divise $21$ .
En déduire la liste des valeurs possibles pour $d'$ .
Dans le cas $n\equiv 5\pmod 6$ , le corrigé conclut $\mathrm{pgcd}=7$ . Quelle obstruction élimine $3$ et $21$ ?

Voir la correction commentéeAprès avoir posé votre démarche

1. $d'\mid 5^n$ et $d'\mid y_n$ ⇒ $d'\mid (5^n-4y_n)$ soit $d'\mid 21$ (corrigé : « d' divise 5−4y donc d' divise 21 »).

2. Diviseurs positifs de $21$ : $d'\in\{1,3,7,21\}$ .

3. Ni $5^n$ ni $y_n$ n'est divisible par $3$ dans ce cas, donc $d'\notin\{3,21\}$ . Avec les congruences modulo $7$ du corrigé, il reste $d'=7$ (corrigé : « pgcd = 7 »).

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 01

Drill R-H.1 — Candidats du PGCD

1 questionCorrigé masqué

Si $d=\mathrm{pgcd}(a,b)$ divise $21$ , lister les valeurs positives possibles de $d$ . Si de plus $3$ ne divise ni $a$ ni $b$ , quelles valeurs restent-elles pour ce PGCD ?

Voir la correction commentéeAprès avoir posé votre démarche

Valeurs : $1,3,7,21$ . Si $3$ ne divise ni $a$ ni $b$ , on élimine $3$ et $21$ : il reste $1$ ou $7$ . C'est exactement le filtre du corrigé 2018 avant le raffinement par congruence modulo $7$ (« d' ∈ 1,3,7,21 » puis exclusion des multiples de $3$ ).

Méthode / Automatismes

Relation linéaire + PGCD ⇒ le PGCD divise le second membre constant.
Affiner avec des congruences pour éliminer les candidats.

Pièges classiques

Oublier d'exclure $3$ et $21$ ; confondre $d'\mid 21$ et $d'=21$ .