Arithmétique dans l'ensemble des entiers relatifs

Si $a\mid b$ et $b\mid a$ avec $a,b$ non nuls, alors $|a|\le |b|$ et $|b|\le |a|$, d'où $|a|=|b|$. (Si l'un est nul, l'autre aussi.) La réciproque est immédiate.

Existence. L'ensemble $E=\{k\in \mathbb{Z}:kb\le a\}$ est non vide (il contient $-|a|$) et majoré (par $|a|$) : il admet un plus grand élément $q$. Alors $qb\le a<(q+1)b$, et $r=a-bq$ vérifie $0\le r<b$.

Unicité. Si $bq+r=b{q}^{\prime }+r^{\prime }$ avec $0\le r,r^{\prime }<b$, alors $b(q-q^{\prime })=r^{\prime }-r$, donc $b\mid r^{\prime }-r$ ; or $|r^{\prime }-r|<b$, ce qui force $r^{\prime }=r$, puis $q^{\prime }=q$.

Si $d\mid a$ et $d\mid b$, alors $d\mid a-bq=r$ ; si $d\mid b$ et $d\mid r$, alors $d\mid bq+r=a$. Les deux couples ont donc le même ensemble de diviseurs communs — et a fortiori le même plus grand élément.

Le premier point s'obtient en remontant l'algorithme d'Euclide : à chaque étape, l'ensemble des diviseurs communs est inchangé (lemme) ; à la fin, c'est l'ensemble des diviseurs du dernier reste non nul $a\wedge b$. Pour le second : en multipliant chaque division $a=bq+r$ par $k$, on obtient $ka=(kb)q+kr$ avec $0\le kr<kb$ — l'algorithme d'Euclide pour $(ka,kb)$ reproduit celui de $(a,b)$ multiplié par $k$, et le dernier reste non nul est $k(a\wedge b)$.

On remonte l'algorithme d'Euclide. Chaque reste s'écrit $r=a-bq$ : c'est une combinaison $au+bv$. Par récurrence descendante, si deux restes consécutifs $r_{k-1}$ et $r_k$ sont des combinaisons de $a$ et $b$, alors $r_{k+1}=r_{k-1}-q_k{r}_k$ aussi. Le dernier reste non nul, $a\wedge b$, est donc de la forme $au+bv$.

Le sens direct est la relation de Bézout. Réciproquement, si $au+bv=1$, tout diviseur commun $d$ de $a$ et $b$ divise la combinaison $au+bv=1$, donc $d=\pm 1$.

Par Bézout, $au+bv=1$ pour certains $u,v$. En multipliant par $c$ :

$$c=acu+bcv.$$

Or $a\mid acu$ (évident) et $a\mid bcv$ (car $a\mid bc$) : donc $a$ divise la somme $c$.

Premier point : écrivons $n=ak$. De $b\mid ak$ et $b\wedge a=1$, le lemme de Gauss donne $b\mid k$, soit $k=b{k}^{\prime }$ et $n=ab{k}^{\prime }$.

Second point : par Bézout, $au+nv=1$ et $b{u}^{\prime }+n{v}^{\prime }=1$. En multipliant ces deux égalités :

$$ab(u{u}^{\prime })+n(au{v}^{\prime }+b{u}^{\prime }v+nv{v}^{\prime })=1,$$

qui est une relation de Bézout entre $ab$ et $n$.

Par l'absurde : supposons qu'il n'y ait qu'un nombre fini de premiers $p_1,\dots ,p_r$, et posons

$$N=p_1{p}_2\cdots p_r+1.$$

$N\ge 2$ admet un diviseur premier $p$, qui est l'un des $p_i$. Mais alors $p$ divise $N$ et $p_1\cdots p_r$, donc leur différence $1$ — absurde. (Attention : $N$ lui-même n'est pas nécessairement premier ; la démonstration dit seulement que ses facteurs premiers sont « nouveaux ».)

Existence, par récurrence forte : c'est clair pour $n=1$ ; pour $n\ge 2$, soit $p$ son plus petit diviseur premier : $n=pm$ avec $m<n$, et on applique l'hypothèse de récurrence à $m$.

Unicité : supposons $p_1\cdots p_s=q_1\cdots q_t$ (premiers, avec répétitions). Le premier $p_1$ divise le produit des $q_j$ ; comme $p_1$ est premier à tout premier $q\ne p_1$, des applications répétées du lemme de Gauss montrent que $p_1$ est égal à l'un des $q_j$. On simplifie et on recommence : les deux listes coïncident.

$n$ divise $(b-a)+(d-c)=(b+d)-(a+c)$, d'où la somme. Pour le produit :

$$bd-ac=b(d-c)+c(b-a),$$

combinaison de multiples de $n$. Les puissances s'obtiennent par récurrence.

$au\equiv 1[n]$ signifie $au+nv=1$ pour un certain $v$ : c'est exactement une relation de Bézout, qui existe si et seulement si $a\wedge n=1$. Unicité : si $au\equiv a{u}^{\prime }\equiv 1[n]$, alors $u^{\prime }\equiv u^{\prime }(au)\equiv (u^{\prime }a)u\equiv u[n]$.

Supposons $p\nmid a$, c'est-à-dire $a\wedge p=1$. Considérons les $p-1$ entiers $a,2a,3a,\dots ,(p-1)a$. Modulo $p$, ils sont deux à deux distincts : si $ka\equiv k^{\prime }a[p]$, alors $p\mid (k-k^{\prime })a$, et comme $p\wedge a=1$, le lemme de Gauss donne $p\mid k-k^{\prime }$, donc $k=k^{\prime }$ (car $|k-k^{\prime }|<p$). Aucun n'est nul modulo $p$ (même argument). Ces $p-1$ restes sont donc une permutation de $1,2,\dots ,p-1$. En multipliant tout :

$$a^{p-1}(p-1)!\equiv (p-1)![p].$$

Or $(p-1)!$ est premier avec $p$ (produit d'entiers premiers à $p$) : on peut simplifier (multiplier par son inverse), d'où $a^{p-1}\equiv 1[p]$. Le cas général $a^p\equiv a$ s'en déduit en multipliant par $a$ (et il est trivial si $p\mid a$).

Le chiffre des unités est le reste modulo $10$. Calculons les premières puissances de $7$ modulo $10$ :

$$7^1\equiv 7,7^2=49\equiv 9,7^3\equiv 9\times 7=63\equiv 3,7^4\equiv 3\times 7=21\equiv 1[10].$$

Les restes sont périodiques de période $4$. Comme $2026=4\times 506+2$ :

$$7^{2026}={\left(7^4\right)}^{506}\times 7^2\equiv 1^{506}\times 9=9[10]:$$

le chiffre des unités est $\boxed{9}$.

$$1071=2\times 462+147,462=3\times 147+21,147=7\times 21+0.$$

Le dernier reste non nul est $21$ : $1071\wedge 462=21$. En divisant numérateur et dénominateur par $21$ :

$$\frac{462}{1071}=\frac{22}{51},$$

et $22\wedge 51=1$ : la fraction est irréductible.

$360=2^3\cdot 3^2\cdot 5$ et $84=2^2\cdot 3\cdot 7$. En prenant le $\min$ puis le $\max$ des valuations :

$$360\wedge 84=2^2\cdot 3=12,360\vee 84=2^3\cdot 3^2\cdot 5\cdot 7=2520.$$

Vérification : $12\times 2520=30240$ et $360\times 84=30240$. ✓

Euclide : $31=2\times 13+5$, $13=2\times 5+3$, $5=1\times 3+2$, $3=1\times 2+1$, $2=2\times 1$. Donc $13\wedge 31=1$. Remontée :

$$\begin{array}{rl}1& =3-2=3-(5-3)=2\times 3-5\\ & =2(13-2\times 5)-5=2\times 13-5\times 5\\ & =2\times 13-5(31-2\times 13)=12\times 13-5\times 31.\end{array}$$

Vérification : $12\times 13-5\times 31=156-155=1$. ✓ Ainsi $13\times 12\equiv 1[31]$ : l'inverse de $13$ modulo $31$ est $\boxed{12}$.

Comme $17\wedge 40=1$ divise $5$, l'équation a des solutions. Du couple de Bézout $17\times (-7)+40\times 3=1$, on tire (en multipliant par $5$) la solution particulière $(x_0,y_0)=(-35,15)$.

Soit $(x,y)$ une autre solution : par différence, $17(x+35)=-40(y-15)$. Donc $40\mid 17(x+35)$ ; comme $40\wedge 17=1$, le lemme de Gauss donne $40\mid x+35$, soit $x=-35+40k$, puis $y=15-17k$. Réciproquement, ces couples conviennent :

$$\boxed{(x,y)=(-35+40k,15-17k),k\in \mathbb{Z}.}$$

Remarquons que $n(n^2+5)=n(n^2-1)+6n=(n-1)n(n+1)+6n$. Le second terme est divisible par $6$. Le premier est un produit de trois entiers consécutifs : parmi eux, l'un est pair et l'un est multiple de $3$, donc $2\mid (n-1)n(n+1)$ et $3\mid (n-1)n(n+1)$. Comme $2\wedge 3=1$, leur produit $6$ divise $(n-1)n(n+1)$. D'où $6\mid n(n^2+5)$.

$13$ est premier et $13\nmid 2$ : Fermat donne $2^{12}\equiv 1[13]$. Divisons l'exposant par $12$ : $2026=12\times 168+10$, donc

$$2^{2026}={\left(2^{12}\right)}^{168}\times 2^{10}\equiv 2^{10}=1024[13].$$

Enfin $1024=78\times 13+10$ : le reste est $\boxed{10}$.

Supposons $\sqrt{n}=\frac{a}{b}$ avec $a,b\in {\mathbb{N}}^{\ast }$. Alors $n{b}^2=a^2$. Prenons la valuation $p$-adique pour un premier $p$ quelconque :

$$v_p(n)+2v_p(b)=2v_p(a),\text{d’ouˋ}{v}_p(n)=2(v_p(a)-v_p(b)).$$

Toute valuation de $n$ est donc paire (et positive). En posant $m=\prod p^{v_p(n)/2}$, on obtient $n=m^2$ : $n$ est un carré parfait. (Pour $n=2$ : $v_2(2)=1$ est impaire, on retrouve l'irrationalité de $\sqrt{2}$ — la machinerie des valuations donne le résultat général sans effort supplémentaire.)

Par contraposée : supposons $n=de$ avec $1<d<n$. La factorisation $x^e-1=(x-1)(x^{e-1}+\cdots +x+1)$ appliquée à $x=2^d$ donne :

$$2^n-1={\left(2^d\right)}^e-1=\left(2^d-1\right)\left(2^{d(e-1)}+\cdots +2^d+1\right).$$

Or $1<2^d-1<2^n-1$ : c'est un diviseur strict non trivial, donc $2^n-1$ est composé.

Réciproque fausse : $2^{11}-1=2047=23\times 89$ alors que $11$ est premier. Les premiers de la forme $2^p-1$ sont les nombres de Mersenne ; les plus grands nombres premiers connus sont de cette forme.

La première condition s'écrit $x=2+7k$, $k\in \mathbb{Z}$. Reportons dans la seconde :

$$2+7k\equiv 5[9]⟺7k\equiv 3[9].$$

Inversons $7$ modulo $9$ : $7\times 4=28=3\times 9+1\equiv 1[9]$, donc $7^{-1}\equiv 4$, et

$$k\equiv 4\times 3=12\equiv 3[9],k=3+9m.$$

D'où $x=2+7(3+9m)=23+63m$ :

$$\boxed{x\equiv 23[63].}$$

Vérification : $23=3\times 7+2$ ✓ et $23=2\times 9+5$ ✓. (Comme $7\wedge 9=1$, la solution est unique modulo $7\times 9=63$ : c'est le « théorème des restes chinois », ici retrouvé à la main.)