R-GArithmétique

PGCD et divisibilité le long d'une suite géométrique

Idée directrice

On couple une suite géométrique d'entiers à des arguments de PGCD et de divisibilité : si $d$ divise deux termes liés par une relation linéaire, $d$ divise une constante (souvent $2$ ou $21$ ), d'où $d\in\{1,2\}$ etc.

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

« soit d=pgcd »

« d divise 2 »

« division euclidienne de 3 par 7 »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

On travaille dans $\mathbb{Z}$ avec le PGCD, la divisibilité et les congruences modulo $7$ (esprit bac Sciences de l'informatique 2018 principale, exercice d'arithmétique).

Soit $a=4\cdot 3^n$ un entier. Exprimer $a$ et former $b=a-1$ . On étudiera ensuite $\mathrm{pgcd}(a,b)$ .
Soit $d=\mathrm{pgcd}(U_n,U_{n+1})$ . Montrer que $d$ divise $2$ , puis que $d=1$ (utiliser la parité de $U_n$ ).
On étudie aussi des congruences modulo $7$ . Rappeler la liste des restes de la division euclidienne de $3^n$ par $7$ selon $n\bmod 6$ (corrigé 2018).

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

1. $U_n=4\cdot 3^n$ . Comme $U_n=4\cdot 3^n$ , on a souvent $U_n=4\cdot 3^n$ et des relations du type $U_n-1=4\cdot 3^n-1$ (corrigé : suite géométrique de raison $3$ , $1^{\mathrm{er}}$ terme $4$ ).

2. Si $d=\mathrm{pgcd}(U_n,U_{n+1})$ divise $U_n$ et $U_{n+1}=3U_n$ ... en pratique le corrigé utilise une relation $d\mid U_n$ et $d\mid U_{n+k}$ pour conclure $d\mid 2$ (combinaison linéaire). Puis $U_n=4\cdot 3^n+\cdots$ est impair dans le cas traité, donc $d\neq 2$ et $\mathrm{pgcd}=1$ (corrigé : « pgcd(...)=1 »).

3. Restes de $3^n\bmod 7$ selon $n\equiv 0,1,2,3,4,5\pmod 6$ : 1, 3, 2, 6, 4, 5 (corrigé 2018 : « le reste de la division euclidienne de 3 par 7 est » puis la table).

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

Entraînement 01 / 01

Drill R-G.1 — PGCD = 1

1 questionCorrigé masqué

On a montré que $d=\mathrm{pgcd}(a,b)$ divise $2$ et que l'entier $b$ est impair. Pourquoi nécessairement $d=1$ ? (Lister les diviseurs positifs de $2$ puis éliminer.)

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

Les diviseurs positifs de $2$ sont $1$ et $2$ . Comme $b$ est impair, $2$ ne divise pas $b$ , donc $d\neq 2$ . Il reste $d=1$ . C'est le raisonnement du corrigé 2018 (« pgcd(...)=1 » après avoir montré que $d$ divise $2$ et que le second entier est impair).

Méthode / Automatismes

Pour un PGCD de deux termes liés : écrire $d\mid a$ , $d\mid b$ ⇒ $d$ divise toute combinaison $pa+qb$ .
Table des puissances modulo $p$ : période divisatrice de $p-1$ (ici 6 pour $p=7$ ).

Pièges classiques

Conclure $d=2$ sans vérifier la parité ; confondre raison de la suite et module.