Terminale – Maths expertes – Arithmétique – PGCD

Arithmétique

PGCD

Exercice 1

Utiliser l’algorithme d’Euclide pour trouver le $\text{PGCD}$ des  nombres suivants :

  1. $360$ et $2~100$
    $\quad$
  2. $468$ et $312$
    $\quad$
  3. $700$ et $840$
    $\quad$
  4. $300$ et $350$
    $\quad$
  5. $168$ et $2~160$
    $\quad$
  6. $308$ et $364$
    $\quad$
  7. $1~105$ et $462$
    $\quad$
Correction Exercice 1

  1. $2~100=5\times 360+300$
    $360 = 1\times 300+60$
    $300 = 5\times 60+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(360;2~160)=60$.
    $\quad$
  2. $468=1\times 312+156$
    $312 = 2\times 156+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(468;312)=156$.
    $\quad$
  3. $840=1\times 700+140$
    $700 = 5\times 140+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(840;700)=140$.
    $\quad$
  4. $350=1\times 300+50$
    $300 = 6\times 50+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(350;300)=50$.
    $\quad$
  5. $2~160=12\times 168+144$
    $168 = 1\times 144+24$
    $144 = 6\times 24+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(2~160;168)=24$.
    $\quad$
  6. $364=1\times 308+56$
    $308 = 5\times 56+28$
    $56 = 2\times 28+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(364;308)=28$.
    $\quad$
  7. $1~105=2\times 462+181$
    $462 = 2\times 181+100$
    $181 = 1\times 100+81$
    $100 = 1\times 81+19$
    $81 = 4\times 19+5$
    $19=3\times 5+4$
    $5=1\times 4+1$
    $4=4\times 1+0$
    Le $\text{PGCD}$ est le dernier reste non nul dans l’algorithme d’Euclide.
    Par conséquent $\text{PGCD}(1~105;462)=1$.
    $\quad$

[collapse]

$\quad$

Exercice 2

Trouver 2 nombres entiers naturels $a$ et $b$ dont le $\text{PGCD}$ est $4$ tels que $a + b = 48$.

$\quad$

Correction Exercice 2

Il existe donc deux entiers naturels $a’$ et $b’$ premiers entre eux, tels que $a=4a’$ et $b=4b’$.

Ainsi $4a’+4b’=48$ soit $a’+b’=12$.

  • Si $a’=1$ alors $b’=11$. $a’$ et $b’$ sont premiers entre eux. Donc $a=4$ et $b=44$.
  • Si $a’=2$ alors $b’=10$. $a’$ et $b’$ sont divisibles par $2$.
  • Si $’=3$ alors $b’=9$ $a’$ et $b’$ sont divisibles par $2$.
  • Si $a’=4$ alors $b’=8$. $a’$ et $b’$ sont divisibles par $2$.
  • Si $a’=5$ alors $b’=7$. $a’$ et $b’$ sont premiers entre eux. Donc $a=20$ et $b=28$.
  • Si $a’=6$ alors $b’=6$. $a’$ et $b’$ sont égaux.

Ainsi, par symétrie, les couples solutions sont $(4;44)$, $(20;28)$, $(28;20)$ et $(44;4)$.

$\quad$

[collapse]

$\quad$

Exercice 3

Soit $n\in \N$ , quand on divise $169$ et $267$ par $n$, on obtient le même reste $15$ .

  1. Démontrer que $n$ est un diviseur commun à $154$ et $252$.
    $\quad$
  2. Quelle est la plus grande valeur possible pour $n$ ?
    $\quad$
Correction Exercice 3

  1. Il existe donc deux entiers naturels $p$ et $q$ tels que $169=np+15$ et $267=nq=+15$.
    Par conséquent $154=np$ et $252=nq$.
    $n$ divise donc $154$ et $252$.
    $\quad$
  2. Le plus grand diviseur commun à $154$ et $252$ est leur $\text{PGCD}$.
    On applique l’algorithme d’Euclide pour le déterminer :
    $252 = 1\times 154+98$
    $154=1\times 98+56$
    $98=1\times 56+42$
    $56=1\times 42+14$
    $42=3\times 14+0$
    Le $\text{PGCD}$ est le dernier reste non nul.
    Ainsi la plus grande valeur possible pour $n$ est $14$.
    $\quad$

[collapse]

$\quad$

$\quad$

Exercice 4

Déterminer deux entiers naturels $a$ et $b$ sachant que leur $\text{PGCD}$  est $9$ et leur somme $72$.

$\quad$

Correction Exercice 4

Il existe donc deux entiers naturels $a’$ et $b’$ premiers entre eux tels que $a=9a’$ et $b=9b’$.

On a ainsi $9a’+9b’=72$ soit $a’+b’=8$.

  • Si $a’=1$ alors $b’=7$. Ils sont premiers entre eux. On a ainsi $a=9$ et $b=63$.
  • Si $a’=2$ alors $b’=6$. Ils ne sont pas premiers entre eux.
  • Si $a’=3$ alors $b’=5$. Ils sont premiers entre eux. On a ainsi $a=27$ et $b=45$.
  • Si $a’=4$ alors $b’=4$. Ils ne sont pas premiers entre eux.

Ainsi par symétrie, les solutions sont les couples $(9;63)$, $(27;45)$, $(45;27)$ et $(63;9)$.

$\quad$

[collapse]

$\quad$

Exercice 5

Déterminer deux entiers naturels $a$ et $b$ sachant que leur $\text{PGCD}$  est $17$ et leur produit $1~734$.

$\quad$

Correction Exercice 5

Il existe donc deux entiers naturels $a’$ et $b’$ premiers entre eux tels que $a=17a’$ et $b=17b’$.

On a ainsi $17a’\times 17b’=1~734$ soit $a’b’=6$.

  • Si $a’=1$ alors $b’=6$. Ils sont premiers entre eux. On a ainsi $a=17$ et $b=102$.
  • Si $a’=2$ alors $b’=3$. Ils sont premiers entre eux. On a ainsi $a=34$ et $b=51$

Ainsi par symétrie, les solutions sont les couples $(17;102)$, $(34;51)$, $(51;34)$ et $(102;17)$.

$\quad$

[collapse]

$\quad$

 

Exercice 6

Trouver tous les couples d’entiers naturels $( a ; b )$ tels que: $2 a^2 + b^2 = 16~072$ et $\text{PGCD} ( a , b ) = 14$.

$\quad$

Correction Exercice 6

Il existe donc deux entiers naturels $a’$ et $b’$ premiers entre eux tels que $a=14a’$ et $b=14b’$.

On a ainsi $392a’+196b’=16~072$ soit $2a’^2+b’^2=82$.
Par conséquent $b’^2=82-2a’^2$ et donc $b’^2=2\left(41-a’^2\right)$.
$b’^2$ est pair par conséquent $b’$ l’est également (la preuve se fait, si nécessaire, à l’aide d’un raisonnement par l’absurde).
De plus $b’^2<82$ donc $b’\pp 9$.

  • Si $b’=2$ alors $b’^2=4$. Ainsi $a’^2=39$ et $a’$ n’est pas un entier.
  • Si $b’=4$ alors $b’^2=16$. Ainsi $a’^2=33$ et $a’$ n’est pas un entier.
  • Si $b’=6$ alors $b’^2=36$. Ainsi $a’^2=23$ et $a’$ n’est pas un entier.
  • Si $b’=8$ alors $b’^2=64$. Ainsi $a’^2=9$ et $a’=3$.
    On a alors $a=42$ et $b=112$

Le seul couple solution est $(42;112)$.

$\quad$

[collapse]

$\quad$

 

Exercice 7

$a$ et $b$ sont deux entiers naturels premiers entre eux tels que $a^2 + a = 7 b^3$ .

  1. Justifier que $a$ et $b^3$ sont premiers entre eux.
    $\quad$
  2. Démontrer que $a$ divise $7$. Trouver les valeurs de $a$ et $b$ vérifiant les hypothèses.
    $\quad$
Correction Exercice 7

  1. $a$ est premier avec $b$, il est donc également premier avec $b^2=b\times b$ et $b^3=b^2\times b$.
    $\quad$
  2. $a^2+a=7b^3\ssi a(a+1)=7b^3$.
    $a$ divise donc $7b^3$ et est premier avec $b^3$.
    Par conséquent $a$ divise $7$.
    Ainsi $a=1$ ou $a=7$.
    $\bullet$ Si $a=1$ alors $7b^3=2$ ce qui est impossible.
    $\bullet$ Si $a=7$ alors $7b^3=56$ soit $b^3=8$ et $b=2$.
    Le seul couple solution est donc $(7;2)$.
    $\quad$

[collapse]

$\quad$

Exercice 8

Soit $n \in \N$ tel que en divisant $n$ par $567$ et $407$, on obtient le même reste $60$.

  1. Démontrer que $n-60$ est un multiple de $567$ et $407$.
    $\quad$
  2. Quelle est la plus petite valeur de $n$ possible? (On utilise le $\text{PPCM}$ dans cette question.)
    $\quad$
Correction Exercice 8

  1. Il existe deux entiers naturels $p$ et $q$ tels que $n=567p+60$ et $n=407n+60$
    Ainsi $n-60=567p$ et $n-60=407n$.
    $567$ et $407$ sont donc des diviseurs de $n-60$.
    Par conséquent $n-60$ est un multiple de $567$ et de $407$.
  2. On cherche donc le plus petit multiple commun à $567$ et $407$.
    $567$ et $407$ sont premiers entre eux.
    Or, pour tout couple d’entiers naturels $a$ et $b$ on a $ab=\text{PGCD}(a;b)\times \text{PPCM}(a;b)$
    En particulier, quand $a$ et $b$ sont premiers entre eux, $ab=\text{PPCM}(a;b)$.
    Ainsi, la plus petite valeur possible pour $n-60$ est $567\times 407=230~769$ et donc $n=230~829$.
    $\quad$

[collapse]

$\quad$

Exercice 9

Résoudre dans $\N\times \N$ le système : $$\begin{cases} x^2-y^2=5~440\\\text{PGCD}(x,y)=8\end{cases}$$

$\quad$

Correction Exercice 9

Il existe deux entiers naturel $x’$ et $y’$ premiers entre eux tels que $x=8x’$ et $y=8y’$.
Ainsi $64x’^2-64y’^2=5~440$ soit $x’^2-y’^2=85$.
Par conséquent $(x’-y’)(x’+y’)=5\times 17$.

On résout donc les quatre systèmes suivants :
$ \begin{cases}x’-y’=5\\x’+y’=17\end{cases}\ssi \begin{cases} x’=11\\y’=6\end{cases}$. Donc $x=88$ et $y=48$.
$\quad$
$ \begin{cases}x’-y’=17\\x’+y’=5\end{cases}\ssi \begin{cases} x’=11\\y’=-6\end{cases}$ ce qui est impossible puisque $y’\pg 1$.
$\quad$
$ \begin{cases}x’-y’=1\\x’+y’=85\end{cases}\ssi \begin{cases} x’=43\\y’=42\end{cases}$. Donc $x=344$ et $y=336$.
$\quad$
$ \begin{cases}x’-y’=85\\x’+y’=1\end{cases}\ssi \begin{cases} x’=43\\y’=-42\end{cases}$ ce qui est impossible puisque $y’\pg 1$.

Ainsi les seuls couples solutions sont $(88;48)$ et $(344;336)$.

$\quad$

 

[collapse]

$\quad$

Exercice 10

On considère deux entiers naturels $a$ et $b$ , $A= 11 a +2 b$ et $B = 18 a +5 b$.

  1. Démontrer que si un des nombres $A$ ou $B$ est divisible par $19$ , alors l’autre aussi.
    $\quad$
  2. Démontrer que si $a$ et $b$ sont premiers entre eux, $A$ et $B$ ne peuvent avoir d’autres diviseurs communs que $1$ et $19$.
    $\quad$
Correction Exercice 10

 

  1. Supposons que $19$ divise $A$.
    On a $11B-18A=19b$. Ainsi $11B=19b-18A$.
    Si $A$ est divisible par $19$ alors $11B$ l’est également.
    $19$ et $11$ sont premiers entre eux. Par conséquent $19$ divise $B$.
    Si $19$ divise $B$ alors $18A=11B-19b$ et, en appliquant le même raisonnement, on obtient que $A$ est également divisible par $19$.
    $\quad$
  2. On a $11B-18A=19b$ et $5A-2B=19a$.
    Ainsi si $d$ divise à la fois $A$ et $B$, il divise également $19a$ et $19b$.
    $a$ et $b$ étant premiers entre eux, $d$ ne peut diviser que $19$.
    Ainsi les seuls diviseurs communs possibles de $A$ et $B$ sont $1$ et $19$.
    $\quad$

[collapse]

$\quad$

Exercice 11

On considère deux entiers naturels $a$ et $b$ et on note $d$ un diviseur de $a$ et $b$.

  1. Démontrer que $d$ divise $4 a + 3 b$ et $5 a + 4 b$.
    $\quad$
  2. Réciproquement, démontrer que tout diviseur de $4 a + 3 b$ et $5 a + 4 b$ divise $a$ et $b$.
    $\quad$
  3. En déduire que $( a ; b )$ et $( 4 a + 3 b ; 5 a + 4 b )$ ont même $\text{PGCD}$ .
    $\quad$
Correction Exercice 11

  1. $d$ divise $a$ et $b$. Il divise donc toute combinaison linéaire de ces deux nombres en particulier $4a+3b$ et $5a+4b$.
    $\quad$
  2. $-5(4a+3b)+4(5a+4b)=b$.
    $4(4a+3b)-3(5a+4b)=a$
    Tout diviseur de $4a+3b$ et $5a+4b$ divise toutes leurs combinaisons linéaires et donc en particulier les deux données au-dessus. Il divise ainsi $a$ et $b$.
    $\quad$
  3. Ainsi $d$ divise $a$ et $b$ si, et seulement si, $d$ divise $4a+3b$ et $5a+4b$.
    Par conséquent le $\text{PGCD}$ de $a$ et $b$ divise celui de $4a+3b$ et $5a+4b$. On a donc $\text{PGCD}(a;b) \pp \text{PGCD}(4a+3b;5a+4b)$.
    De plus le $\text{PGCD}$ de $4a+3b$ et $5a+4b$ divise celui de $a$ et $b$. On a donc $\text{PGCD}(a;b) \pg \text{PGCD}(4a+3b;5a+4b)$.
    Ainsi les deux $\text{PGCD}$ sont égaux.
    $\quad$

[collapse]