Exercices : PGCD - Arithmétique - Spé Maths

Correction :

On procède en trois étapes :

1. Décomposition de 4480 en facteurs premiers :

$4480 = 2^7 \times 5 \times 7$.

2. Décomposition de 400 en facteurs premiers :

$400 = 2^4 \times 5^2$.

3. Détermination du PGCD : On sélectionne les facteurs premiers communs aux deux décompositions, en choisissant la plus petite puissance pour chaque facteur.

Les facteurs premiers communs sont 2 et 5.

La plus petite puissance de 2 est $2^4$.

La plus petite puissance de 5 est $5^1$.

Donc, $\text{PGCD}(4480~;~400) = 2^4 \times 5^1 = 16 \times 5 = 80$.

Conclusion : Le PGCD de 4480 et 400 est 80.

Correction :

L'algorithme d'Euclide repose sur des divisions euclidiennes successives :

Étape 1 : Division de 3045 par 300

$3045 = 300 \times 10 + 45$

Étape 2 : Division de 300 par le reste précédent (45)

$300 = 45 \times 6 + 30$

Étape 3 : Division de 45 par le reste précédent (30)

$45 = 30 \times 1 + 15$

Étape 4 : Division de 30 par le reste précédent (15)

$30 = 15 \times 2 + 0$

Le reste est nul : l'algorithme se termine.

Le PGCD est le dernier reste non nul, soit 15.

Conclusion : $\text{PGCD}(3045~;~300) = 15$.

Correction :

Les diviseurs communs à deux nombres sont les diviseurs de leur PGCD.

1. Calcul du PGCD(168 ; 204) avec l'algorithme d'Euclide :

$204 = 168 \times 1 + 36$

$168 = 36 \times 4 + 24$

$36 = 24 \times 1 + 12$

$24 = 12 \times 2 + 0$

Le dernier reste non nul est 12, donc $\text{PGCD}(168~;~204) = 12$.

2. Liste des diviseurs de 12 :

On teste les entiers de 1 à 12 : 1, 2, 3, 4, 6, et 12 divisent 12.

Conclusion : Les diviseurs communs à 168 et 204 sont : 1, 2, 3, 4, 6, et 12.

Correction :

On doit montrer que $\text{PGCD}(m, n) = 1$. On sait que $m + n = p$, où $p$ est premier.

D'après le lemme d'Euclide : $\text{PGCD}(m~;~n) = \text{PGCD}(m~;~m+n) = \text{PGCD}(m~;~p)$.

Puisque $p$ est premier, ses seuls diviseurs sont 1 et $p$. Donc $\text{PGCD}(m, p)$ vaut soit 1, soit $p$.

Si $\text{PGCD}(m~;~p) = p$, alors $p$ divise $m$. Mais comme $m + n = p$, cela signifierait que $p$ divise aussi $n$ (car $n = p - m$). C'est impossible, car $m$ et $n$ sont non nuls et strictement inférieurs à $p$ (leur somme est $p$).

La seule possibilité restante est donc $\text{PGCD}(m~;~p) = 1$, et par conséquent $\text{PGCD}(m~;~n) = 1$.

Conclusion : $m$ et $n$ sont premiers entre eux.

Méthode alternative (par l'absurde) :

Supposons que $m$ et $n$ ne soient pas premiers entre eux. Alors, il existe un diviseur commun $d > 1$ tel que $d$ divise $m$ et $d$ divise $n$. Donc $d$ divise aussi $m + n = p$. Mais $p$ est premier, donc ses seuls diviseurs sont 1 et $p$. Comme $d > 1$, on a $d = p$. Cela signifie que $p$ divise $m$ et $p$ divise $n$, ce qui est impossible comme expliqué précédemment. Cette contradiction montre que notre supposition initiale était fausse, et donc $m$ et $n$ sont premiers entre eux.

Correction :

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

On utilise une combinaison linéaire pour éliminer $n$ : $2(5n+1) - 5(2n-1) = 10n + 2 - 10n + 5 = 7$.

Donc $d$ divise 7. Les seuls diviseurs positifs de 7 sont 1 et 7, donc $d$ vaut soit 1, soit 7.

On cherche quand $d=7$. Si $d=7$, alors à la fois $5n + 1$ et $2n - 1$ doivent être divisibles par 7.

Pour $2n - 1$ : Si $2n - 1 \equiv 0 \pmod{7}$, alors $2n \equiv 1 \pmod{7}$. En multipliant par 4 (l'inverse de 2 modulo 7), on obtient $8n \equiv 4 \pmod{7}$, soit $n \equiv 4 \pmod{7}$.

Vérifions pour $5n + 1$ : Si $n \equiv 4 \pmod{7}$, alors $5n \equiv 5 \cdot 4 \equiv 20 \equiv 6 \pmod{7}$. Donc, $5n + 1 \equiv 6 + 1 \equiv 7 \equiv 0 \pmod{7}$. $5n + 1$ est bien divisible par 7 lorsque $n \equiv 4 \pmod{7}$.

Conclusion :

$\text{PGCD}(5n+1; 2n-1) = \begin{cases} 7 & \text{si } n \equiv 4 \pmod{7} \\ 1 & \text{si } n \not\equiv 4 \pmod{7} \end{cases} $

Correction :

Une fraction est irréductible si et seulement si le plus grand commun diviseur (PGCD) de son numérateur et de son dénominateur est égal à 1.

Soit $d = \text{PGCD}(3n+2; n+2)$. Notre objectif est de déterminer les valeurs de $n$ pour lesquelles $d = 1$.

Étape 1: Combinaison linéaire

Utilisons une combinaison linéaire pour éliminer $n$. On peut multiplier $(n+2)$ par 3 et le soustraire de $(3n+2)$ : $(3n + 2) - 3(n+2) = 3n + 2 - 3n - 6 = -4$.

Par conséquent, $d$ divise $-4$. Puisque $d$ est un diviseur positif, cela implique que $d$ divise 4.

Étape 2: Diviseurs possibles de d

Les diviseurs positifs de 4 sont 1, 2 et 4. Donc, $d$ peut uniquement prendre les valeurs 1, 2 ou 4.

Étape 3: Analyse des cas pour d

- Si $d = 1$, alors la fraction est irréductible. C'est le cas que nous recherchons.
- Si $d = 2$ ou $d = 4$, alors $3n + 2$ et $n + 2$ sont tous deux divisibles par 2 (et donc pairs). Analysons cette situation plus en détail en utilisant les congruences.

Étape 4: Analyse de la parité avec les congruences

Un nombre est pair si et seulement s'il est congru à 0 modulo 2. Un nombre est impair si et seulement s'il est congru à 1 modulo 2.

Si $n$ est pair, alors $n \equiv 0 \pmod{2}$. Donc:

- $n + 2 \equiv 0 + 2 \equiv 2 \equiv 0 \pmod{2}$ (Donc $n+2$ est pair)
- $3n + 2 \equiv 3(0) + 2 \equiv 2 \equiv 0 \pmod{2}$ (Donc $3n+2$ est pair)

Si $n \equiv 0 \pmod{2}$ alors $n+2$ et $3n + 2$ sont pairs, donc $d \ge 2$ et la fraction est réductible.

Si $n$ est impair, alors $n \equiv 1 \pmod{2}$. Donc:

- $n + 2 \equiv 1 + 2 \equiv 3 \equiv 1 \pmod{2}$ (Donc $n+2$ est impair)
- $3n + 2 \equiv 3(1) + 2 \equiv 5 \equiv 1 \pmod{2}$ (Donc $3n+2$ est impair)

Si $n \equiv 1 \pmod{2}$, alors $n + 2$ et $3n+2$ sont impairs, donc $d$ ne peut pas être 2 ou 4. Puisque $d$ divise 4 et que $d$ ne peut être ni 2 ni 4, alors $d = 1$.

Conclusion :

La fraction $\displaystyle \frac{3n+2}{n+2}$ est irréductible si et seulement si $n$ est impair (c'est-à-dire, $n \equiv 1 \pmod{2}$).

Correction :

Méthode 1 : Combinaison linéaire

Soit $d = \text{PGCD}(9n + 4, 2n + 1)$.

On cherche une combinaison linéaire qui élimine $n$: $2(9n + 4) - 9(2n + 1) = 18n + 8 - 18n - 9 = -1$.

Donc $d$ divise -1, ce qui signifie que $d = 1$.

Méthode 2 : Algorithme d'Euclide

On applique l'algorithme d'Euclide :

$9n + 4 = 4(2n+1) + (n)$

$2n+1 = 2(n) + 1$

$n = n(1) + 0$

Le dernier reste non nul est 1, donc le PGCD est 1.

Conclusion : Le PGCD de $9n + 4$ et $2n + 1$ est toujours 1, quel que soit l'entier naturel $n$.

Correction :

1. Algorithme d'Euclide :

\(540 = 3 \times 174 + 18\)

\(174 = 9 \times 18 + 12\)

\(18 = 1 \times 12 + 6\)

\(12 = 2 \times 6 + 0\)

Le dernier reste non nul est 6, donc PGCD(540, 174) = 6.

2. Algorithme d'Euclide étendu (remontée) :

On exprime chaque reste en fonction de 540 et 174 :

\(6 = 18 - 1 \times 12\)

\(12 = 174 - 9 \times 18\), donc \(6 = 18 - 1 \times (174 - 9 \times 18) = 10 \times 18 - 1 \times 174\)

\(18 = 540 - 3 \times 174\), donc \(6 = 10 \times (540 - 3 \times 174) - 1 \times 174 = 10 \times 540 - 31 \times 174\)

Conclusion : \(6 = 10 \times 540 - 31 \times 174\).

Correction :

Si \(n + 5\) divise \(3n + 20\), alors il divise aussi toute combinaison linéaire de \(n+5\) et \(3n+20\). En particulier, il divise \(3(n + 5) = 3n + 15\).

Donc, \(n + 5\) divise la différence \((3n + 20) - (3n + 15) = 5\).

Les diviseurs positifs de 5 sont 1 et 5.

Si \(n + 5 = 1\), alors \(n = -4\), ce qui n'est pas un entier naturel.

Si \(n + 5 = 5\), alors \(n = 0\), qui est un entier naturel.

Conclusion : La seule solution est \(n = 0\).

Correction :

Correction :

Si $\text{PGCD}(a, b) = d$, alors par définition, $d$ divise $a$ et $d$ divise $b$. Donc il existe des entiers $a'$ et $b'$ tels que $a = da'$ et $b = db'$.

Soit $d' = \text{PGCD}(a', b')$. On veut montrer que $d' = 1$.

Puisque $d'$ divise $a'$ et $b'$, il existe des entiers $k$ et $l$ tels que $a' = kd'$ et $b' = ld'$. Alors on peut écrire : $a = da' = d(kd') = (dd')k$ et $b = db' = d(ld') = (dd')l$.

Donc $dd'$ est un diviseur commun de $a$ et $b$.

Or, $d$ est le plus grand diviseur commun de $a$ et $b$. Puisque $dd'$ est un diviseur commun de $a$ et $b$, on doit avoir $dd' \le d$.

Comme $d$ et $d'$ sont positifs (ce sont des PGCD), l'inégalité $dd' \le d$ implique $d' \le 1$.

Mais $d'$ est un PGCD, donc par définition $d' \ge 1$.

Les deux conditions $d' \le 1$ et $d' \ge 1$ impliquent que $d' = 1$.

Conclusion : $\text{PGCD}(a', b') = 1$.

Correction :

Si $\text{PGCD}(x, 24) = 6$, alors $x = 6k$ pour un certain entier naturel $k$, et $24 = 6 \times 4$.

De plus, on doit avoir $\text{PGCD}(k, 4) = 1$. Si le PGCD de $k$ et 4 était supérieur à 1, alors le PGCD de $x$ et 24 serait supérieur à 6.

Les diviseurs de 4 sont 1, 2, et 4. Pour que $\text{PGCD}(k, 4) = 1$, il faut que $k$ ne soit divisible ni par 2, ni par 4. Cela signifie que $k$ doit être impair.

Conclusion : Les solutions sont tous les nombres de la forme $x = 6k$, où $k$ est un entier naturel impair quelconque.

Correction :

Si $\text{PGCD}(a, b) = 8$, alors $a = 8a'$ et $b = 8b'$, où $a'$ et $b'$ sont des entiers naturels tels que $\text{PGCD}(a', b') = 1$ (d'après l'exercice 11).

On a $a + b = 8a' + 8b' = 8(a' + b') = 96$.

Donc $a' + b' = \frac{96}{8} = 12$.

On cherche les couples d'entiers naturels $(a', b')$ premiers entre eux dont la somme est 12. On liste les possibilités :

1. $a' = 1$, $b' = 11$
2. $a' = 5$, $b' = 7$
3. $a' = 7$, $b' = 5$
4.$a' = 11$, $b' = 1$

Les couples $(a, b)$ correspondants sont obtenus en multipliant chaque couple $(a', b')$ par 8 :

1. $(8 \times 1, 8 \times 11) = (8, 88)$
2. $(8 \times 5, 8 \times 7) = (40, 56)$
3. $(8 \times 7, 8 \times 5) = (56, 40)$
4. $(8 \times 11, 8 \times 1) = (88, 8)$

Conclusion: Les couples $(a,b)$ solutions sont $(8, 88)$, $(40, 56)$, $(56, 40)$, et $(88, 8)$.

Correction :

Soit $d = \text{PGCD}(a+b, ab)$. On doit montrer que $d = 1$.

Puisque $d$ divise $a+b$ et $ab$, $d$ divise aussi $(a+b)a = a^2 + ab$ et $(a+b)b = ab+b^2$.

Donc d divise $(a^2+ab) - ab = a^2$ et $d$ divise $(ab+b^2)-ab = b^2$.

Donc $d$ est un diviseur commun de $a^2$ et $b^2$. Or, si $\text{PGCD}(a,b)=1$, alors $\text{PGCD}(a^2, b^2) = 1$.

Preuve de $\text{PGCD}(a,b)=1 \implies \text{PGCD}(a^2, b^2) = 1$:

Supposons que $\text{PGCD}(a^2, b^2) = d' > 1$. Alors il existe un nombre premier $p$ qui divise $d'$. Donc $p$ divise $a^2$ et $b^2$. Si un nombre premier divise un produit, il divise au moins l'un des facteurs. Puisque $p$ divise $a^2 = a \cdot a$, $p$ divise $a$. De même, $p$ divise $b$. Donc $p$ est un diviseur commun de $a$ et $b$, ce qui contredit l'hypothèse $\text{PGCD}(a,b)=1$.

Puisque $\text{PGCD}(a^2,b^2)=1$ et que $d$ est un diviseur commun de $a^2$ et $b^2$, on doit avoir $d=1$.

Conclusion: $a+b$ et $ab$ sont premiers entre eux.

Correction :

C'est le même principe que l'exercice 14 :

$a = 15a'$, $b = 15b'$, avec $\text{PGCD}(a', b') = 1$.

$a + b = 15a' + 15b' = 15(a' + b') = 180$.

Donc $a' + b' = \frac{180}{15} = 12$.

On cherche les couples d'entiers naturels $(a', b')$ premiers entre eux et de somme 12 : (1, 11), (5, 7), (7, 5), (11, 1).

Les couples $(a, b)$ correspondants sont : (15, 165), (75, 105), (105, 75), (165, 15).

Correction :

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

On remarque que $5n^3 - n = n(5n^2 - 1)$. On effectue la division euclidienne de $5n^2 -1$ par $n+2$ :

$5n^2 - 1 = (n+2)(5n-10) + 19$.

Donc $5n^3 - n = n[(n+2)(5n-10) + 19] = n(n+2)(5n-10) + 19n$.

Comme $d$ divise $n+2$ et $5n^3 - n$, $d$ divise aussi $n(n+2)(5n-10)$. Puisque $d$ divise $5n^3 - n = n(n+2)(5n-10) + 19n$, $d$ divise donc $19n$.

De plus, $d$ divise $n+2$, donc $d$ divise $19(n+2) = 19n + 38$.

Comme $d$ divise $19n$ et $19n + 38$, $d$ divise leur différence : $(19n + 38) - 19n = 38$.

Conclusion: $d$ divise 38.

Correction :

On utilise la propriété suivante (qui peut être démontrée par l'algorithme d'Euclide) : $\text{PGCD}(a^m - 1, a^n - 1) = a^{\text{PGCD}(m,n)} - 1$.

On calcule $\text{PGCD}(2024, 2020)$ :

$2024 = 1 \times 2020 + 4$

$2020 = 505 \times 4 + 0$

Donc $\text{PGCD}(2024, 2020) = 4$.

On applique la propriété : $\text{PGCD}(2^{2024} - 1, 2^{2020} - 1) = 2^{\text{PGCD}(2024, 2020)} - 1 = 2^4 - 1 = 16 - 1 = 15$.

Conclusion: $\text{PGCD}(2^{2024} - 1, 2^{2020} - 1) = 15$.

Correction :

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

Alors $d$ divise toute combinaison linéaire de $2n+1$ et $3n+1$. En particulier, $d$ divise $3(2n+1) - 2(3n+1) = 6n+3-6n-2 = 1$.

Donc $d$ divise 1, et par conséquent $d=1$.

Conclusion: Pour tout entier naturel $n$, les nombres $2n+1$ et $3n+1$ sont premiers entre eux.

Correction :

Soit $d_1 = \text{PGCD}(a,b,c)$ et $d_2 = \text{PGCD}(\text{PGCD}(a,b),c)$. On doit montrer que $d_1 = d_2$.

Par définition, $d_1$ divise $a$, $b$, et $c$. Donc $d_1$ divise toute combinaison linéaire de $a$ et $b$, en particulier $d_1$ divise $\text{PGCD}(a,b)$. Puisque $d_1$ divise $\text{PGCD}(a,b)$ et $d_1$ divise $c$, $d_1$ est un diviseur commun de $\text{PGCD}(a,b)$ et $c$. Donc $d_1$ divise $\text{PGCD}(\text{PGCD}(a,b), c) = d_2$.

Réciproquement, $d_2$ divise $\text{PGCD}(a,b)$ et $d_2$ divise $c$. Puisque $d_2$ divise $\text{PGCD}(a,b)$, $d_2$ divise $a$ et $b$ (car tout diviseur du PGCD de deux nombres divise ces deux nombres). Donc $d_2$ divise $a$, $b$, et $c$. Donc $d_2$ est un diviseur commun de $a$, $b$, et $c$, et par conséquent $d_2$ divise $\text{PGCD}(a,b,c) = d_1$.

On a montré que $d_1$ divise $d_2$ et $d_2$ divise $d_1$. Puisque $d_1$ et $d_2$ sont des entiers positifs, cela implique $d_1 = d_2$.

Conclusion: $\text{PGCD}(a,b,c) = \text{PGCD}(\text{PGCD}(a,b), c)$.