Divisibilité et algorithme d'Euclide

Calculer $\text{pgcd}(48,18)$ par l'algorithme d'Euclide.

$48=18\times2+12$. $18=12\times1+6$. $12=6\times2+0$. $\text{pgcd}=6$.

Vrai ou faux : $6\mid42$.

$42=6\times7$. Donc $6\mid42$.

Donner la division euclidienne de $100$ par $7$.

$7\times14=98$, $100-98=2$. Donc $100=7\times14+2$ avec $0\leq2<7$.

Vrai ou faux : $\text{pgcd}(a,b)=\text{pgcd}(b,a\bmod b)$.

Vrai. C'est la propriété fondamentale de l'algorithme d'Euclide. Si $a=bq+r$, alors tout diviseur commun de $a,b$ est diviseur commun de $b,r$ et vice versa.

Quel est $\text{ppcm}(12,8)$ ?

$\text{pgcd}(12,8)=4$. $\text{ppcm}=12\times8/4=96/4=24$.

Trouver les coefficients de Bézout pour $\text{pgcd}(35,12)$.

Euclide : $35=12\times2+11$, $12=11\times1+1$, $11=1\times11$.

Remontée (Bézout) :
$1=12-11\times1=12-(35-12\times2)=12\times3-35\times1$.

Donc $35\times(-1)+12\times3=1$. Coefficients : $u=-1$, $v=3$.

Vérification : $-35+36=1$ ✓.

Vrai ou faux : Si $\text{pgcd}(a,b)=1$ et $a\mid bc$, alors $a\mid c$ (lemme de Gauss).

Vrai. C'est le lemme de Gauss. Preuve : $\text{pgcd}(a,b)=1\Rightarrow\exists u,v:au+bv=1$. Multipliant par $c$ : $auc+bvc=c$. Comme $a\mid auc$ et $a\mid bc$ (donc $a\mid bvc$), on a $a\mid c$.

Calculer $\text{pgcd}(2^{10}-1, 2^{15}-1)$.

Propriété : $\text{pgcd}(2^m-1,2^n-1)=2^{\text{pgcd}(m,n)}-1$.

$\text{pgcd}(10,15)=5$.

Donc $\text{pgcd}(2^{10}-1,2^{15}-1)=2^5-1=31$.

Vrai ou faux : Il existe une infinité de nombres premiers.

Vrai. Preuve d'Euclide : supposons une liste finie $p_1,\ldots,p_k$. Alors $N=p_1\cdots p_k+1$ n'est divisible par aucun $p_i$ (reste $1$). Donc $N$ a un facteur premier non dans la liste : contradiction.

Résoudre $7x\equiv1\pmod{11}$ (trouver l'inverse de $7$ mod $11$).

Euclide : $11=7\times1+4$, $7=4\times1+3$, $4=3\times1+1$.

Bézout : $1=4-3=4-(7-4)=2\times4-7=2(11-7)-7=2\times11-3\times7$.

Donc $7\times(-3)+11\times2=1$, soit $7\times(-3)\equiv1\pmod{11}$.

$-3\equiv8\pmod{11}$. Donc l'inverse de $7$ mod $11$ est $8$. Vérif : $7\times8=56=55+1=5\times11+1\equiv1$ ✓.

Montrer que $\text{pgcd}(n,n+1)=1$ pour tout $n\in\mathbb{N}$.

Preuve :

Soit $d=\text{pgcd}(n,n+1)$. Alors $d\mid n$ et $d\mid(n+1)$.

Donc $d\mid[(n+1)-n]=1$.

Comme $d\geq1$ et $d\mid1$, on a $d=1$. $\square$

Vrai ou faux : $p$ premier et $p\mid ab$ $\Rightarrow$ $p\mid a$ ou $p\mid b$.

Vrai. C'est la propriété fondamentale des nombres premiers (Euclide). Si $p\nmid a$, alors $\text{pgcd}(p,a)=1$ (car $p$ est premier), et par le lemme de Gauss $p\mid b$.

Résoudre l'équation diophantienne $15x+21y=6$.

$\text{pgcd}(15,21)=3\mid6$ : l'équation admet des solutions.

On divise par $3$ : $5x+7y=2$.

Bézout : $7\times3-5\times4=21-20=1$, donc $7\times6-5\times8=2$. Solution particulière : $x_0=-8$, $y_0=6$.

Solution générale : $x=-8+7k$, $y=6-5k$, $k\in\mathbb{Z}$ (les $7=15/3$ et $5=21/3$).

Montrer que tout entier $n\geq2$ admet un facteur premier.

Preuve par descente infinie :

Si $n$ est premier, c'est lui-même son facteur premier.

Sinon $n=ab$ avec $1<a<n$. L'entier $a$ est $\geq2$. Par récurrence (ou descente sur des diviseurs strictement plus petits), $a$ admet un facteur premier $p$. Alors $p\mid a$ et $a\mid n$, donc $p\mid n$. $\square$

Vrai ou faux : L'algorithme d'Euclide a une complexité $O(\log(\min(a,b)))$ étapes.

Vrai. Par le lemme de Lamé : le nombre d'étapes est $\leq5\log_{10}(\min(a,b))+1$. En pratique on montre que les restes diminuent d'au moins moitié tous les deux pas, donnant $O(\log_\phi(\min(a,b)))$ (lié aux nombres de Fibonacci).