PGCD, équation de Bézout et congruences modulo 7

1. On donne les nombres $a=960$ et $b=528$.

En utilisant une composition de chaque nombre en produit de facteurs premiers, nous devons montrer que le $PGCD(a;b)=48$.

En effet, nous obtenons :

$\left\lbrace\begin{matrix} a=960=2^6\times3\times5\\ b=528=2^4\times3\times11 \end{matrix}\right.\quad\Longrightarrow\quad PGCD(a;b)=2^4\times3$

$\phantom{\left\lbrace\begin{matrix} a=960=2^6\times3\times5 \end{matrix}\right.}\quad\Longrightarrow\quad PGCD(a;b)=16\times3$

$\phantom{\left\lbrace\begin{matrix} a=960=2^6\times3\times5 \end{matrix}\right.}\quad\Longrightarrow\quad \boxed{PGCD(a;b)=48}$

2. On veut déterminer l'ensemble des couples $(u;v)$ d'entiers relatifs tels que:

$(E):au+bv=PGCD(a;b)$

2. a) Nous devons écrire l'équation $(E)$.

Rappelons le théorème de Bachet-Bézout :

Soient $a$ et $b$, deux entiers relatifs non nul.
Il existe un couple d'entiers relatifs $(u\;;\;v)$ tel que $au+bv=PGCD(a,b)$.

Dans cet exercice, $a=960,\,b=528$ et $PGCD(a;b)=48$.
Donc l'équation $(E)$ est $\boxed{(E):960u+528v=48}$

2. b) Nous devons vérifier que le couple $(u_0\;;\;v_0)=(5\;;\;-9)$ est solution de l'équation $(E)$.

En effet,

$960,u_0+528,v_0=960\times5+528\times(-9)$
$\phantom{960,u_0+528,v_0}=4800-4752$
$\phantom{960,u_0+528,v_0}=48$

$\Longrightarrow\quad\boxed{960,u_0+528,v_0=48}$

Par conséquent, le couple $(u_0\;;_;v_0)=(5\;;\;-9)$ est solution de l'équation $(E)$.

2. c) Nous devons montrer que l'équation $(E)$ est équivalente à l'équation $(E')\text{ : }20u+11v=1$.

$(E):960u+528v=48\quad\Longleftrightarrow\quad (E):48\times20u+48\times11v=48$
$\phantom{(E):960u+528v=48}\quad\Longleftrightarrow\quad (E):48(20u+11v)=48$
$\phantom{(E):960u+528v=48}\quad\Longleftrightarrow\quad (E'):20u+11v=1$

D'où $\boxed{(E):960u+528v=48\quad\Longleftrightarrow\quad (E'):20u+11v=1}$.

2. d) Nous devons résoudre l'équation $(E'')\text{ : }20u+11v=0$.

$20u+11v=0\quad\Longleftrightarrow\quad 20u=-11v$

Donc l'entier $20$ divise le produit $11v$.
Or $20$ et $11$ sont premiers entre eux.
Par le théorème de Gauss, nous en déduisons que $20$ divise $v$.

Dès lors, il existe un entier relatif $k$ tel que $\boxed{v=20k}$.

De plus,

$\left\lbrace\begin{matrix} 20u=-11v\\ v=20k \end{matrix}\right.\quad\Longrightarrow\quad20u=-11\times20k$
$\phantom{\left\lbrace\begin{matrix} 20u=-11v \end{matrix}\right.}\quad\Longrightarrow\quad \boxed{u=-11k}$

Donc, il existe un entier relatif $k$ tel que $\left\lbrace\begin{matrix} u=-11k\\ v=20k \end{matrix}\right.$.

Montrons que le couple $(-11k\;;\;20k)$ est solution de $(E'')$ pour tout entier relatif $k$.

En effet, $20\times(-11k)+11\times20k=-220k+220k=0$.

Par conséquent, l'ensemble des solutions de l'équation $(E'')$ est
$\boxed{S=\lbrace(-11k\,;\,20k)\,/ k\in\Z\rbrace}$.

2. e) Nous devons déduire de ce qui précède, les solutions de l'équation $(E)$.

La solution de l'équation $(E)$ est de la forme
$(u\,;_;v)=(u_0-11k\;;\;v_0+20k)$ avec $k\in\Z$.

Par conséquent, l'ensemble des solutions de l'équation $(E)$ est
$\boxed{S=\lbrace(5-11k\,;\,-9+20k)\,/\,k\in\Z\rbrace}$.

3. a) Nous devons montrer que l'équation $(E_1):18x-31\equiv 0,[7]$ est équivalente à $(E_2)\text{ : }4x\equiv 3\,[7]$.

$18x-31\equiv 0\,[7]\quad\Longleftrightarrow\quad 18x\equiv 31\,[7]$

Or $18[7]=4$ car $18=2\times7+4$
et $31[7]=3$ car $31=4\times7+3$.

Donc en réduisant l'équation $18x\equiv 31\,[7]$ aux restes, nous obtenons :
$4x\equiv3\,[7]$.

Par conséquent, l'équation $(E_1):18x-31\equiv 0,[7]$ est équivalente à $(E_2)\text{ : }4x\equiv 3\,[7]$.

3. b) En utilisant le tableau ci-dessous, nous devons déterminer l'ensemble des solutions de $(E_1)$.

$\begin{array}{|c|l|l|l|l|l|l|l|}\hline x &0&1&2&3&4&5&6\\ \hline 4x &0&4&1&5&2&6&3\\\hline \end{array}$

La dernière colonne du tableau nous indique que l'ensemble des solutions de $(E_1)$ est l'ensemble des entiers égaux à $6$ modulo $7$.

Par conséquent, l'ensemble des solutions de $(E_1)$ est
$\boxed{S=\lbrace6+7k\,;\,k\in\Z\rbrace}$.