Exercices : Arithmétique

Correction :

Pour montrer que $368$ et $117$ sont premiers entre eux, nous allons utiliser l'algorithme d'Euclide.

Étape 1: Division euclidienne de $368$ par $117$. $$368 = 117 \times 3 + 17$$ Le reste est $17$.

Étape 2: Division euclidienne de $117$ par $17$. $$117 = 17 \times 6 + 15$$ Le reste est $15$.

Étape 3: Division euclidienne de $17$ par $15$. $$17 = 15 \times 1 + 2$$ Le reste est $2$.

Étape 4: Division euclidienne de $15$ par $2$. $$15 = 2 \times 7 + 1$$ Le reste est $1$.

Étape 5: Division euclidienne de $2$ par $1$. $$2 = 1 \times 2 + 0$$ Le dernier reste non nul est $1$. Donc, ${\rm PGCD}(368, 117) = 1$. Ainsi, $368$ et $117$ sont premiers entre eux.

Maintenant, pour trouver les coefficients de Bézout $u$ et $v$ tels que $368u + 117v = 1$, nous allons utiliser l'algorithme d'Euclide étendu en remontant les égalités :

À partir de l'étape 4 : $$1 = 15 - 2 \times 7$$

À partir de l'étape 3, on exprime $2 = 17 - 15 \times 1$ et on le substitue dans l'équation précédente : $$1 = 15 - (17 - 15 \times 1) \times 7 = 15 - 17 \times 7 + 15 \times 7 = 15 \times 8 - 17 \times 7$$

À partir de l'étape 2, on exprime $15 = 117 - 17 \times 6$ et on le substitue dans l'équation précédente : $$1 = (117 - 17 \times 6) \times 8 - 17 \times 7 = 117 \times 8 - 17 \times 48 - 17 \times 7 = 117 \times 8 - 17 \times 55$$

À partir de l'étape 1, on exprime $17 = 368 - 117 \times 3$ et on le substitue dans l'équation précédente : $$1 = 117 \times 8 - (368 - 117 \times 3) \times 55 = 117 \times 8 - 368 \times 55 + 117 \times 165 = 117 \times (8 + 165) - 368 \times 55$$ $$1 = 117 \times 173 - 368 \times 55$$

En réarrangeant pour avoir la forme $368u + 117v = 1$, on obtient : $$368 \times (-55) + 117 \times 173 = 1$$

Donc, on a $u = -55$ et $v = 173$.

Conclusion : Nous avons montré que ${\rm PGCD}(368, 117) = 1$, donc $368$ et $117$ sont premiers entre eux. De plus, nous avons trouvé $u = -55$ et $v = 173$ tels que $368u + 117v = 1$.

Correction :

1. Montrons que si $a$ et $b^2$ sont premiers entre eux alors $a$ et $b$ sont premiers entre eux.

Si $a$ et $b^2$ sont premiers entre eux, alors d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que : $$au + b^2v = 1$$ Nous devons montrer que $a$ et $b$ sont premiers entre eux, c'est-à-dire qu'il existe des entiers $u'$ et $v'$ tels que $au' + bv' = 1$. Observons l'équation de Bézout pour $a$ et $b^2$: $au + b^2v = 1$. On peut réécrire $b^2v$ comme $b \times (bv)$. Posons $v' = v$ et $u' = u$. Ce n'est pas directement de la forme souhaitée, mais l'équation de Bézout pour $a$ et $b^2$ implique une relation forte entre $a$ et $b$.

Supposons par l'absurde que $a$ et $b$ ne soient pas premiers entre eux. Alors, il existe un diviseur commun $d > 1$ à $a$ et $b$. Si $d$ divise $b$, alors $d$ divise $b^2$. Puisque $d$ divise aussi $a$, $d$ est un diviseur commun à $a$ et $b^2$. Si $a$ et $b^2$ sont premiers entre eux, leur seul diviseur commun positif est $1$. Donc, si $a$ et $b^2$ sont premiers entre eux, alors $a$ et $b$ ne peuvent pas avoir de diviseur commun $d > 1$. Par conséquent, $a$ et $b$ sont premiers entre eux.

Autre méthode (plus directe avec Bézout) : Partons de $au + b^2v = 1$. On veut "faire apparaître" $b$ au lieu de $b^2$. Si on suppose que $a$ et $b^2$ sont premiers entre eux, on a $au + b^2v = 1$. Supposons que $a$ et $b$ ne soient pas premiers entre eux. Alors ils ont un diviseur commun $d > 1$. Donc $d|a$ et $d|b$. Si $d|b$, alors $d|b^2$. Donc $d$ divise $au$ et $b^2v$, donc $d$ divise $au + b^2v = 1$. Donc $d|1$, ce qui implique $d=1$. Contradiction avec $d > 1$. Donc $a$ et $b$ sont premiers entre eux.

2. Montrons que réciproquement, si $a$ et $b$ sont premiers entre eux alors $a$ et $b^2$ sont premiers entre eux.

Si $a$ et $b$ sont premiers entre eux, alors d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que : $$au + bv = 1$$ Pour montrer que $a$ et $b^2$ sont premiers entre eux, nous devons montrer qu'il existe des entiers $u'$ et $v'$ tels que $au' + b^2v' = 1$. Partons de l'équation de Bézout pour $a$ et $b$: $au + bv = 1$. Élevons au carré les deux membres de cette équation : $$(au + bv)^2 = 1^2$$ $$(au)^2 + 2(au)(bv) + (bv)^2 = 1$$ $$a^2u^2 + 2aubv + b^2v^2 = 1$$ $$a(au^2 + 2ubv) + b^2v^2 = 1$$ Posons $u' = au^2 + 2ubv$ et $v' = v^2$. Alors on a : $$au' + b^2v' = 1$$ Puisque nous avons trouvé des entiers $u'$ et $v'$ tels que $au' + b^2v' = 1$, d'après le théorème de Bézout, $a$ et $b^2$ sont premiers entre eux.

Conclusion : Nous avons démontré les deux implications à l'aide du théorème de Bézout.

Correction :

Pour montrer que $2n^2 + 10n + 13$ et $n+3$ sont premiers entre eux, nous allons utiliser le théorème de Bézout ou montrer que leur PGCD est 1. Utilisons les propriétés du PGCD et des combinaisons linéaires.

Soit $d = {\rm PGCD}(2n^2 + 10n + 13, n+3)$. Alors $d$ divise $2n^2 + 10n + 13$ et $d$ divise $n+3$. Si $d$ divise $n+3$, alors $d$ divise aussi tout multiple de $n+3$. En particulier, $d$ divise $2n(n+3) = 2n^2 + 6n$. Puisque $d$ divise $2n^2 + 10n + 13$ et $2n^2 + 6n$, $d$ divise leur différence : $$(2n^2 + 10n + 13) - (2n^2 + 6n) = 4n + 13$$ Donc, $d$ divise $4n + 13$. On sait aussi que $d$ divise $n+3$. Si $d$ divise $n+3$, alors $d$ divise $4(n+3) = 4n + 12$. Puisque $d$ divise $4n + 13$ et $4n + 12$, $d$ divise leur différence : $$(4n + 13) - (4n + 12) = 1$$ Donc, $d$ divise $1$. Comme $d$ est un entier positif qui divise $1$, on a $d = 1$. Par conséquent, ${\rm PGCD}(2n^2 + 10n + 13, n+3) = 1$.

Conclusion : Pour tout entier $n$, les entiers $2n^2 + 10n + 13$ et $n+3$ sont premiers entre eux.

Correction :

Nous voulons déterminer ${\rm PGCD}(n^2+n, 2n+1)$.

Méthode 1: Chercher les coefficients dans l'égalité de Bézout

On cherche $u(n)$ et $v(n)$ tels que $(n^2+n)u(n) + (2n+1)v(n) = {\rm PGCD}(n^2+n, 2n+1)$. Essayons d'obtenir une constante à droite. Multiplions $n^2+n$ par $2$ et $2n+1$ par $-n/2 + ...$ pour éliminer les termes en $n^2$. C'est plus simple d'éliminer $n^2$ en multipliant $(2n+1)$ par quelque chose.

Multiplions $(2n+1)$ par $-\frac{n}{2}$: $-\frac{n}{2}(2n+1) = -n^2 - \frac{n}{2}$. Alors $(n^2+n) + (-\frac{n}{2})(2n+1) = n^2+n - n^2 - \frac{n}{2} = \frac{n}{2}$. Cela ne donne pas un entier coefficient. Essayons de multiplier par un entier. Multiplions $(2n+1)$ par $-n$: $-n(2n+1) = -2n^2 - n$. Alors $2(n^2+n) + (-n)(2n+1) = 2n^2+2n - 2n^2 - n = n$. On a donc : $$2(n^2+n) - n(2n+1) = n$$ Maintenant, multiplions $(2n+1)$ par $-\frac{1}{2}$: $-\frac{1}{2}(2n+1) = -n - \frac{1}{2}$. Alors $(n^2+n) + (-\frac{n}{2} + \frac{1}{4})(2n+1) = n^2+n + (-\frac{n}{2} + \frac{1}{4})(2n+1) = n^2+n -n^2 - \frac{n}{2} + \frac{n}{2} + \frac{1}{4} = \frac{1}{4}$. En multipliant par $4$: $$4(n^2+n) + ( -2n + 1)(2n+1) = 1$$ Vérification : $4(n^2+n) + (-2n+1)(2n+1) = 4n^2+4n + (-4n^2 - 2n + 2n + 1) = 4n^2+4n - 4n^2 + 1 = 4n+1$. Erreur de calcul.

Refaisons le calcul : $4(n^2+n) + (-2n+1)(2n+1) = 4n^2+4n -4n^2 -2n + 2n + 1 = 4n+1$. Non, toujours faux.

Recommençons : On veut éliminer $n^2$. On a $n^2+n$ et $2n+1$. Multiplions $(n^2+n)$ par $2$ et $(2n+1)$ par $-n$. $$2(n^2+n) - n(2n+1) = 2n^2+2n - (2n^2+n) = n$$ Donc $2(n^2+n) + (-n)(2n+1) = n$. Maintenant, on veut éliminer $n$. On a $n$ et $2n+1$. Multiplions $n$ par $2$ et $(2n+1)$ par $-1$. $2(n) - 1(2n+1) = 2n - 2n - 1 = -1$. Donc $2(n) - 1(2n+1) = -1$. Multiplions par $-1$: $-2(n) + 1(2n+1) = 1$. Substituons $n = 2(n^2+n) - n(2n+1)$ dans $-2(n) + 1(2n+1) = 1$. $$-2[2(n^2+n) - n(2n+1)] + 1(2n+1) = 1$$ $$-4(n^2+n) + 2n(2n+1) + 1(2n+1) = 1$$ $$-4(n^2+n) + (2n+1)(2n+1) = 1$$ $$-4(n^2+n) + (2n+1)^2 = 1$$ Donc $(2n+1)^2 - 4(n^2+n) = 1$. On a trouvé des coefficients de Bézout $u = -4$ et $v = (2n+1)$. Non, $u = -4$ et $v = (2n+1)$. Non plus. Reprenons : $-4(n^2+n) + (2n+1)(2n+1) = 1$. Ici $a = n^2+n$, $b = 2n+1$. On a $u = -4$ (constant) et $v = 2n+1$ (dépendant de $n$). Non, $v = 2n+1$ est faux. C'est $(2n+1)$ qui est multiplié par $(2n+1)$. Donc $u = -4$ et le coefficient de $(2n+1)$ est $(2n+1)$. Donc $v = 2n+1$. Non, c'est $v = 2n+1$. Non. Reprenons. $$-4(n^2+n) + (2n+1)(2n+1) = 1$$ $$-4(n^2+n) + (2n+1)^2 = 1$$ On cherche $u$ et $v$ tels que $(n^2+n)u + (2n+1)v = 1$. Ici, on a $(n^2+n)(-4) + (2n+1)(2n+1) = 1$. Donc $u = -4$ et $v = 2n+1$. Ces sont les coefficients de Bézout. Puisqu'on a trouvé une combinaison linéaire de $n^2+n$ et $2n+1$ qui est égale à $1$, alors ${\rm PGCD}(n^2+n, 2n+1) = 1$. Le PGCD est $1$. Il ne dépend pas de $n$.

Méthode 2: A l'aide d'une division euclidienne

On divise $n^2+n$ par $2n+1$. Pour diviser des polynômes, on peut procéder comme la division euclidienne des entiers. $$n^2+n = (2n+1) \times Q(n) + R(n)$$ On cherche $Q(n)$ et $R(n)$. Pour avoir $n^2$, on multiplie $2n+1$ par $\frac{n}{2}$. $\frac{n}{2}(2n+1) = n^2 + \frac{n}{2}$. $$(n^2+n) - \frac{n}{2}(2n+1) = n^2+n - n^2 - \frac{n}{2} = \frac{n}{2}$$ Donc $n^2+n = \frac{n}{2}(2n+1) + \frac{n}{2}$. Les coefficients ne sont pas entiers. On doit avoir des coefficients entiers. Multiplions $n^2+n$ par $2$: $2(n^2+n) = 2n^2+2n$. Divisons $2n^2+2n$ par $2n+1$. Pour avoir $2n^2$, on multiplie $2n+1$ par $n$. $n(2n+1) = 2n^2+n$. $$(2n^2+2n) - n(2n+1) = 2n^2+2n - 2n^2 - n = n$$ Donc $2(n^2+n) = n(2n+1) + n$. On continue la division avec $2n+1$ et $n$. $$2n+1 = n \times 2 + 1$$ Le reste est $1$. Le dernier reste non nul est $1$. Donc ${\rm PGCD}(2n+1, n) = 1$. Et ${\rm PGCD}(n, 1) = 1$. Et ${\rm PGCD}(1, 0) = 1$. En remontant : ${\rm PGCD}(2(n^2+n), 2n+1) = {\rm PGCD}(2n+1, n) = {\rm PGCD}(n, 1) = 1$. ${\rm PGCD}(2(n^2+n), 2n+1) = 1$. Est-ce que ${\rm PGCD}(n^2+n, 2n+1) = 1$? Oui, car ${\rm PGCD}(ka, b) = {\rm PGCD}(a, b)$ si ${\rm PGCD}(k, b) = 1$. Ici $k = 2$, $a = n^2+n$, $b = 2n+1$. Est-ce que ${\rm PGCD}(2, 2n+1) = 1$? Oui, car $2n+1$ est impair, donc n'est pas divisible par $2$. Donc ${\rm PGCD}(2, 2n+1) = 1$. Donc ${\rm PGCD}(2(n^2+n), 2n+1) = {\rm PGCD}(n^2+n, 2n+1) = 1$.

Méthode 3: A l'aide des propriétés du PGCD

On utilise la propriété ${\rm PGCD}(a, b) = {\rm PGCD}(a, b - ka)$. ${\rm PGCD}(n^2+n, 2n+1) = {\rm PGCD}(n^2+n - \frac{n}{2}(2n+1), 2n+1) = {\rm PGCD}(\frac{n}{2}, 2n+1)$. Non, on doit avoir des coefficients entiers. ${\rm PGCD}(n^2+n, 2n+1) = {\rm PGCD}(n^2+n - \frac{n}{2}(2n+1), 2n+1) = {\rm PGCD}(\frac{n}{2}, 2n+1)$. Pas bon. ${\rm PGCD}(n^2+n, 2n+1) = {\rm PGCD}(2(n^2+n), 2n+1) = {\rm PGCD}(2n^2+2n, 2n+1)$. ${\rm PGCD}(2n^2+2n, 2n+1) = {\rm PGCD}(2n^2+2n - n(2n+1), 2n+1) = {\rm PGCD}(2n^2+2n - 2n^2 - n, 2n+1) = {\rm PGCD}(n, 2n+1)$. ${\rm PGCD}(n, 2n+1) = {\rm PGCD}(n, (2n+1) - 2n) = {\rm PGCD}(n, 1) = 1$.

Conclusion : Par les trois méthodes, on trouve que ${\rm PGCD}(n^2+n, 2n+1) = 1$.

Correction :

1. Démontrer que $a$ admet un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux.

Sens $\Rightarrow$ : Supposons que $a$ admet un inverse modulo $n$. Alors, il existe un entier $b$ tel que $ab \equiv 1 \pmod{n}$. Par définition de la congruence, cela signifie que $ab - 1$ est un multiple de $n$. Donc il existe un entier $k$ tel que $ab - 1 = kn$, ce qui peut s'écrire $ab - kn = 1$, ou encore $ab + n(-k) = 1$. Posons $u = b$ et $v = -k$. Alors on a $au + nv = 1$, où $u$ et $v$ sont des entiers. D'après le théorème de Bézout, si il existe des entiers $u$ et $v$ tels que $au + nv = 1$, alors $a$ et $n$ sont premiers entre eux.

Sens $\Leftarrow$ : Supposons que $a$ et $n$ sont premiers entre eux. D'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + nv = 1$. Considérons cette égalité modulo $n$. $$au + nv \equiv 1 \pmod{n}$$ Puisque $nv \equiv 0 \pmod{n}$ (car $nv$ est un multiple de $n$), on a : $$au \equiv 1 \pmod{n}$$ Cela signifie que $u$ est un inverse de $a$ modulo $n$. Donc, $a$ admet un inverse modulo $n$.

Conclusion de la question 1 : Nous avons démontré les deux implications, donc $a$ admet un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux.

2. Application:

a) 7 admet-il un inverse modulo 22? Dans l'affirmative, en donner un.

Pour savoir si $7$ admet un inverse modulo $22$, nous devons vérifier si $7$ et $22$ sont premiers entre eux. Calculons ${\rm PGCD}(7, 22)$ avec l'algorithme d'Euclide. $$22 = 7 \times 3 + 1$$ $$7 = 1 \times 7 + 0$$ Le dernier reste non nul est $1$, donc ${\rm PGCD}(7, 22) = 1$. Ainsi, $7$ et $22$ sont premiers entre eux, et $7$ admet un inverse modulo $22$. Pour trouver un inverse, nous utilisons l'égalité de Bézout obtenue lors de l'algorithme d'Euclide. De la première étape, on a : $$1 = 22 - 7 \times 3$$ $$1 = 22 + 7 \times (-3)$$ En considérant cette égalité modulo $22$, on a : $$1 \equiv 22 + 7 \times (-3) \pmod{22}$$ $$1 \equiv 0 + 7 \times (-3) \pmod{22}$$ $$1 \equiv 7 \times (-3) \pmod{22}$$ Donc $-3$ est un inverse de $7$ modulo $22$. On cherche un inverse positif. $-3 \equiv -3 + 22 \equiv 19 \pmod{22}$. Donc $19$ est aussi un inverse de $7$ modulo $22$. Vérification : $7 \times 19 = 133 = 6 \times 22 + 1$, donc $7 \times 19 \equiv 1 \pmod{22}$.

Réponse a) : Oui, 7 admet un inverse modulo 22, et un inverse est $19$ (ou $-3$, ou $19 + 22k$ pour tout entier $k$).

b) Résoudre $7x \equiv 5 \pmod{22}$.

Nous avons trouvé qu'un inverse de $7$ modulo $22$ est $19$. Pour résoudre $7x \equiv 5 \pmod{22}$, nous multiplions les deux membres de la congruence par l'inverse de $7$, qui est $19$: $$19 \times (7x) \equiv 19 \times 5 \pmod{22}$$ $$(19 \times 7)x \equiv 95 \pmod{22}$$ Puisque $19 \times 7 \equiv 1 \pmod{22}$, on a : $$1 \times x \equiv 95 \pmod{22}$$ $$x \equiv 95 \pmod{22}$$ Réduisons $95$ modulo $22$. $95 = 4 \times 22 + 7$. Donc $95 \equiv 7 \pmod{22}$. $$x \equiv 7 \pmod{22}$$ Les solutions sont tous les entiers $x$ de la forme $x = 7 + 22k$, où $k$ est un entier relatif.

Réponse b) : Les solutions de $7x \equiv 5 \pmod{22}$ sont les entiers $x \equiv 7 \pmod{22}$.

Correction :

1. ($\Rightarrow$) Si $a$ est inversible modulo $n$,

   alors il existe un entier $b$ tel que $ab \equiv 1 \pmod{n}$.

   Cela signifie qu'il existe un entier $k$ tel que $ab - 1 = kn$,

   ou encore, $ab - kn = 1$.

   D'après le théorème de Bézout, $\text{PGCD}(a, n) = 1$.

   ($\Leftarrow$) Si $\text{PGCD}(a, n) = 1$,

   alors, d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + nv = 1$.

   En réduisant modulo $n$, cette équation devient $au \equiv 1 \pmod{n}$.

   Donc $a$ est inversible modulo $n$, et $u$ est un inverse de $a$ modulo $n$.

2. Existence : Comme $a$ est inversible modulo $n$,

   il existe un entier $b$ tel que $ab \equiv 1 \pmod{n}$.

   Par division euclidienne de $b$ par $n$, on a $b = qn + r$ avec $0 \le r < n$.

   Alors $ab \equiv a(qn + r) \equiv ar \equiv 1 \pmod{n}$.

   Si $r = 0$, alors $ar \equiv 0 \not\equiv 1 \pmod{n}$ (car $n > 1$),

   donc $1 \le r \le n-1$.

   Unicité : Supposons qu'il existe deux inverses $r_1$ et $r_2$ tels que :

   $ar_1 \equiv ar_2 \equiv 1 \pmod{n}$ avec $1 \le r_1, r_2 \le n-1$.

   Alors $a(r_1 - r_2) \equiv 0 \pmod{n}$.

   Puisque $\text{PGCD}(a, n) = 1$ et que $n$ divise $a(r_1 - r_2)$,

   alors, d'après le lemme de Gauss, $n$ divise $r_1 - r_2$.

   Or, $-(n-2) \le r_1 - r_2 \le n-2$.

   Le seul multiple de $n$ dans cet intervalle est $0$.

   Donc $r_1 - r_2 = 0$, et par conséquent, $r_1 = r_2$.

3. $\text{PGCD}(15, 26) = 1$ (on peut utiliser l'algorithme d'Euclide pour le vérifier).

   Donc $15$ est inversible modulo $26$.

   En remontant l'algorithme d'Euclide, on trouve $15 \cdot 7 - 4 \cdot 26 = 1$,

   donc $15 \cdot 7 \equiv 1 \pmod{26}$.

   L'inverse de $15$ modulo $26$ est $7$.

   $\text{PGCD}(8, 26) = 2 > 1$,

   donc $8$ n'est pas inversible modulo $26$.

Correction :

1. Théorème de Bézout : $a$ et $b$ sont premiers entre eux ($\text{PGCD}(a,b)=1$)

   si et seulement s'il existe des entiers $u$ et $v$ tels que $au + bv = 1$.

2. 1. En développant le membre de droite de l'égalité, on obtient $(au+bv)^2$.

   2. Si $\text{PGCD}(a, b) = 1$,

      alors, d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + bv = 1$.

      Alors $(au+bv)^2 = 1$.

      En utilisant l'identité de la question (a), on a :

      $(a+b)(au^2 + bv^2) + ab(2uv - u^2 - v^2) = 1$.

      Posons $U = au^2 + bv^2$ et $V = 2uv - u^2 - v^2$.

      Alors $(a+b)U + (ab)V = 1$.

      D'après le théorème de Bézout, $\text{PGCD}(a+b, ab) = 1$.

3. Si $\text{PGCD}(a+b, ab) = 1$,

   alors, d'après le théorème de Bézout, il existe des entiers $U$ et $V$ tels que $(a+b)U + (ab)V = 1$.

   Donc $a(U+bV) + bU = 1$.

   Posons $u = U+bV$ et $v = U$.

   Alors $au + bv = 1$,

   et, d'après le théorème de Bézout, $\text{PGCD}(a, b) = 1$.

Correction :

Posons $d = \text{PGCD}(a, b)$ et $D = \text{PGCD}(a, bc)$.

$d$ divise $D$ :

$d$ divise $a$ et $d$ divise $b$,

donc $d$ divise $bc$.

Ainsi, $d$ est un diviseur commun de $a$ et $bc$,

donc $d$ divise $D$.

$D$ divise $d$ :

$D$ divise $a$ et $D$ divise $bc$.

Comme $\text{PGCD}(a, c) = 1$,

alors, d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + cv = 1$.

Multiplions cette égalité par $b$ : $abu + bcv = b$.

$D$ divise $a$ donc $D$ divise $abu$.

$D$ divise $bc$ donc $D$ divise $bcv$.

Donc $D$ divise $(abu + bcv)$, c'est-à-dire $D$ divise $b$.

Comme $D$ divise $a$ et $D$ divise $b$,

on en déduit que $D$ divise $d$.

Comme $d$ divise $D$ et $D$ divise $d$,

et que $d$ et $D$ sont positifs, on conclut que $d=D$.

Correction :

1. $u_n = 9 \cdot 2^n - 6$

   $u_n= 2(9 \cdot 2^{n-1} - 3)$

   $u_n = 3(3 \cdot 2^n - 2)$.

   Donc $u_n$ est divisible par $2$ et par $3$.

   Comme $\text{PGCD}(2,3)=1$, $u_n$ est divisible par $6$.

2. L'affirmation est fausse.

   Par exemple, $v_6 = 95 = 5 \cdot 19$ qui n'est pas un nombre premier.

3. 1. $v_{n+1} - 2v_n = (3 \cdot 2^n - 1) - 2(3 \cdot 2^{n-1} - 1)$

      $v_{n+1} - 2v_n= 3 \cdot 2^n - 1 - 3 \cdot 2^n + 2$

      $v_{n+1} - 2v_n = 1$.

   2. On a $v_{n+1} - 2v_n = 1$.

      D'après le théorème de Bézout, $\text{PGCD}(v_n, v_{n+1}) = 1$.

   3. $\text{PGCD}(u_n, u_{n+1}) = \text{PGCD}(6v_n, 6v_{n+1})$

      $\text{PGCD}(u_n, u_{n+1})= 6\text{PGCD}(v_n, v_{n+1})$

      $\text{PGCD}(u_n, u_{n+1}) = 6 \cdot 1 = 6$.

4. 1. $2^4 = 16$

      $16 \equiv 1 \pmod{5}$.

   2. Si $n = 4k+2$, alors :

      $u_n = 9 \cdot 2^{4k+2} - 6$

      $u_n = 9 \cdot (2^4)^k \cdot 2^2 - 6$

      $u_n \equiv 9 \cdot 1^k \cdot 4 - 6 \pmod{5}$

      $u_n \equiv 36 - 6 \pmod{5}$

      $u_n \equiv 30 \pmod{5}$

      $u_n \equiv 0 \pmod{5}$.

      Donc $u_n$ est divisible par $5$.

   3. On examine les autres cas possibles pour $n$ modulo $4$ :

      Si $n \equiv 0 \pmod{4}$, $u_n \equiv 9 \cdot 1 - 6 \equiv 3 \pmod{5}$.

      Si $n \equiv 1 \pmod{4}$, $u_n \equiv 9 \cdot 2 - 6 \equiv 12 \equiv 2 \pmod{5}$.

      Si $n \equiv 3 \pmod{4}$, $u_n \equiv 9 \cdot 8 - 6 \equiv 66 \equiv 1 \pmod{5}$.

      Donc $u_n$ est divisible par $5$ seulement si $n \equiv 2 \pmod{4}$.

Correction :

1. $a = n(n^2 - n - 12) = n(n-4)(n+3)$.

   $b = 2n^2 - 7n - 4 = (n-4)(2n+1)$.

2. 1. $2\beta - \alpha = 2(n+3) - (2n+1)$

      $2\beta - \alpha = 2n + 6 - 2n - 1$

      $2\beta - \alpha = 5$.

   2. $d$ divise $\alpha$ et $d$ divise $\beta$,

      donc $d$ divise toute combinaison linéaire de $\alpha$ et $\beta$.

      En particulier, $d$ divise $2\beta - \alpha = 5$.

      Donc $d$ divise $5$.

   3. ($\Rightarrow$) Si $5$ divise $\alpha$ et $5$ divise $\beta$,

      alors $5$ divise $n+3$, donc $n \equiv -3 \equiv 2 \pmod{5}$.

      Donc $n-2 \equiv 0 \pmod{5}$.

      ($\Leftarrow$) Si $5$ divise $n-2$,

      alors $n \equiv 2 \pmod{5}$.

      Donc $n+3 \equiv 5 \equiv 0 \pmod{5}$ et $2n+1 \equiv 5 \equiv 0 \pmod{5}$.

3. Soit $g = \text{PGCD}(2n+1, n)$.

   Alors $g$ divise $2n+1$ et $g$ divise $n$.

   Donc $g$ divise $1 \cdot (2n+1) - 2 \cdot n = 1$.

   Donc $g=1$.

4. $\text{PGCD}(a, b) = \text{PGCD}(n(n-4)(n+3), (n-4)(2n+1))$

   $\text{PGCD}(a, b)= |n-4|\text{PGCD}(n(n+3), 2n+1)$.

   Posons $d = \text{PGCD}(n(n+3), 2n+1) = \text{PGCD}(n^2 + 3n, 2n+1)$.

   Comme $d$ divise $2n+1$ et $n$, $d$ divise toute combinaison linéaire de ces deux nombres.

   $d$ divise $2(n^2 + 3n) - n(2n+1) = 2n^2 + 6n - 2n^2 - n = 5n$.

   Donc $d = \text{PGCD}(5n, 2n+1)$.

   $d$ divise $5n$ et $2n+1$, donc $d$ divise $2(5n)-5(2n+1)=10n - 10n - 5 = -5$.

   Donc $d$ divise $5$, d'où $d=1$ ou $d=5$.

   $d= \text{PGCD}(5n,2n+1) = \text{PGCD}(5n - 2(2n+1) , 2n+1) $

   $d=\text{PGCD}(n-2,2n+1)$

   $d= \text{PGCD}(n-2, 2n+1 - 2(n-2)) = \text{PGCD}(n-2,5)$.

   Finalement, $\text{PGCD}(a,b) = |n-4|\text{PGCD}(n-2,5)$

   Si $n \equiv 2 \pmod{5}$, alors $\text{PGCD}(n-2, 5) = 5$, et donc $\text{PGCD}(a,b) = 5|n-4|$.

   Si $n \not\equiv 2 \pmod{5}$, alors $\text{PGCD}(n-2, 5) = 1$, et donc $\text{PGCD}(a,b) = |n-4|$.

5. $n=6$: $n \not\equiv 2 \pmod{5}$, donc $\text{PGCD}(a,b) = |6-4| = 2$.

   $a = 108$, $b = 26$, $\text{PGCD}(108, 26) = 2$. OK.

   $n=7$: $n \equiv 2 \pmod{5}$, donc $\text{PGCD}(a,b) = 5|7-4| = 15$.

   $a = 210$, $b = 45$, $\text{PGCD}(210, 45) = 15$. OK.