ATLAS Ouvrir dans l'atlas →

ExerciceMaths Sup – MPSI, chapitre 12 — Arithmétique dans ℤ\mathbb{Z} · PGCD, PPCM et relation de Bézout

Exercice 10

Calcul

Pour n∈ℕn \in \mathbb{N}, on pose un=n2+1u_{n} = n^{2} + 1. Déterminer, selon les valeurs de nn, le PGCD de deux termes consécutifs un∧un+1u_{n} \wedge u_{n + 1}.

Corrigé

Soit d=un∧un+1d = u_{n} \wedge u_{n + 1}. Il divise un+1−un=2n+1u_{n + 1} - u_{n} = 2n + 1, puis 4un−(2n+1)(2n−1)=4n2+4−(4n2−1)=5.4u_{n} - (2n + 1)(2n - 1) = 4n^{2} + 4 - (4n^{2} - 1) = 5. Donc d∈{1,5}d \in \{1, 5\}. On cherche quand 55 divise les deux termes. Les carrés modulo 55 valent 0,1,4,4,10, 1, 4, 4, 1 pour n≡0,1,2,3,4n \equiv 0, 1, 2, 3, 4, donc 5∣n2+15 \mid n^{2} + 1 si et seulement si n≡2n \equiv 2 ou 3  [5]3 \;[5], et 5∣(n+1)2+15 \mid (n + 1)^{2} + 1 si et seulement si n≡1n \equiv 1 ou 2  [5]2 \;[5]. un∧un+1=5 si n≡2  [5],1 sinon\boxed{u_{n} \wedge u_{n + 1} = 5 \text{ si } n \equiv 2 \;[5], \quad 1 \text{ sinon}} Vérification : u2∧u3=5∧10=5u_{2} \wedge u_{3} = 5 \wedge 10 = 5, et u7∧u8=50∧65=5u_{7} \wedge u_{8} = 50 \wedge 65 = 5. ✓

Dans l'édifice

Thèmes

pgcd et bézout, pgcd et algorithme d'euclide

Notions

PGCD

Ouvrir dans l'atlas interactif →