Utiliser l’algorithme d’Euclide pour trouver le $\text{PGCD}$ des nombres suivants :
$360$ et $2~100$
$\quad$
$468$ et $312$
$\quad$
$700$ et $840$
$\quad$
$300$ et $350$
$\quad$
$168$ et $2~160$
$\quad$
$308$ et $364$
$\quad$
$1~105$ et $462$
$\quad$
$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$
$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$
$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$
$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$
$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$
$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$
$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$
Trouver 2 nombres entiers naturels $a$ et $b$ dont le $\text{PGCD}$ est $4$ tels que $a + b = 48$.
$\quad$
$\quad$
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$
Soit $n\in \mathbb{N}$ , quand on divise $169$ et $267$ par $n$, on obtient le même reste $15$ .
Démontrer que $n$ est un diviseur commun à $154$ et $252$.
$\quad$
Quelle est la plus grande valeur possible pour $n$ ?
$\quad$
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$
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$
Déterminer deux entiers naturels $a$ et $b$ sachant que leur $\text{PGCD}$ est $9$ et leur somme $72$.
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)$.
Déterminer deux entiers naturels $a$ et $b$ sachant que leur $\text{PGCD}$ est $17$ et leur produit $1~734$.
$\quad$
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$.
Ainsi par symétrie, les solutions sont les couples $(17;102)$, $(34;51)$, $(51;34)$ et $(102;17)$.
$\quad$
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$
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’\leq 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)$.
$a$ et $b$ sont deux entiers naturels premiers entre eux tels que $a^2 + a = 7 b^3$ .
Justifier que $a$ et $b^3$ sont premiers entre eux.
$\quad$
Démontrer que $a$ divise $7$. Trouver les valeurs de $a$ et $b$ vérifiant les hypothèses.
$\quad$
$a$ est premier avec $b$, il est donc également premier avec $b^2=b\times b$ et $b^3=b^2\times b$.
$\quad$
$a^2+a=7b^3\Leftrightarrow 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$
Soit $n \in \mathbb{N}$ tel que en divisant $n$ par $567$ et $407$, on obtient le même reste $60$.
Démontrer que $n-60$ est un multiple de $567$ et $407$.
$\quad$
Quelle est la plus petite valeur de $n$ possible? (On utilise le $\text{PPCM}$ dans cette question.)
$\quad$
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$.
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$
Résoudre dans $\mathbb{N}\times \mathbb{N}$ le système : $$\begin{cases} x^2-y^2=5~440\\\text{PGCD}(x,y)=8\end{cases}$$
$\quad$
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}\Leftrightarrow \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}\Leftrightarrow \begin{cases} x’=11\\y’=-6\end{cases}$ ce qui est impossible puisque $y’\geq 1$.
$\quad$
$ \begin{cases}x’-y’=1\\x’+y’=85\end{cases}\Leftrightarrow \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’\geq 1$.
Ainsi les seuls couples solutions sont $(88;48)$ et $(344;336)$.
On considère deux entiers naturels $a$ et $b$ , $A= 11 a +2 b$ et $B = 18 a +5 b$.
Démontrer que si un des nombres $A$ ou $B$ est divisible par $19$ , alors l’autre aussi.
$\quad$
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$
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$
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$