Arithmétique
A SAVOIR: le cours sur l'arithmétique
Exercice 6
Soit $a$ un entier relatif et $n$ un entier naturel au moins égal à 2.
Par définition, $a$ admet un inverse modulo $n$ si et seulement si il existe un entier relatif $b$ tel que $ab≡1$ $[n]$.
Le relatif $b$ est alors un inverse de $a$ modulo $n$.
- Montrer, à l'aide du théorème de Bézout, que 28 et 15 sont premiers entre eux.
- Déterminer un inverse de 28 modulo 15.
- Résoudre l'équation (E) $28x≡9$ $[15]$ en utilisant l'inverse de 28 modulo 15.
- En procédant comme précédemment, résoudre l'équation (2) $14x≡5$ $[9]$
Corrigé
Clique ICI pour revoir le cours sur le PGCD.
- On a: $28u+15v=1$ $⇔$ $u={1}/{28}(1-15v)$
On utilise le tableau de valeurs de la calculatrice avec la fonction $f(x)={1}/{28}(1-15x)$ pour des $x$ entiers relatifs.
On recherche un $x$ pour lequel $f(x)$ est entier. On trouve, par exemple: $x=15$, qui donne $f(15)=-8$.
Par conséquent: si $u=-8$ et $v=15$, alors: $28u+15v=1$
Donc, d'après le théorème de Bézout, 28 et 15 sont premiers entre eux. -
On a vu précédemment que: $28×(-8)+15×15=1$.
Donc on a: $28×(-8)=15×(-15)+1$.
Et comme $0≤1 < 15$, cela prouve que: $28×(-8)≡1$ $[15]$.
Un inverse de 28 modulo 15 est donc $-8$. -
Résolvons l'équation (E) $28x≡9$ $[15]$
(E) $⇔$ $28×(-8)×x≡9×(-8)$ $[15]$ $⇔$ $-224x≡-72$ $[15]$
Or, comme $28×(-8)≡1$ $[15]$, on a: $28×(-8)×x≡1×x$ $[15]$, soit: $-224x≡x$ $[15]$
Et par là, on obtient: (E) $⇔$ $x≡-72$ $[15]$
Soit: (E) $⇔$ $x≡3$ $[15]$
Les solutions cherchées sont donc les nombres de la forme $15k+3$ (où $k$ est un entier relatif).
On peut aussi écrire: $S=\{15k+3, k∈ℤ\}$ - Résolvons l'équation (2) en 3 étapes.
Etape 1 .
On a: $14u+9v=1$ $⇔$ $u={1}/{14}(1-9v)$
On utilise le tableau de valeurs de la calculatrice avec la fonction $f(x)={1}/{14}(1-9x)$ pour des $x$ entiers relatifs.
On recherche un $x$ pour lequel $f(x)$ est entier. On trouve, par exemple: $x=11$, qui donne $f(11)=-7$.
Par conséquent: si $u=-7$ et $v=11$, alors: $14u+9v=1$
Donc, d'après le théorème de Bézout, 14 et 9 sont premiers entre eux.
Etape 2 .
Comme $14×(-7)+9×11=1$, on a: $14×(-7)=9×(-11)+1$.
Et comme $0≤1 < 9$, cela prouve que: $14×(-7)≡1$ $[9]$.
Un inverse de 14 modulo 9 est donc $-7$.
Etape 3 .
Résolvons l'équation (2) $14x≡5$ $[9]$
(2) $⇔$ $14×(-7)×x≡5×(-7)$ $[9]$ $⇔$ $-98x≡-35$ $[9]$
Or, comme $14×(-7)≡1$ $[9]$, on a: $14×(-7)×x≡1×x$ $[9]$, soit: $-98x≡x$ $[9]$
Et par là, on obtient: (2) $⇔$ $x≡-35$ $[9]$
Soit: (2) $⇔$ $x≡1$ $[9]$
Les solutions cherchées sont donc les nombres de la forme $9k+1$ (où $k$ est un entier relatif).
On peut aussi écrire: $S=\{9k+1, k∈ℤ\}$