Arithmétique

Théorèmes de Bézout et de Gauss

Exercice 1

Déterminer tous les entiers relatifs $m$ et $n$ tels que:

$63 m = 91 n$
$\quad$
$208 m = 390 n$
$\quad$

Correction Exercice 1

$\text{PGCD}(63;91)=7$.
Par conséquent $63m=91n\ssi 9m=13n$.
$9$ et $13$ sont premiers entre eux. D’après le théorème de Gauss, $9$ divise $n$.
Il existe donc un entier relatif $k$ tel que $n=9k$.
Ainsi $9m=13\times 9k \ssi m=13k$.
$\quad$
Réciproquement, soit $k\in \Z$. Prenons $m=13k$ et $n=9k$. $m$ et $n$ sont des entiers relatifs.
On a de plus $63m=819k$ et $91n=819k$.
Donc $(m;n)$ est solution de l’équation $63m=91n$.
$\quad$
L’ensemble solution de l’équation $63m=91n$ est $\acco{(13k;9k),~\forall k\in \Z}$.
$\quad$
$\text{PGCD}(208;390)=26$.
Par conséquent $208m=390n\ssi 8m=15n$.
$8$ et $15$ sont premiers entre eux. D’après le théorème de Gauss, $8$ divise $n$.
Il existe donc un entier relatif $k$ tel que $n=8k$.
Ainsi $8m=15\times 8k \ssi m=15k$.
$\quad$
Réciproquement, soit $k\in \Z$. Prenons $m=15k$ et $n=8k$. $m$ et $n$ sont des entiers relatifs.
On a de plus $208m=3~120k$ et $390n=3~120k$.
Donc $(m;n)$ est solution de l’équation $208m=390n$.
$\quad$
L’ensemble solution de l’équation $208m=390n$ est $\acco{(15k;8k),~\forall k\in \Z}$.
$\quad$

[collapse]

$\quad$

Exercice 2

Trouver deux entiers $a$ et $b$ dont le $\text{PGCD}$ est $21$ et vérifiant $99 a-165 b = 0$.

$\quad$

Correction Exercice 2

$\text{PGCD}(99;165)=33$ par conséquent $99a-165b=0\ssi 3a=5b$.
$3$ et $5$ sont premiers entre eux. D’après le théorème de Gauss, $3$ divise $b$.
Il existe donc un entier relatif $k$ tel que $b=3k$.
On a alors $3a=15k \ssi a=5k$.
$\quad$
Ainsi, $\text{PGCD}(3k;5k)=k$ or $\text{PGCD}(5k;3k)=\text{PGCD}(a;b)=21$.
Donc $k=21$.

Ainsi $a=105$ et $b=63$.

$\quad$

[collapse]

$\quad$

Exercice 3

Soit $n$ un entier naturel. Prouver que $n(2n+1)(7n+1)$ est divisible par $6$.

$\quad$

Correction Exercice 3

Si $n$ est pair alors $n(2n+1)(7n+1)$ est pair.
Si $n$ est impair alors $7n+1$ est pair et $n(2n+1)(7n+1)$ est pair.

$\quad$

Si $n\equiv 0~[3]$ alors $n(2n+1)(7n+1)$ est divisible
Si $n\equiv 1~[3]$ alors $2n+1\equiv 0~[3]$ et $n(2n+1)(7n+1)$ est divisible par $3$.
Si $n\equiv 2~[3]$ alors $7n+1\equiv 0~[3]$ et $n(2n+1)(7n+1)$ est divisible par $3$.

$n(2n+1)(7n+1)$ est divisible à la fois par $2$ et $3$ qui sont deux entiers premiers entre eux.
Par conséquent $n(2n+1)(7n+1)$ est divisible par $2\times 3=6$.

$\quad$

[collapse]

$\quad$

Exercice 4

Soit $n$ un entier naturel. Simplifier $A=2(5n+3)-5(2n+1)$.
Que peut-on en déduire pour les entiers $5n+3$ et $2n+1$?

$\quad$

Correction Exercice 4

$\begin{align*} A&=2(5n+3)-5(2n+1) \\
&=10n+6-10n-5 \\
&=1 \end{align*}$

D’après le théorème de Bézout, $5n+3$ et $2n+1$ sont premier entre eux.

$\quad$

[collapse]

$\quad$

Exercice 5

En utilisant l’égalité de Bézout, démontrer que $2n+1$ et $9n+4$ sont premiers entre eux pour tout $n\in \Z$.

$\quad$

Correction Exercice 5

Soit $n\in \Z$.

$\begin{align*}9(2n+1)-2(9n+4)&=18n+9-18n-8 \\
&=1\end{align*}$

D’après le théorème de Bézout, $2n+1$ et $9n+4$ sont premiers entre eux.

$\quad$

[collapse]

$\quad$

Exercice 6

Déterminer un couple d’entier $(x;y)$ solution des équations suivantes :

$5x-3y=1$
$\quad$
$9x+12y=3$
$\quad$
$18x+25y=2$
$\quad$
$187x+78y=1$
$\quad$
$26x+65y=13$
$\quad$
$144x+625y=3$
$\quad$

Correction Exercice 6

$5=1\times 3+2$ et $3=1\times 2+1\ssi 2=3-1$
Par conséquent $5=3+3-1$ soit $2\times 3-5=1$.
Le couple $(-1;-2)$ est solution de l’équation $5x-3y=1$.
$\quad$
$9x+12y=3\ssi 3x+4y=1$.
Or $3\times (-1)+4\times 1=1$.
Le couple $(-1;1)$ est solution de l’équation $9x+12=3$.
$\quad$
$\text{PGCD}(18;25)=1$. On cherche tout d’abord une solution particulière de l’équation $18x+25y=1$.
$25=18+7$ $\quad$ $18=2\times 7+4$ $\quad$ $7=4+3$ $\quad$ $4=3+1$
Donc :
$\begin{align*} 1=4-3&\ssi 1=4-(7-4)\\
&\ssi 1=2\times 4-7 \\
&\ssi 1=2(18-2\times 7)-7\\
&\ssi 1=2\times 18-5\times 7\\
&\ssi 1=2\times 18-5(25-18)\\
&\ssi 1=7\times 18-5\times 25\end{align*}$
Ainsi $(7;-5)$ est une solution particulière de l’équation $18x+25y=1$.
Donc $(14;-10)$ est une solution particulière de l’équation $18x+25y=2$.
$\quad$
$187=2\times 78+31$ $\quad$ $78=2\times 31+16$ $\quad$ $31=16+15$ $\quad$ $16=15+1$
Donc
$\begin{align*} 1&=16-15\\
&=16-(31-16) \\
&=2\times 16-31\\
&=2(78-2\times 31)-31\\
&=2\times 78-5\times 31 \\
&=2\times 78-5(187-2\times 78) \\
&=12\times 78-5\times 187\end{align*}$
Par conséquent $(-5;12)$ est une solution particulière de l’équation $187x+78y=1$.
$\quad$
$26x+65y=13\ssi 2x+5y=1$.
Or $2\times (-2)+5=1$
Une solution particulière de l’équation $26x+65y=13$ est donc $(-2;1)$.
$\quad$
$625=4\times 144+49$ $\quad$ $144=2\times 49+46$ $\quad$ $49=46+3$.
Donc
$\begin{align*}3&=49-46 \\
&=49-(144-2\times 49) \\
&=3\times 49-144 \\
&=3(625-4\times 144)-144 \\
&=3\times 625-13\times 144\end{align*}$
Une solution particulière de l’équation $144x+625y=3$ est $(-13;3)$.
$\quad$

[collapse]

$\quad$

Exercice 7

Appliquer l’algorithme d’Euclide aux $2$ entiers $a=41$ et $b=27$.
En déduire une solution particulière dans $\N^2$ de $41x-27y=1$.
$\quad$
En déduire une solution particulière dans $\N^2$ de $41x-27y=5$.
$\quad$
Résoudre dans $\Z^2$ l’équation $41x-27y=5$.
$\quad$

Correction Exercice 7

$41=27+14$ $\quad$ $27=14+13$ $\quad$ $14=13+1$
Donc :
$\begin{align*} 1&=14-13 \\
&=14-(27-14) \\
&=2\times 14-27 \\
&=2(41-27)-27\\
&=2\times 41-3\times 27\end{align*}$
Une solution particulière de l’équation $41x-27y=1$ est $(2;3)$.
$\quad$
Une solution particulière de l’équation $41x-27y=5$ est donc $(10;15)$.
$\quad$
Soit $(x;y)$ une solution de $41x-27y=5$.
On a également $41\times 10-27\times 15=5$.
Par soustraction, on obtient $41(x-10)-27(y-15)=0 \ssi 41(x-10)=27(y-15)$.
Or $41$ et $27$ sont premiers entre eux.
D’après le théorème de Gauss, il existe un entier relatif $k$ tel que $x-10=27k$ et $y-15=41k$.
Ainsi $x=10+27k$ et $y=15+41k$.
$\quad$
Réciproquement, soit $k\in \Z$. Prenons $x=10+27k$ et $y=15+41k$. $x$ et $y$ sont bien deux entiers relatifs.
$\begin{align*} 41x-27y&=41(10+27k)-27(15+41k) \\
&=410-1~107k-405-1~107k\\
&=5\end{align*}$
$\quad$
L’ensemble solution de l’équation $41x-27y=5$ est $\acco{(10+27k;15+41k),~\forall k\in \Z}$.
$\quad$

[collapse]

$\quad$

Exercice 8

En utilisant l’algorithme d’Euclide, trouver $2$ entiers $x$ et $y$ tels que $1~274x-275y=1$.
$\quad$
Déterminer tous les couples d’entiers naturels solutions de $1~274x-275y=3$.
$\quad$

Correction Exercice 8

$1~274=4\times 275+174$ $\quad$ $275=174+101$ $\quad$ $174=101+73$ $\quad$ $101=73+28$ $\quad$ $73=2\times 28+17$ $\quad$ $28=17+11$ $\quad$ $17=11+6$ $\quad$ $11=6+5$ $\quad$ $ 6=5+1$
Ainsi :
$\begin{align*}1&=6-5\\
&=2\times 6-11\\
&=2\times 17-3\times 11\\
&=5\times 17-3\times 28\\
&=5\times 73-13\times 28 \\
&=18\times 73-13\times 101\\
&=18\times 174-31\times 101\\
&=49\times 174-31\times 275\\
&=49\times 1~274-227\times 275\end{align*}$
Une solution particulière de l’équation $1~274x-275y=1$ est $(49;227)$.
$\quad$
Une solution particulière de l’équation $1~274x-275y=3$ est $(147;681)$.
Soit $(x,y)$ une autre solution de cette équation.
Par soustraction $1~274(x-147)-275(y-681)=0 \ssi 1~274(x-147)=275(y-681)$.
D’après la question précédente, $1~274$ et $275$ sont premiers entre eux.
D’après le théorème de Gauss, il existe un entier relatif $k$ tel que $x-147=275k$ et $y-681=1~274k$ soit $x=147+275k$ et $y=681+1~274k$.
Si $k<0$ alors $x<0$ et si $k\pg 0$ alors $(x,y)\in \N^2$.
$\quad$
Réciproquement, soit $k\in \N$. Posons $x=147+275k$ et $y=681+1~274k$.
$\begin{align*} 1~274x-275y&=1~274(147+275k)-275(681+1~274k) \\
&=187~278-187~275 \\
&=3\end{align*}$
$\quad$
L’ensemble solution de l’équation $1~274x-275y=3$ est $\acco{(147+275k,681+1~274k),~\forall k\in \N}$.
$\quad$

[collapse]

$\quad$

Exercice 9

On considère l’équation $(E):~8x+5y=1$ où $(x,y)$ est un couple d’entiers relatifs.

Donner une solution particulière de $(E)$.
$\quad$
Résoudre $(E)$.
$\quad$
Soit $N$ un entier naturel vérifiant $N=8a+1$ et $N=5b+2$.
Montrer que le couple $(a;-b)$ est solution de $(E)$.
$\quad$
Quel est le reste de la division euclidienne de $N$ par $40$?
$\quad$
Résoudre l’équation $8x+5y=100$ où $(x;y)$ est un couple d’entiers relatifs.
$\quad$
Un nombre d’hommes et de femmes a dépensé $100$ pièces de monnaie dans une auberge. Chaque homme a dépensé $8$ pièces et chaque femme $5$ pièces. Combien pouvait-il y avoir d’hommes et de femmes dans le groupe? (Donner toutes les solutions)
$\quad$

Correction Exercice 9

$8\times 2-5\times 3=1$ donc $(2;-3)$ est une solution particulière de $(E)$.
$\quad$
Soit $(x;y)$ une autre solution de $(E)$.
Par soustraction on a $8(x-2)+5(y+3)=0 \ssi 8(x-2)=5(-3-y)$
$5$ et $8$ sont premiers entre eux. D’après le théorème de Gauss, il existe un entier relatif $k$ tel que $x-2=5k$ et $-3-y=8k$ ainsi $x=2+5k$ et $y=-3-8k$.
$\quad$
Réciproquement, soit $k\in \Z$. Posons $x=2+5k$ et $y=-3-8k$.
$x$ et $y$ sont bien des entiers relatifs.
De plus :
$\begin{align*} 8x+5y&=8(2+5k)+5(-3-8k)\\
&=16-15 \\
&=1\end{align*}$
$\quad$
L’ensemble solution de $(E)$ est $\acco{(2+5k;-3-8k),~\forall k\in \Z}$.
$\quad$
On a $N=8a+1\ssi 8a=N-1$ et $N=5b+2\ssi 5b=N-2$ donc :
$\begin{align*} 8a+5(-b)&=N-1+2-N \\
&=1\end{align*}$
$(a;-b)$ est solution de $(E)$.
$\quad$
Il existe donc $k\in \Z$ tel que $a=2+5k$ et $-b=-3-8k$
Par conséquent :
$\begin{align*} N&=8a+1\\
&=16+40k+1 \\
&=17+40k\end{align*}$
Ainsi $n\equiv 17~[40]$.
$\quad$
$(200;-300)$ est une solution particulière de l’équation $8x+5y=100$.
Soit $(x;y)$ une autre solution de cette équation.
Par différence on obtient $8(x-200)+5(y+300)=0 \ssi 8(x-200)=5(-y-300)$.
$8$ et $5$ sont premiers entre eux. D’après le théorème de Gauss, il existe un entier relatif $k$ tel que $x-200=5k$ et $-y-300=8k$ soit $x=200+5k$ et $y=-300-8k$.
$\quad$
Réciproquement, soit $k\in\Z$ et posons $x=200+5k$ et $y=-300-8k$.
$x$ et $y$ sont bien des entiers relatifs.
De plus :
$\begin{align*} 8x+5y&=8(200+5k)+5(-300-8k)\\
&=1~600-1~500\\
&=100\end{align*}$
$\quad$
L’ensemble solution de $8x+5y=100$ est $\acco{(200+5k;-300-8k),~\forall k\in \Z}$.
$\quad$
On appelle $x$ le nombre d’hommes et $y$ le nombre de femmes.
On a donc $(x,y)\in \N^2$ et $8x+5y=100$.
D’après la question précédente, il existe $k\in \Z$ tel que $x=200+5k$ et $y=-300-8k$.
$\begin{align*} \begin{cases} x\pg 0\\y\pg 0\end{cases}&\ssi \begin{cases} 200+5k\pg 0\\-300-8k\pg 0\end{cases} \\
&\ssi \begin{cases} 5k\pg -200\\8k\pp -300 \end{cases} \\
&\ssi \begin{cases} k\pg -40\\k \pp -37,5\end{cases} \\
&\ssi k\in \acco{-40;-39;-38}\end{align*}$
Si $k=-40$ alors $x=0$ et $y=20$.
Si $k=-39$ alors $x=5$ et $y=12$.
Si $k=-38$ alors $x=10$ et $y=4$.
Il pouvait donc y avoir :
$\bullet$ $0$ homme et $20$ femmes;
$\bullet$ $5$ hommes et $12$ femmes;
$\bullet$ $10$ hommes et $4$ femmes.
$\quad$

[collapse]

$\quad$