Un cours d’arithmétique complet pour la licence ou la sup

Groupes et Arithmétique : Chapitres choisis

Construction de ${ \mathbb Z}$ à partir de ${\mathbb N}$

En supposant connues les propriétés élémentaires de l’ensemble ${\mathbb N}$ et de l’addition des entiers naturels, nous allons donner une construction rigoureuse de ${ \mathbb Z}$ et de l’addition des entiers relatifs. Dans cette construction, ${ \mathbb Z}$ apparaı̂tra sous forme d’un quotient de ${\mathbb N}\times{\mathbb N}$ par une relation d’équivalence. Ce paragraphe est aussi l’occasion de rappeler les notions de relation d’équivalence et d’ensemble quotient, notions centrales pour le reste du cours.

(relation sur $X$).

Soit $X$ un ensemble. Une relation sur $X$ est un ensemble $R\subset X\times X$ de couples d’éléments de $X$. On écrit $x R x'$ au lieu de $(x,x')\in R$. Une relation $R$ est une relation d’équivalence si elle est

réflexive (i.e. pour tout $x\in X$, on a $x R x$)
symétrique (i.e. on a équivalence entre $x R x'$ et $x' R x$ quels que soient $x,x'\in X$)
transitive (i.e. les conditions $x R x'$ et $x' R x''$ impliquent que $x R x''$ quels que soient $x,x',x''\in X$)

Soit $V$ l’ensemble des villes de France. On définit une relation $R$ sur $V$ en déclarant que $v R v'$ signifie que $v$ et $v'$ se trouvent dans la même région. Il est facile de vérifier qu’il s’agit d’une relation d’équivalence.
Soit $X={\mathbb N}\times {\mathbb N}$ et définissons $R$ par \[(x,y) R (x',y') \Leftrightarrow x+y'= y+x'.\] Par exemple, on a $(0,1) R (1,2)$ et $(1,2) R (2,3)$. La réflexivité et la symétrie de $R$ résultent de la commutativité de l’addition des entiers positifs. Montrons que $R$ est transitive. En effet, par définition, les conditions $(x,y) R (x',y')$ et $(x',y') R (x'',y'')$ équivalent aux équations \[\begin{aligned} x+y' & = & y + x' \newline x' + y'' & = & y' + x''\end{aligned}\] En rajoutant la première à la seconde on obtient \[x+y'+x'+y'' = y+x'+y'+x''\] ou encore \[x+y''+(x'+y') = x'' + y + (x'+y').\] Or on sait que la loi d’addition sur ${\mathbb N}$ est régulière c’est-à-dire qu’une égalité $a+c=b+c$ implique $a=b$ quels que soient $a,b,c\in{\mathbb N}$. Il s’ensuit que $x+y''=x''+y$ c’est-à-dire que $(x,y) R (x'',y'')$. Notons que dans cette démonstration, nous avons utilisé l’associativité, la commutativité et la régularité de l’addition des entiers naturels.

(classe d’équivalence de $x$ par rapport à $R$).

Soit $X$ un ensemble et $R$ une relation d’équivalence sur $X$. Pour $x\in X$, on pose \[\mbox{ }^R\overline{x} = \{ x'\in X \;| \; x R x' \; \} \subset X\] et on appelle classe d’équivalence de $x$ par rapport à $R$ cette partie de $X$. Par définition, l’ensemble $X/R$ est formé des classes $\mbox{ }^R\overline{x}$ d’éléments $x\in X$. On appelle $X/R$ le quotient de $X$ par la relation d’équivalence $R$. On définit l’application quotient (=la projection canonique) $q : X \rightarrow X/R$ par $q(x)=\mbox{ }^R\overline{x}$. Une partie de $X$ est un système de représentants pour $R$ si elle contient un élément de chaque classe d’équivalence et un seul.

Dans l’exemple des villes de France (voir ci-dessus) la classe d’équivalence d’une ville $v$ est formée de toutes les villes qui se trouvent dans la même région que $v$. En particulier deux classes $\overline{v}$ et $\overline{v'}$ sont égales ssi $v$ et $v'$ se trouvent dans la même région. Les éléments de $V/R$ sont des ensembles de villes, deux villes étant regroupé dans un même ensemble ssi elles se trouvent dans la même région. On a donc une bijection \[X/R \stackrel{_\sim}{\rightarrow}\{\mbox{régions de France}\}\: , \; \overline{v} \mapsto \mbox{la région où se trouve v}.\] Il existe beaucoup de systèmes de représentants. Par exemple, l’ensemble $V_0$ formé des capitales des régions en est un. L’ensemble $V_1$ formé des villes les plus éloignées de la capitale dans leur région en est un autre.
Dans le cas de l’exemple $X={\mathbb N}\times {\mathbb N}$ et de la relation $R$ introduite ci-dessus on vérifie que $(x,y) R (x',y')$ si et seulement si l’une des deux conditions suivantes est remplie
- il existe $d\in{\mathbb N}$ tel que $x'=x+d$ et $y'=y+d$
- il existe $d\in{\mathbb N}$ tel que $x=x'+d$ et $y=y'+d$.
Ainsi, deux éléments appartiennent à une même classe d’équivalence si on peut passer de l’un à l’autre en ajoutant un même entier naturel aux deux coordonnées. Les classes sont donc des ‘parties diagonales’ du plan ${\mathbb N}\times{\mathbb N}$ :

Les-mathematiques.net

Il y a beaucoup de systèmes de représentants. Par exemple \[X_0 = \{0\}\times{\mathbb N}\cup {\mathbb N}\times\{0\} = \{ \ldots, (0,3), (0,2), (0,1), (0,0), (1,0), (2,0), \ldots \}\] en est un. On définit l’ensemble ${ \mathbb Z}_{ax}$ (${ \mathbb Z}$ axiomatique) comme étant l’ensemble quotient $({\mathbb N}\times{\mathbb N}) / R$.

(Propriété universelle de $X/R$).

Soit $X$ un ensemble, $R$ une relations d’équivalence sur $X$ et $f:X \rightarrow Y$ une application constante sur les classes d’équivalence par rapport à $R$ (c’est-á-dire qu’on a $f(x)=f(x')$ à chaque fois que $x R x'$). Alors il existe une application $g: X/R \rightarrow Y$ et une seule telle que $f=g\circ q$. Réciproquement, toute application de la forme $g\circ q$ est constante sur les classes d’équivalence.

Le lemme signifie que la règle $g(\overline{x})=f(x)$ définit une application $g:X/R \rightarrow Y$ si et seulement si on a $f(x)=f(x')$ quels que soient $x,x'\in X$ vérifiant $x R x'$.

On pose $g(\overline{x})=f(x)$. Il s’agit de vérifier que $f(x)$ est indépendant du représentant $x$ de la classe $\overline{x}$. Or si $x'$ en est un autre, c’est-à-dire que $\overline{x}=\overline{x'}$, alors par définition, on a $x R x'$ et donc $f(x)=f(x')$.

Il existe une application $g: { \mathbb Z}_{ax} \rightarrow{ \mathbb Z}$ et une seule telle que $g(\overline{(x,y)})=x-y$. En effet, si $(x,y)R(x',y')$ alors $x+y'=y+x'$ et donc $x-y=x'-y'$. L’application $g$ est bijective : En effet, elle est surjective car si $n\in{ \mathbb Z}$, on a $n=g(\overline{(n,0)})$ si $n\geq 0$ et $n=g(\overline{(0,-n)})$ si $n<0$. Elle est injective car si on a $x-y=x'-y'$, alors $x+y'=x'+y$ c’est-à-dire que $(x,y) R (x',y')$ et que $\overline{(x,y)}=\overline{(x',y')}$.

(Addition sur ${ \mathbb Z}_{ax}$).

Il existe une application \[{ \mathbb Z}_{ax} \times { \mathbb Z}_{ax} \rightarrow{ \mathbb Z}_{ax}\] et une seule telle que \[\overline{(a,b)} + \overline{(c,d)} = \overline{(a+c, b+d)}.\]

Il s’agit de montrer que $\overline{(a+c, b+d)}=\overline{(a'+c', b'+d')}$ si $(a,b) R (a',b')$ et $(c,d) R (c',d')$. Nous laissons au lecteur le soin de cette vérification.

(groupe).

Un groupe est un couple $(G, \star)$ formé d’un ensemble $G$ et d’une application \[\star : G\times G \rightarrow G \: , \;(g,h) \mapsto g\star h\] appelée la loi du telle que

la loi $\star$ est associative (i.e. on a $(x\star y)\star z= x\star(y\star z)$ quels que soient $x,y,z\in G$)
la loi $\star$ admet un élément neutre (i.e. il existe $e\in G$ tel que $x\star e = e\star x=x$ quel que soit $x\in G$)
tout élément $x$ de $G$ admet un inverse $x'$ pour la loi $\star$ (i.e. on a $x\star x'= e = x'\star x$)

Un $(G,\star)$ est commutatif si on a $x\star y = y \star x$ quels que soient $x,y\in G$.

Si les conditons a) et b) sont vérifiées, alors l’élément neutre $e$ est unique. En effet, soient $e$ et $e'$ deux éléments neutres. Alors on a $e=e\star e'$ (car $e'$ est neutre) et $e\star e'=e'$ (car $e$ est neutre) et donc $e=e'$.
Si les conditions a), b) et c) sont vérifiées, l’élément inverse $x'$ de la conditon c) est unique. En effet, supposons que $x'$ et $x''$ sont deux éléments inverses à $x$. Alors on a \[x'=x'\star e=x'\star(x\star x'')= (x'\star x)\star x'' = e\star x''=x''.\] On note $x^{-1}$ l’élement inverse de l’élément $x$.

Le couple $({\mathbb N}, +)$ vérifie a) et b) (pour $e=0$) mais non pas c) car l’équation $n+n'=0$ n’admet pas de solution $n'\in{\mathbb N}$ si $n>0$.
Le couple $({ \mathbb Z}_{ax}, +)$ est un groupe. En effet, on vérifie facilement l’associativité. L’élément neutre est la classe de $(0,0)$. L’inverse de la classe de $(a,b)$ est la classe de $(b,a)$ ! En effet, nous avons \[\overline{(a,b)}+\overline{(b,a)} = \overline{(a+b, a+b)} = \overline{(0,0)}.\]

(Propriété universelle de ${ \mathbb Z}_{ax}$).

Soit $\iota$ l’application \[\iota :{\mathbb N}\rightarrow{ \mathbb Z}_{ax}\: , \;n \rightarrow\overline{(n,0)}.\] On a $\iota(n+n')=\iota(n)+\iota(n')$ et si $\phi : {\mathbb N}\rightarrow G$ est une autre application de ${\mathbb N}$ vers un $G$ telle que $\phi(n+n')=\phi(n)\star \phi(n')$, alors il existe une application $\psi: { \mathbb Z}_{ax}\rightarrow G$ et une seule telle que a) $\psi\circ \iota = \phi$ et b) $\psi(x+x')=\psi(x)\star \psi(x')$ quels que soient $x,x'\in { \mathbb Z}_{ax}$.

On peut interpréter ce lemme en disant que ${ \mathbb Z}_{ax}$ (et donc ${ \mathbb Z}$) est le groupe universel contenant ${\mathbb N}$.

Il est immédiat que $\iota$ est additive. Supposons donnée une application $\phi$ comme dans l’énoncé. Définissons $f: {\mathbb N}\times{\mathbb N}\rightarrow G$ par $f((a,b))=\phi(a)\star\phi(b)^{-1}$. Montrons que $f$ induit une application ${ \mathbb Z}_{ax}\rightarrow G$, Supposons que $(a,b) R (a',b')$ et donc que $a+b'=b+a'$. Alors pour montrer que \[\phi(a)\phi(b)^{-1} = \phi(a') \phi(b')^{-1}\] il suffit de montrer que \[\phi(a)\phi(b)^{-1} \phi(b) \phi(b') = \phi(a') \phi(b')^{-1} \phi(b) \phi(b').\] En utilisant que $\phi(b)\phi(b')=\phi(b+b')=\phi(b')\phi(b)$ nous sommes ramenés à montrer que \[\phi(a)\phi(b')=\phi(a')\phi(b)\] ce qui est clair car $\phi(a)\phi(b')=\phi(a+b')$ et $\phi(a')\phi(b)=\phi(a'+b)$. Montrons l’unicité de $\psi$. En effet, si $\psi$ et $\psi'$ vérifient les hypothèses, nous avons \[\psi(\overline{(n,0)})=\psi\circ\iota(n)= \phi(n)=\psi'\circ\iota(n)= \psi'(\overline{(n,0)}).\] En outre, si $x'=\overline{(0,n)}$, alors $\psi(x')$ et $\psi'(x')$ sont tous les deux inverses de $\psi(x)=\psi'(x)$ où $x=\overline{(n,0)}$. Donc $\psi(x')=\psi'(x')$. Comme les $(0,n)$ et les $(n,0)$, $n\in{\mathbb N}$, forment un système de représentants des classes d’équivalence par rapport à $R$, il s’ensuit que $\psi=\psi'$.

La division euclidienne et ses conséquences

(division euclidienne).

Soient $a\in{ \mathbb Z}$ et $b\in{ \mathbb Z}\setminus \{0\}$. Alors il existe $q\in{ \mathbb Z}$ et $r\in\{0,1,\ldots, |b|-1\}$ tels que \[a=qb+r.\] En outre, $q$ et $r$ sont uniques.

Exemples. On a $15=2\times 7 + 1$ ce qui est une division euclidienne. On a aussi $-15=(-2)\times 7 + (-1)$ ce qui n’est pas une division euclidienne, car le reste d’une est positif, par définition. Par contre, $-15=(-3)\times 7+6$ est bien une.

On considère l’ensemble $R$ formé des entiers $a-p\,b$, où $p\in{ \mathbb Z}$. Puisque $b$ est non nul, l’ensemble $R$ contient des nombres positifs. Donc l’intersection $R\cap {\mathbb N}$ est non vide. Elle admet donc un élément minimal. Appelons $r$ cet élément et définissons $q$ par l’égalité $a-q\,b=r$. Montrons que $r<|b|$. Soit $\varepsilon$ le signe de $b$ ($\varepsilon=1$ si $b>0$ et $\varepsilon=-1$ si $b<0$). Si nous avions $r>|b|$, nous pourrions enlever $\varepsilon\,b$ des deux côtés de l’égalité $a-q\,b=r$ pour trouver un nombre \[r-\varepsilon\,b=a-(q+\varepsilon)b\] qui appartiendrait encore a $R\cap {\mathbb N}$ mais qui serait strictement inférieur à $r$. Contradiction. On a donc bien $r\in\{0,1,\ldots, |b|-1\}$. Montrons l’unicité. Si nous avons \[q\,b+r= a = q'\,b+r',\] alors $(q-q')\,b=r-r'$. Puisque $r$ et $r'$ sont positifs et strictement inférieurs à $|b|$, il s’ensuit que $|q-q'|\,|b| = |r-r'|< |b|$. Comme $|b|\neq 0$, nous avons $|q-q'|<1$. Or, $|q-q'|$ est un entier positif et donc $|q-q'|=0$ et $q=q'$. Par conséquent, nous avons aussi $r=a-q\,b=a-q'\,b=r'$.

(sous-groupe).

Soit $(G,*)$ un. Un sous-groupe de $(G,*)$ est une partie $H\subset G$ telle que

L’élément neutre $e$ de $G$ appartient à $H$.
On a $h * h'\in H$ quels que soient $h,h'\in H$.
On a $h^{-1}\in H$ quel que soit $h\in H$.

Si $H$ est une sous-groupe de $(G,*)$, on définit une loi $*_H: H \times H \rightarrow H$ par \[h *_H h' = h * h'.\] Il est clair que $(H, *_H)$ est un groupe.
Quel que soit le groupe $(G,*)$, les parties $G$ et $\{e\}$ sont toujours des sous-groupes.
Pour tout $n\in{ \mathbb Z}$, la partie \[n{ \mathbb Z}=\{ nx \; | \; x\in{ \mathbb Z}\}\] est un sous-groupe de $({ \mathbb Z},+)$. D’après le théorème ci-dessus, on obtient ainsi tous les sous-groupes de $({ \mathbb Z},+)$.

Tout $H$ de $({ \mathbb Z}, +)$ est de la forme $H=n{ \mathbb Z}$ pour un $n\in{ \mathbb Z}$ unique au signe près.

Si $H=\{0\}$, alors $H= 0{ \mathbb Z}$ et il n’y a rien à démontrer. Supposons donc que $H \neq \{0\}$. Alors l’ensemble dess $|x|>0$ d’éléments de $H$ est non-vide. Soit $n\in H$ tel que $|n|$ est non nul et minimal. Je dis que $H=n{ \mathbb Z}$. En effet, puisque $H$ est un qui contient $n$, il contient $n{ \mathbb Z}$. Réciproquement, soit $a\in H$ et soit $a=qn+r$ la de $a$ par $n$ (rappelons que $n\neq 0$). Si on avait $r\neq 0$, alors $r=q-qn$ serait un élément de $H$ non nul et de strictement inférieure à celle de $n$. Donc nous avons $r=0$ et $a=qn$ appartient à $n{ \mathbb Z}$.

Montrons l’unicité. En effet, si $n{ \mathbb Z}=n'{ \mathbb Z}$, nous avons $n= xn'$ pour un $x\in{ \mathbb Z}$ et $n'=x'n$ pour un $x'\in{ \mathbb Z}$. Donc $n=xx'n$. Nous avons soit $n=0$, et alors $n{ \mathbb Z}=\{0\}$ et $n'=0$, soit $n\neq 0$ et alors $1=xx'$ et donc $x=\pm 1$ et $n'=\pm n$.

Si $H$ et $H'$ sont deuxs de $({ \mathbb Z}, +)$, on pose \[H+H'=\{ x+x'\; | \; x\in H \mbox{ et } x'\in H'\}.\] On vérifie aussitôt que $H+H'$ est encore un de $({ \mathbb Z}, +)$. D’après le théorème, si $a$ et $b$ sont deux entiers, il existe un entier $c$ unique au signe près tel que \[a{ \mathbb Z}+ b{ \mathbb Z}= c{ \mathbb Z}.\] Nous allons voir que $c$ est en fait le plus grand commun diviseur de $a$ et $b$.

(divisible).

Soient $a,b\in{ \mathbb Z}$. On dit que $a$ est divisible par $b$ s’il existe $q\in{ \mathbb Z}$ tel que $a=q\,b$. Dans ce cas, on dit aussi que $a$ est multiple de $b$, que $b$ divise $a$ ou que $b$ est diviseur de $a$. On écrit $b|a$.

Le nombre $15$ est divisible par $1,3,5,15, -1,-3,-5$ et $-15$ !
Le nombre $0$ est divisible par tout entier. Par contre le nombre $1$ n’est divisible que par $1$ et $-1$. En effet, si on a $1=q b$, alors $1/|b|$ est un entier non nul et $\leq 1$. Donc $b=\pm 1$.
Supposons $b\neq 0$. Alors la division euclidienne de $a$ par $b$ est bien définie et $a$ est divisible par $b$ ssi le reste de la division euclidienne de $a$ par $b$ s’annule.

(plus grand diviseur commun).

Soient $a,b\in{ \mathbb Z}$ tels que $(a,b)\neq (0,0)$. Alors le module d’un diviseur commun à $a$ et $b$ est borné par $\max(|a|,|b|)$ et il existe donc un plus grand diviseur commun à $a$ et $b$. On le note $\mbox{PGCD}(a,b)$. Les nombres $a$ et $b$ sont premiers entre eux si $\mbox{PGCD}(a,b)=1$. Si $a=b=0$, on pose $\mbox{PGCD}(a,b)=0$.

(Bézout).

Soient $a,b\in{ \mathbb Z}$. Alors \[a\,{ \mathbb Z}+ b\,{ \mathbb Z}= \mbox{PGCD}(a,b) \,{ \mathbb Z}.\] En particulier, on a équivalence entre

Les entiers $a$ et $b$ sont premiers entre eux.
On a $a{ \mathbb Z}+ b{ \mathbb Z}= { \mathbb Z}$.
L’équation $ax + by =1$ admet une solution $(x,y)\in{ \mathbb Z}^2$.

L’équation $ax+by=1$ est dite équation de Bézout. Si $(a,b)\neq (0,0)$, elle admet toujours des solutions $(x,y)\in{\mathbb Q}^2$ mais pas nécessairement dans ${ \mathbb Z}^2$.
Il s’ensuit du lemme que tout diviseur commun $c$ de $a$ et $b$ divise $\mbox{PGCD}(a,b)$ (car il divise $ax+by$ quels que soient $x,y\in{ \mathbb Z}$).

Supposons que $a{ \mathbb Z}+b{ \mathbb Z}=c{ \mathbb Z}$ avec $c$ positif. Comme $a\in c{ \mathbb Z}$ et $b\in c{ \mathbb Z}$, le nombre $c$ est un diviseur commun de $a$ et $b$. Donc $c\leq \mbox{PGCD}(a,b)$. De l’autre côté, $\mbox{PGCD}(a,b)$ divise $a$ et $b$ et donc tout élément de $a{ \mathbb Z}+ b{ \mathbb Z}$. En particulier, $\mbox{PGCD}(a,b)$ divise $c$. Il s’ensuit que $c=\mbox{PGCD}(a,b)$.

Il est ainsi clair que i) est équivalent à ii). Il est aussi clair que i) implique iii). Réciproquement, si iii) est vérifié et $z\in{ \mathbb Z}$, il suffit de multiplier l’équation $ax+by=1$ par $z$ pour conclure que $z=a(zx)+b(zy)$ appartient à $a{ \mathbb Z}+b{ \mathbb Z}$ et donc que ${ \mathbb Z}=a{ \mathbb Z}+b{ \mathbb Z}$.

(Gauss).

Soient $a,b,c\in{ \mathbb Z}$. Si $a$ divise $bc$ et que $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

D’après le lemme de, il existe $x,y\in{ \mathbb Z}$ tels que $ax+by=1$. Nous multiplions cette ǵalité par $c$ pour obtenir \[acx+bcy=c.\] Puique $a$ divise $acx$ et $bcy$, il doit diviser $axc+bcy=c$.

(premier ).

Un nombre premier est un entier $>1$ dont les seuls diviseurs positifs sont $1$ et lui-même.

Le nombre $1$ n’est pas premier.
Les nombres $2,3,5 \ldots$ sont premiers.
Un nombre premier est un entier positif qui admet exactement deux diviseurs positifs.

(Euclide).

Soit $p$ un et $a,b\in{ \mathbb Z}$. Si $p$ divise $ab$ alors $p$ divise $a$ ou $p$ divise $b$.

Si $p$ ne divise pas $a$, alors $a$ et $p$ sont premiers entre eux, car les seuls diviseurs de $p$ sont $1$ et lui-même. D’après le lemme de, $p$ doit alors diviser $b$. De même, si $p$ ne divise pas $b$, il doit diviser $a$.

L’affirmation de ce lemme est fausse si on omet l’hypothèse que $p$ est premier. Par exemple le nombre $3\times 5$ divise le produit $(2\times 3)\times (5\times 7)$ mais il ne divise ni $2\times 3$ ni $5\times 7$.
Soient $p$ et $p_1, \ldots, p_r$ des nombres premiers. Montrons que si $p$ divise $p_1\cdots p_r$, alors $p=p_i$ pour un $i$. En effet, si $r=1$, il n’y a rien a démontrer. Si $r>1$, et que $p$ divise le produit $p_1\times (p_2\cdots p_r)$, alors d’après le lemme d’Euclide, $p$ divise $p_1$ ou $p$ divise $p_2\cdots p_r$. Dans le premier cas, nous avons $p=p_1$ et dans le second $p=p_i$ pour un $i\geq 2$, d’après l’hypothèse de récurrence.

(Décomposition en facteurs premiers).

Soit $n\geq 1$ un entier et soit $p_1, p_2 \ldots$ la liste des nombres premiers (exhaustive et sans répétitions). Alors il existe des entiers $m_i\in{\mathbb N}$ uniques et nuls sauf pour un nombre fini d’entre eux tels que \[n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots .\]

Comme presque tous les $m_i$ sont nuls, presque tous les facteurs dans l’écriture $p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots$ valent un. Il s’agit donc en effet d’un produit avec un nombre fini de facteurs.

Montrons l’existence de l’écriture par un raisonnement récursif : Si $n=1$, on pose $m_i=0$ pour tous les $i$. Si $n>1$ alors soit $n$ est premier, soit $n=n' n''$ pour deux nombres strictement inférieurs à $n$. Dans le premier cas, il existe un $p_j$ dans la liste et un seul tel que $n=p_j$. On pose $m_i=0$ pour $i\neq j$ et $m_j=1$. Dans le second cas, l’hypothèse de récurrence nous donne les écritures \[\begin{aligned} n' & = & p_1^{m'_1} p_2^{m'_2} \cdots \newline n'' & = & p_1^{m''_1} p_2^{m''_2} \cdots .\end{aligned}\] En multipliant nous trouvons \[n = p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots .\] Montrons l’unicité de l’écriture. Supposons donc que \[n = p_1^{m_1} p_2^{m_2} \cdots = p_1^{m'_1} p_2^{m'_2} \cdots .\] Montrons que $m_1=m'_1$ (la démonstration pour les autres $m_i$ est la même). Nous procédons par récurrence. Si $m_1=0$, alors $p$ ne divise pas $n$ (sinon il serait égal à l’un des $p_i$ d’après la remarque ci-dessus). Donc $m'_1=0$. Si $m_1>0$, alors $p_1$ divise $n$. D’après la remarque ci-dessus, $p_1$ doit apparaı̂tre dans l’écriture \[n = p_1^{m'_1} p_2^{m'_2} \cdots .\] Donc $m'_1>0$. En divisant par $p_1$ nous trouvons \[p_1^{m_1-1} p_2^{m_2} \cdots = p_1^{m'_1-1} p_2^{m'_2} \cdots .\] et par l’hypothèse de récurrence, il s’ensuit que $m_1-1=m'_1-1$. Donc $m_1=m'_1$.

Ce théorème a des conséquences étonnantes. Par exemple, d’après l’unicité, l’application \[{\mathbb N}\times{\mathbb N}\times{\mathbb N}\rightarrow{\mathbb N}\: , \;(m_1, m_2, m_3) \mapsto 2^{m_1} \times 3^{m_2} \times 5^{m_3}\] est injective ! Donc le cardinal de ${\mathbb N}\times{\mathbb N}\times{\mathbb N}$ est inférieur à celui de ${\mathbb N}$. (Bien sûr, on sait par ailleurs que ces deux cardinaux sont égaux).
Si nous avons \[n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots .\] comme dans le théorème, alors les diviseurs positifs de $n$ sont exactement les nombres \[n'=p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots\] où $m'_i\leq m_i$ pour tout $i$. En effet, il est clair que ces nombres divisent $n$. Réciproquement supposons que $n=n' n''$ et que nous avons les décompositions \[\begin{aligned} n' & = & p_1^{m'_1} p_2^{m'_2} \cdots \\ n'' & = & p_1^{m''_1} p_2^{m''_2} \cdots .\end{aligned}\] En multipliant nous trouvons \[n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots =p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots .\ \] Par l’unicité, il s’ensuit que $m_i=m'_i+m''_i$ pour tout $i$. Donc on a bien $m_i\geq m'_i$.
Nous déduisons de b) que le nombre de diviseurs de $n$ est égal à $(m_1+1)\,(m_2+1)\cdots$.
Supposons que nous avons les décompositions \[\begin{aligned} n & = & p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots \\ n' & = & p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots .\end{aligned}\] Alors il s’ensuit de b), que nous avons \[\begin{aligned} \mbox{PGCD}(n,n') & = & p_1^{\min(m_1, m'_1)} p_2^{\min(m_2, m'_2)} \cdots \newline \mbox{PPCM}(n,n') & = & p_1^{\max(m_1, m'_1)} p_2^{\max(m_2, m'_2)} \cdots\end{aligned}\] où $\mbox{PPCM}(n,n')$ désigne le plus petit commun multiple de $n$ et $n'$. On en déduit que \[n\times n' = \mbox{PPCM}(n,n') \times \mbox{PGCD}(n,n').\]

Congruences

(${ \mathbb Z}/n{ \mathbb Z}$ est de cardinal $n$.).

Soient $n\geq 1$ un entier et $a,b\in{ \mathbb Z}$. On dit que $a$ est congru à $b$ modulo $n$ s’il existe un $k\in{ \mathbb Z}$ tel que $a=b+k\,n$. On écrit alors \[a\equiv b\;(n) \mbox{ ou } a\equiv_n b \mbox{ ou } a = b\, \mbox{mod}\,n.\]

On a $a\equiv b\;(n)$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$. En effet, si nous avons $a=q n+ r$ et $b=q' n+r$, alors $a=b +(q-q')\,n$ et $a\equiv b\;(n)$. Réciproquement, si $a=q\,n+r$ et $b=q'\, n+r'$ et que $a=b+k\,n$, alors \[a=b+k\,n=q'\, n +r'+k\,n= (q'+k)\,n +r' = q\,n + r\] et par l’unicité de la, il s’ensuit que $r=r'$ (et $q=q'+k$).

Nous avons $6\equiv -15\;(7)$ car $6=-15+3\times 7$. Notons que $-15$ a effectivement le même reste que $6$ pour la par $7$ car $-15=(-3)\times 7 + 6$.

La relation $\equiv_n$ est une relation d’équivalence.
Si $a\equiv a'\;(n)$ et $b\equiv b'\;(n)$, alors $a+b\equiv a'+b'\;(n)$ et $a\,b \equiv a'\,b'\;(n)$. Dans ce cas, on a aussi $a^m\equiv a'^m\;(n)$ pour tout $m\in{\mathbb N}$.
Les nombres $0,1,\ldots, n-1$ forment un système de représentants des classes par rapport à $\equiv_n$.

a) La relation est réflexive car nous avons $a=a+0\times n$ pour tout $a\in{ \mathbb Z}$. Elle est car si nous avons $a=b+k\,n$ alors nous avons $b=a+(-k)\,n$. Elle est transitive, car si nous avons $a=b+k\,n$ et $b=c+l\,n$, alors nous avons $a=(c+l\,n)+k\,n=c+(l+k)\,n$.

b) Supposons que $a=a'+k\,n$ et que $b=b'+l\,n$. Alors $a+b=a'+b'+(k+l)\,n$ et \[a\,b=(a'+k\,n)(b'+l\,n)=a'\,b'+a'ln+knb'+klnn= a'\,b'+(a'l+kb'+kln)\,n.\] La dernière affirmation s’ensuit par récurrence sur $m$.

c) Tout $a\in{ \mathbb Z}$ est équivalent par $\equiv_n$ à un et un seul des nombres $0,1,\ldots, n-1$. En effet, cette affirmation est une reformulation de l’existence et de l’unicité du reste dans la de $a$ par $n$.

On pose \[{ \mathbb Z}/n{ \mathbb Z}\;= \; { \mathbb Z}/\equiv_n.\] On note $\mbox{ }^n\overline{a}$ ou $\overline{a}$ (ou même $a$) la classe de $a\in{ \mathbb Z}$. Les éléments de ${ \mathbb Z}/n{ \mathbb Z}$ sont donc les $\overline{a}$, $a\in{ \mathbb Z}$. On munit ${ \mathbb Z}/n{ \mathbb Z}$ des deux lois \[\begin{aligned} +\;: { \mathbb Z}/n{ \mathbb Z}\times { \mathbb Z}/n{ \mathbb Z}\stackrel{ }{\longrightarrow} { \mathbb Z}/n{ \mathbb Z}, & & (\overline{a}, \overline{b}) \mapsto \overline{a}+\overline{b}:= \overline{a+b} \newline \cdot\;: { \mathbb Z}/n{ \mathbb Z}\times { \mathbb Z}/n{ \mathbb Z}\stackrel{ }{\longrightarrow} { \mathbb Z}/n{ \mathbb Z}, & & (\overline{a}, \overline{b}) \mapsto \overline{a}\cdot\overline{b}:= \overline{a\cdot b} \end{aligned}\]

Grâce au lemme ci-dessus les deux lois sont bien définies.
Par définition de la notion de ‘classe d’équivalence’, nous avons \[\mbox{ }^n\overline{a} = \mbox{ }^n\overline{b} \mbox{ si et seulement si } a\equiv b\;(n).\] Par conséquent, deux classes $\overline{a}$ et $\overline{b}$ sont égales ssi les restes de $a$ et $b$ par la division euclidienne par $n$ sont égaux.
D’après le lemme ci-dessus, les classes \[\overline{0}, \overline{1}, \ldots, \overline{n-1}\] sont distinctes deux à deux et toute classe est égale à une d’entre elles. Ces classes constituent donc la liste (exhaustive et sans répétitions) des éléments de ${ \mathbb Z}/n{ \mathbb Z}$. En particulier, ${ \mathbb Z}/n{ \mathbb Z}$ est de cardinal $n$.

Critères de divisibilité

Soit \[N=1001001001001001001001001.\] Le nombre $N$ est-il? Non. Il est divisible par $3$ car la somme de ses chiffres est par $3$. De façon générale, on sait qu’un nombre est par $3$ ssi la somme de ses chiffres l’est. De même pour $9$ au lieu de $3$. On sait aussi qu’un nombre est divisible par $11$ ssi la somme alternée $c_0-c_1+c_2- \ldots$ de ses chiffres l’est ($c_0$ est le chiffre des unités, $c_1$ celui des dizaines, …). La par $7$, par contre, ne semble être reliée ni à la par $7$ de la somme ni à celle de la somme alternée de ses chiffres comme le montrent les exemples $7, 14, 21, \ldots$.

En fait, nous allons voir qu’un nombre est par $7$ si et seulement si c’est le cas pour le nombre \[c_0+3c_1+2c_2-c_3-3c_4-2c_5+c_6+3c_7+2c_8-c_9-3c_{10}- \ldots\] Par exemple, le nombre $100100100100$ est par $7$. Plus généralement, tout nombre dont l’écriture décimale est $3$-périodique et comporte un nombre de chiffres par $6$ est divisible par $7$.

Ces faits trouvent leur explication à l’aide de deux outils : 1) le calcul dess et 2) le calcul des restes de puissances. Le lemme suivant élucide le rôle que joue le calcul dess :

Soit $n\geq 2$ un entier et $a_i, i\in{\mathbb N}$ une suite d’entiers telle que \[a_i\equiv 10^i\;(n) \mbox{ pour tout $i\in{\mathbb N}$.}\] Soit $N\in{\mathbb N}$ et soient $c_0, c_1, \ldots, c_s\in \{0,\ldots, 9\}$ les chiffres de son écriture décimale ($c_0$=unités, …). Alors nous avons \[N \equiv\; a_0 c_0 + a_1 c_1 + a_2 c_2 + \ldots + a_s c_s (n).\] En particulier, $N$ est par $n$ si et seulement si $a_0 c_0 + a_1 c_1 + \ldots + a_s c_s$ est divisible par $n$.

Par définition de l’écriture décimale, on a \[N = c_0 + c_1 \times 10 + c_2 \times 10^2 + c_3 \times 10^3 + \cdots + c_s \times 10^s.\] Puisque $10^i\equiv a_i\;(n)$, les règles du calcul dess nous permettent de conclure que \[N \equiv\; c_0 a_0 + c_1 a_1 + c_2 a_2 + c_3 a_3 + \ldots + c_r a_r (n).\]

Déduisons le critère de par $7$ que nous avons évoqué plus haut. Pour pouvoir appliquer le lemme, il nous faut calculer une suite d’entiers $a_i$ tels que $a_i \equiv 10^i\; (7)$. La suite des $a_i$ vérifie donc less \[\begin{aligned} a_0 & \equiv & 1\; (7) \newline a_{i+1} & \equiv & 3 \, a_i \; (7)\end{aligned}\] (car $10 \equiv 3\;(7)$). Pour $a_0, \ldots a_6$, nous trouvons \[1,3,2,-1, -3, -2,1 .\] Donc $a_6\equiv a_0\;(7)$ et par récurrence, on trouve que $a_i \equiv a_{i+6}\; (7)$ pour tout $i\in{\mathbb N}$. Pour la suite des $a_i$, on peut donc choisir la suite $6$-périodique suivante \[1,3,2,-1,-3,-2,1,3,2,-1,-3,-2,1,3,2,-1,-3,-2, \ldots\] D’après le lemme, il s’ensuit que $N$ est par $7$ ssi c’est le cas pour le nombre \[c_0+3c_1+2c_2-c_3-3c_4-2c_5+c_6+3c_7+2c_8-c_9-3c_{10}- \ldots\] où les $c_i$ sont les chiffres de l’écriture décimale de $N$ ($c_0$=unités, $c_1$=dizaines, …).

Généralisation à d’autres systèmes de numération

Le fondement mathématique des systèmes de numération est le lemme suivant :

Soit $b\geq 2$ un entier. Pour tout entier $N\in{\mathbb N}$, il existe des entiers uniques $c_i\in\{0,\ldots, b-1\}$, $i\in{\mathbb N}$, nuls sauf pour un nombre fini d’entre eux, tels que \[N = c_0 + c_1 b + c_2 b^2 + \cdots + c_i b^i + \cdots\]

Dans la situation du lemme, si $N\neq 0$ et que $c_s$ est le dernier coefficient non nul, nous écrivons \[N=[c_s, c_{s-1}, \ldots, c_1, c_0]_b.\] et nous appelons l’expression l’écriture de $N$ en base $b$. Il nous arrivera d’omettre les crochets et les virgules comme dans l’exemple suivant \[1995_{10}= 11111001011_2 = 3713_8=133023_4\] Dans les cas de $b=2$, $8$ et $16$, on parle de l’écriture binaire, octale et hexadécimale, respectivement. Si $b$ excède 10, les ‘chiffres’ de $10$ à $b$ sont représentés par les premières lettres de l’alphabet. Par exemple, les chiffres du système hexadécimal sont $0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$. Ainsi on a \[1995_{10}= 7CB_{16}.\]

On prouve d’abord l’existence par récurrence sur $n$. Pour $n=0$ on pose $c_i=0$ pour tout $i\in{\mathbb N}$. Supposons $n>0$. Effectuons la division euclidienne par $b$ \[n=qb+r.\] D’après l’hypothèse de récurrence, le nombre $q$ s’écrit \[q=c_0'+c_1' b+ \cdots + c_t' b^t\] et donc \[n= r+c_0' b+ c_1' b^2 + \cdots + c_t' b^{t+1}\] On pose donc $c_0=r$ et $c_i=c'_{i-1}$ pour $i>0$. Montrons l’unicité. Si nous avons \[n=c_0 + c_1 b + c_2 b^2 +\cdots = d_0 + d_1 b + d_2 b^2 +\cdots\] alors $c_0=d_0$ car les deux apparaissent comme le reste de la de $n$ par $b$. Nous enlevons $c_0=d_0$ des deux côtés et nous divions par $b$ pour obtenir \[(n-c_0)/b= c_1 + c_2 b + \cdots = d_1 + d_2 b + \cdots.\] L’unicité s’ensuit par récurrence sur $n$.

Soit $n\geq 2$ un entier et $a_i$, $i\in{\mathbb N}$, une suite d’entiers tels que \[b^i\equiv a_i\;(n).\] Soit $N\in{\mathbb N}$ et $c_i$, $i\in{\mathbb N}$, les chiffres de son écriture en $b$ ($c_0$=unités, …). Alors on a \[N\equiv a_0 c_0 + a_1 c_1 + a_2 c_2 \cdots \;(n).\] En particulier, $N$ est par $n$, si c’est le cas pour $a_0 c_0 + a_1 c_1 + a_2 c_2 \cdots$.

La démonstration est analogue à celle du cas $b=10$.

Nous avons $8^i\equiv 1 \;(7)$. Donc un nombre est divisible par $7$ ssi la somme des chiffres de son écriture octale est divisible par $7$.
Nous avons $16^i \equiv (-1)^i\;(17)$. Donc un nombre est divisible par $17$ ssi la somme alternée des chiffres de son écriture hexadécimale est divisible par $17$.

L’algorithme d’Euclide-Bézout

Soient $a,b,c \in{ \mathbb Z}$ tels que $(a,b)\neq (0,0)$. L’algorithme suivant sert à calculer le $\mbox{PGCD}(a,b)$ et la solution générale $(x,y)\in{ \mathbb Z}^2$ de l’équation de \[a\,x+b\,y= c.\] L’algorithme se présente sous forme d’un tableau. Dans une première étape on remplit les deux premières lignes comme indiquées dans le tableau ci-dessous. Le coefficient $q_1$ n’est pas défini; le coefficient $q_2$ est le quotient de la division euclidienne de $a$ par $b$. Les lignes suivantes se calculent chacune en fonction des deux précédentes comme indiquée ci-dessous.

$k$	$r_k$	$q_k$	$x_k$	$y_k$
$1$	a	$*$	$1$	$0$
$2$	b	$q_2$	$0$	$1$	$a=q_2\,b+ r_3$ est une div. eucl.
$3$	$r_3$	…	…	…
$\vdots$
$k-1$	$r_{k-1}$	$q_{k-1}$	$x_{k-1}$	$y_{k-1}$
$k$	$r_k$	$q_k$	$x_k$	$y_k$	$r_{k-1}=q_k\,r_k+r_{k+1}$ est une div. eucl.
$k+1$	$r_{k+1}$	$q_{k+1}$	$x_{k+1}$	$y_{k+1}$	$x_{k+1}=x_{k-1}-q_k x_k$, $y_{k+1}=y_{k-1}-q_k y_k$
$\vdots$
$N$	$r_N$	$q_N$	$x_N$	$y_N$
$N+1$	$r_{N+1}=0$	$*$	$x_{N+1}$	$y_{N+1}$

La première colonne contient donc les restes des divisions euclidiennes successives, la deuxième colonne les et les deux dernières colonnes des coefficients $x_k$, $y_k$ tels que $a\,x_k+b\,y_k=r_k$ (voir la démonstration ci-dessous).

Les coefficients de la première colonne forment une suite strictement décroissante de nombres positifs entiers. Par définition, $N$ est le plus petit entier avec $r_{N+1}=0$.

Théorème. On a $r_N = \mbox{PGCD}(a,b)$. Si $\mbox{PGCD}(a,b)$ divise $c$, la solution générale de l’équation \[ax+by=c\] est donnée par \[\begin{aligned} x & = & \frac{c}{\mbox{PGCD}(a,b)}x_N+l x_{N+1} \\ y & = & \frac{c}{\mbox{PGCD}(a,b)}y_N+l y_{N+1}\end{aligned}\] où $l\in{ \mathbb Z}$. Si $\mbox{PGCD}(a,b)$ ne divise pas $c$, l’équation $ax+by=c$ n’admet pas de solution $(x,y)\in{ \mathbb Z}^2$.

Nous cherchons le $\mbox{PGCD}(198,75)$ et toutes les solutions de l’équation $198 x + 75 y = \mbox{PGCD}( 198,75)$. Nous obtenons le tableau

$k$	$r_k$	$q_k$	$x_k$	$y_k$
$1$	$198$	$*$	$1$	$0$
$2$	$75$	$2$	$0$	$1$
$3$	$48$	$1$	$1$	$-2$
$4$	$27$	$1$	$-1$	$3$
$5$	$21$	$1$	$2$	$-5$
$6$	$6$	$3$	$-3$	$8$
$7$	$3$	$2$	$11$	$-29$
$8$	$0$	$*$	$-25$	$66$

Ainsi $\mbox{PGCD}(198,75)=3$ et la solution générale de l’équation $198 x + 75 y =3$ est donnée par \[\begin{aligned} x & = & 11 - 25 l \\ y & = & -29 + 66 l\end{aligned}\] où $l\in{ \mathbb Z}$.

Notons que $25=75/3$ et $66=198/3$. Notons aussi que les dernières deux colonnes sont des suites alternées et que les modules de $x_k$, $y_k$ sont strictement croissants pour $k\geq 3$. En particulier, nous avons $0\leq x_N< -(-25)$ et $-66< y_N\leq 0$. La solution $(x_N,y_N)$ est la seule avec ces propriétés. Les coefficients $q_k$ apparaissent dans l’identité \[\frac{198}{75}= 2 + \frac{1}{1+ \frac{ 1}{ 1+ \frac{ 1}{ 1+ \frac{ 1}{ 3+ \frac{ 1}{ 2}}}}} \;\; .\] Voir les exercices après la démonstration.

Démonstration. Notons d’abord que l’algorithme s’arrête. En effet, $r_{k+1}$ est le reste d’une division euclidienne par $r_k$. Donc $r_{k+1}$ est compris entre $0$ et $r_k-1$. Les $r_k$ forment donc une suite strictement décroissante de nombres positifs entiers. Une telle suite doit aboutir à zéro après un nombre fini d’étapes.

Montrons que $r_N=\mbox{PGCD}(a,b)$. Montrons d’abord que nous avons \[\mbox{PGCD}(r_{k-1}, r_k)=\mbox{PGCD}(r_k, r_{k+1}).\] En effet, par construction, nous avons une équation \[r_{k-1} = q_k r_k + r_{k+1}.\] Elle montre que l’ensemble des diviseurs communs à $r_{k-1}$ et $r_k$ est égal à l’ensemble des diviseurs communs à $r_k$ et $r_{k+1}$. En particulier, les plus grands éléments de ces ensembles sont égaux. La formule pour $r_N$ s’ensuit par récurrence : \[\begin{aligned} \mbox{PGCD}(a,b)& = & \mbox{PGCD}(b,r_3)= \ldots \\ & = & \mbox{PGCD}(r_{N-1},r_N)=\mbox{PGCD}(r_N, r_{N+1})=\mbox{PGCD}(r_N,0)= r_N.\end{aligned}\]

Pour montrer la deuxième affirmation, nous introduisons less \[S_k=\left[ \begin{array}{cc} x_k & x_{k+1} \\ y_k & y_{k+1} \end{array} \right] \: , \;k\geq 1.\] Nous avons \[S_1=\left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right] \mbox{ et } S_{k+1}= S_k \left[ \begin{array}{cc} 0 & 1 \\ 1 & -q_{k+1} \end{array} \right].\] Par récurrence, il s’ensuit que \[[ a\;\;b] S_k = [r_k \;\; r_{k+1}] \quad\mbox{et}\quad \det S_k=-(-1)^k.\] En particulier, nous avons $[a\;\; b] S_N=[r_N\;\; 0]$ et la \[S_N^{-1}=-(-1)^N \left[ \begin{array}{cc} y_{N+1} & -x_{N+1} \\ -y_N & x_N \end{array} \right]\] est à coefficients entiers. Donc si nous posons \[\left[ \begin{array}{c} u \\ v \end{array} \right] = S_N^{-1} \left[ \begin{array}{c} x \\ y \end{array} \right]\: , \;\] alors $u,v$ sont des entiers. Nous avons \[[a \;\; b] \left[ \begin{array}{c} x \\ y \end{array} \right]= [a \;\; b] S_N S_N^{-1} \left[ \begin{array}{c} x \\ y \end{array} \right]= [r_N\;\; 0] \left[ \begin{array}{c} u \\ v \end{array} \right]\] de façon que l’équation \[[a \;\; b] \left[ \begin{array}{c} x \\ y \end{array} \right]=c \quad\mbox{(resp. $ax+by=c$)}\] est équivalente à l’équation \[[r_N \;\; 0] \left[ \begin{array}{c} u \\ v \end{array} \right]=c \quad\mbox{(resp. $r_N u + 0\,v=c$)}.\] Or il est clair que cette dernière équation admet des solutions si et seulement si $r_N$ divise $c$ et que dans ce cas la solution générale est \[\left[ \begin{array}{c} u \\ v \end{array} \right] = \left[ \begin{array}{c} c/r_N \\ l \end{array} \right] \: , \;\] où $l\in{ \mathbb Z}$. Donc l’équation $ax+by=c$ admet des solutions si et seulement si $r_N$ divise $c$ et dans ce cas la solution générale est \[\left[ \begin{array}{c} x \\ y \end{array} \right] = S_N \left[ \begin{array}{c} u \\ v \end{array} \right] = \left[ \begin{array}{cc} x_N & x_{N+1} \\ y_N & y_{N+1} \end{array} \right] \left[ \begin{array}{c} c/r_N \\ l \end{array} \right] = \left[ \begin{array}{c} \frac{c}{r_N} x_N + l x_{N+1} \\ \frac{c}{r_N} y_N + l y_{N+1} \end{array} \right].\]

Exercices. 1) Trouver toutes les solutions $(x,y)\in{ \mathbb Z}^2$ des équations suivantes : a) $5x+3y=2$, b) $4x+9y=1$, c) $17x+68y=3$, d) $20x+30y=0$, e) $1789x+1994y=1$ f) $1994x+666y=2$.

2) Avec les de l’algorithme d’Euclide-Bézout, montrer que \[x_{N+1}= (-1)^N \frac{c}{\mbox{PGCD}(a,b)} \mbox{ et } y_{N+1}= -(-1)^N \frac{a}{\mbox{PGCD}(a,b)}.\] Indication : On pourra utiliser l’identité \[\left[ \begin{array}{cc} a & b \\ -y_N & x_N \end{array} \right] S_N= \left[ \begin{array}{cc} r_N & 0 \newline 0 & -(-1)^N \end{array} \right].\]

3) Supposons $a>b>0$. Avec les de l’algorithme d’Euclide-Bézout, montrer que \[\dfrac{a}{b}=q_2+ \dfrac{ r_3}{ b}= q_2+ \dfrac{ 1}{ q_3+ \dfrac{ r_4}{ r_3}} =q_2+ \dfrac{ 1}{ q_3+ \dfrac{ 1}{ q_4+ \dfrac{ r_5}{ r_4}}}= \ldots\]

4) Nous allons caractériser la solution $(x_N,y_N)$ fournie par l’algorithme d’Euclide-Bézout parmi toutes les solutions de l’équation de. Supposons, pour simplifier, que $a>b>0$ et que $\mbox{PGCD}(a,b)=1$.

a) Montrer qu’il existe une solution $(x_+,y_+)\in{ \mathbb Z}^2$ de $ax+by=1$ et une seule telle que $0\leq x_+<b$. Montrer qu’on a $-a<y_+\leq 0$.

b) Montrer qu’il existe une solution $(x_-, y_-)\in{ \mathbb Z}^2$ de $ax+by=1$ et une seule telle que $-b<x_-\leq 0$. Montrer qu’on a $0\leq y_+<a$.

c) Montrer qu’on a $(x_N,y_N)= (x_+,y_+)$ si $N$ est impair et $(x_N,y_N)=(x_-,y_-)$ si $N$ est pair. Indication : on pourra commencer par montrer que les suites $-(-1)^k x_k$ et $(-1)^k y_k$ sont strictement croissantes pour $k\geq 3$.

5) Nous allons estimer le nombre d’étapes de l’algorithme d’Euclide-Bézout. Pour un couple d’entiers $(a,b)$ avec $a>b\geq 0$ notons $N(a,b)$ le nombre $N$ apparaissant comme nombre d’étapes de l’algorithme d’Euclide-Bézout appliqué à $(a,b)$.

a) Montrer que $N(a,b)\leq 1+\log_2 a$.

b) Soit $F_0=0$, $F_1=1$ et $F_n=F_{n-1}+F_{n-2}$ pour tout $n>1$. Par définition, le nombre $F_n$ est le $n$-ième nombre de Fibonacci. Montrer que $N(F_n, F_{n-1})=n$, que $N(a,b)\leq n$ si $a\leq F_n$ et que l’égalité ne se présente que pour $a=F_n$ et $b=F_{n-1}$.

Une autre approche de l’équation de Bézout

Soient $a,b,c\in{ \mathbb Z}$ tels que $(a,b)\neq (0,0)$. L’équation de Bézout est l’équation \[ax+by=c\] où $x,y$ désignent deux entiers relatifs. Si $c\neq 0$ on dit qu’il s’agit d’une équation inhomogène d’inhomogénéité $c$. Dans ce cas, l’équation homogène associée est l’équation \[ax+by=0.\] Notons $d=\mbox{PGCD}(a,b)$.

La solution générale de l’équation homogène $ax+by=0$ est donnée par \[\begin{array}{ccc} x_h & = & l \;\frac{b}{d} \\ y_h & = & -l \;\frac{a}{d} \end{array} \;\; l\in{ \mathbb Z}.\]
Si $d$ divise $c$ et que $(x_p,y_p)$ est une solution (dite “particulière”) de l’équation inhomogène $ax+by=c$, alors la solution générale de l’équation inhomogène est donnée par \[\begin{array}{ccc} x & = & x_p+ l \;\frac{b}{d} \newline y & = & y_p- l \;\frac{a}{d} \end{array}\]

La construction de la solution générale de l’équation de se fait donc suivant le même schéma que la construction de la solution d’une équation linéaire : \[\mbox{sol. gén. de l'éq. inhomogène} = \mbox{sol. part. de l'éq. inhomogène} + \mbox{sol. gén. de l'éq. homogène}.\]

a) Regardons d’abord le cas où $b=0$. Alors l’équation se réduit à $ax+0\;y =0$ où $a\neq 0$ (car $(a,b)\neq(0,0)$). Clairement la solution générale est donnée par $x=0$, $y=l$, $l\in{ \mathbb Z}$. De l’autre côté, on a $d=|a|$, donc $a/d=\pm 1$ et $b/d=0$. L’affirmation est donc vraie dans ce cas.

Supposons maintenant $b\neq 0$. L’équation $ax+by=0$ équivaut à \[\frac{a}{d} \; x = - \frac{b}{d}\, y.\] Notons que les deux fractions qui apparaissent ici sont en fait des entiers, car $d=\mbox{PGCD}(a,b)$ divise $a$ et $b$. Cette dernière équation montre que $b/d$ divise le produit $x\; a/d$. Or, nous avons $\mbox{PGCD}(a/d, b/d)=1$. Par le lemme de Gauss, il s’ensuit que $b/d$ divise $x$. Donc il existe un $l\in{ \mathbb Z}$ tel que $x=l\; b/d$. Nous avons donc \[\frac{a}{d} \; l \; \frac{b}{d} = -\frac{b}{d} \, y.\] Puisque $b\neq 0$, nous pouvons conclure que $y=-l\; a/d$.

b) Supposons que $(x,y)\in{ \mathbb Z}^2$ est une solution de l’équation inhomogène. Si nous formons la différence des deux équations \[\begin{aligned} ax+by & = & c \\ a x_p + b y_p & = & c \end{aligned}\] nous trouvons \[a (x-x_p) + b(y-y_p) = 0\] c’est-à-dire que $(x-x_p, y-y_p)$ est une solution de l’équation homogène. D’après a), il existe donc un $l\in{ \mathbb Z}$ tel que \[\begin{aligned} x-x_p & = & l\; \frac{b}{d} \newline y-y_p & = & -l\; \frac{a}{d}\end{aligned}\] L’affirmation en résulte.

Interprétation géométrique

Nous considérons le plan ${\mathbb R}^2$ et nous appelons points entiers les points $(x,y)\in{\mathbb R}^2$ à coordonnées entières $x,y\in{ \mathbb Z}$. Soient $a,b,c\in{ \mathbb Z}$ tels que $(a,b)\neq(0,0)$. Notons $D=D(a,b,c)$ la droite dans ${\mathbb R}^2$ formée des points $(\xi,\eta)\in{\mathbb R}^2$ tels que $a\xi+b\eta=c$. Alors l’ensemble des solutions $(x,y)\in{ \mathbb Z}^2$ de l’équation de Bézout $ax+by=c$ s’identifie à l’ensemble des points entiers de la droite $D$.

Les-mathematiques.net

D’après les théorèmes cités ci-dessus, deux cas seulement sont possibles

soit la droite $D$ ne contient aucun point entier
soit la droite $D$ contient une infinité de points entiers.

Dans le deuxième cas, l’ensemble des points entiers est obtenu en rajoutant un multiple entier $v=(x_h,y_h)$ à un point entier $p=(x_p,y_p)$ fixé de la droite. Le vecteur $(x_h, y_h)$ peut être identifié avec un point entier de distance minimale à l’origine sur la droite $D(a,b,0)$. Notons que cette droite contient exactement deux tels points (à savoir $v$ et $-v$).

Le lemme chinois en termes de congruences

(lemme chinois).

Soient $n_1, n_2\geq 2$ deux entiers premiers entre eux et $u_1 n_1 + u_2 n_2= 1$ une équation de. Soient $a_1, a_2\in{ \mathbb Z}$ et $a\in{ \mathbb Z}$ tel que $a\equiv a_1 u_2 n_2 + a_1 u_1 n_1 (n_1 n_2)$. Alors pour $x\in{ \mathbb Z}$ on a l’équivalence \[\left. \begin{array}{ccc} x & \equiv & a_1\; (n_1) \newline x & \equiv & a_2\; (n_2) \end{array} \right\} \; \Longleftrightarrow \; x \equiv a\;(n_1 n_2).\]

On peut réinterpréter le lemme en disant que la solution générale $x\in{ \mathbb Z}$ du système desest donnée par \[x=a+k n_1 n_2\: , \;k\in{ \mathbb Z}.\]

Vérifions d’abord que $a$ est bien une solution du système des. En effet, d’après l’hypothèse, nous avons \[a= a_1 u_2 n_2 + a_2 u_1 n_1 + k n_1 n_2\] pour un $k\in{ \mathbb Z}$ et donc \[a \equiv a_1 u_2 n_2 \equiv a_1 (u_2 n_2 + u_1 n_1) \equiv a_1 \;(n_1)\] et de même \[a\equiv a_2 u_1 n_1 \equiv a_2 (u_1 n_1 + u_2 n_2) \equiv a_2 \; (n_2).\] Montrons maintenant l’équivalence. Supposons que $x\equiv a \; (n_1 n_2)$. Alors $x=a+k n_1 n_2$ pour un $k\in{ \mathbb Z}$ et donc $x\equiv a \equiv a_1\;(n_1)$ et $x \equiv a \equiv a_2\;(n_2)$. Réciproquement, supposons que $x$ vérifie $x\equiv a_1\;(n_1)$ et $x\equiv a_2 \;(n_2)$. Alors nous avons $(x-a) \equiv 0\;(n_1)$ et $(x-a)\equiv 0\;(n_2)$. Donc $x-a$ est par $n_1$ et par $n_2$. Puisque les deux sont premiers entre eux, il s’ensuit (lemme de) que $x-a$ est par $n_1 n_2$, c’est-à-dire que $x\equiv a \;(n_1 n_2)$.

Considérons le système \[\begin{aligned} x & \equiv & 1\;(17) \\ x & \equiv & 2\;(28) \\ x & \equiv & 3\;(31) \end{aligned}\] Nous avons l’équation de $5\times 17 - 3 \times 28=1$. Le système formé des deux premières équations est donc équivalent à la $x\equiv a\;(17\times 28)$ où $a=1 \times (-3\times 28) + 2\times (5\times 17)= 86$. Le système des trois équations se réduit donc à \[\begin{aligned} x & \equiv & 86 \; (476) \\ x & \equiv & 3 \; (31).\end{aligned}\] Nous avons l’équation de $(-14)\times 476 + 215\times 31=1$. Donc le système est équivalent à la congruence $x\equiv b\;(476\times 31)$ où $b= 86\times (215\times 31) +3 \times (-14\times 476)= 553198$. Si nous réduisons $b$ modulo $476\times 31= 14756$, nous trouvons que le système des trois équations est équivalent à la \[x \equiv 7226 \; (14756);\] Nous invitons le lecteur à vérifier que $7226$ donne les restes $1$, $2$ et $3$ dans la division par $17$, $28$ et $31$.

Systèmes de congruences

Soient $r$ et $n_1, \ldots, n_r$ des entiers $\geq 2$ et $a_1, \ldots, a_r$ des entiers quelconques. Considérons le système \[\begin{aligned} x & \equiv & a_1 \; (n_1) \\ x & \equiv & a_2 \; (n_2) \\ & \vdots & \\ x & \equiv & a_r \; (n_r).\end{aligned}\] Supposons que $x=a$ et $x=a'$ sont deux solutions. Alors la différence $a-a'$ est par tous les $n_i$ et donc par leur plus petit commun multiple $n=\mbox{PPCM}(n_1, \ldots, n_r)$. Donc s’il existe une solution, sa classe modulo $n$ est unique.

Il peut ne pas exister de solution comme le montre l’exemple du système \[\begin{aligned} x & \equiv & 1 \; (6) \\ x & \equiv & 2 \; (8) \\\end{aligned}\] ou encore celui du système \[\begin{aligned} x & \equiv & 1 \;(2) \\ x & \equiv & 0 \;(2) .\end{aligned}\] Notons que nous n’avons pas exclu ce genre de contradictions banales.

L’application systématique du nous permettra de réduire tout système des soit à un système contradictoire soit à une seule modulo le plus petit commun multiple des modules. Nous ne développons pas ici la méthode dans le cas général mais nous limitons à la décrire dans un exemple simple.

Considérons le système \[\begin{aligned} x & \equiv & 3 \; (18) \\ x & \equiv & c \; (12).\end{aligned}\] Il s’agit de déterminer tous les entiers $c$ pour lesquels le sytème admet des solutions et de calculer les solutions dans ce cas. Constatons tout d’abord que les nombres $18$ et $12$ ne sont pas premiers entre eux de façon que le ne s’applique pas immédiatement. Pour résoudre le problème, nous allons dans une première étape augmenter le nombre d’équations pour obtenir des modules qui sont des puissances de nombres premiers. Nous avons ainsi $18=2\times 3^2$ et d’après le lemme chinois la première est équivalente au système \[\begin{aligned} x & \equiv & 1 \; (2) \\ x & \equiv & 3 \; (9) .\end{aligned}\] De même, puisque nous avons $12=3\times 4$, la seconde congruence est équivalente au système \[\begin{aligned} x & \equiv & c \; (3) \\ x & \equiv & c \; (4).\end{aligned}\] Nous avons ainsi trouvé un système de quatres qui est équivalent au système de départ. Nous le réécrivons dans un ordre où les puissances de chaque nombresont regroupées ensemble et les puissances les plus élevées apparaissent enlieu : \[\begin{aligned} x & \equiv & c \; (4) \\ x & \equiv & 1 \; (2) \\ x & \equiv & 3 \; (9) \\ x & \equiv & c \; (3) \end{aligned}\] Rappelons-nous que si nous avons $a\equiv b\;(n)$ alors nous avons aussi $a\equiv b \;(d)$ pour tout diviseur $d$ de $n$ (en effet, si $n=q\,d$ et $a=b+k\,n$ alors $a=b+(k\,q)\,d$). L’équation ([one]) implique donc que $x \equiv c \;(2)$ de façon que les équations ([one]) et ([two]) sont contradictoires sauf si $c\equiv 1\;(2)$. De même, les équations ([three]) et ([four]) sont contradictoires sauf si $c\equiv 0\;(3)$. Nous avons donc les conditions \[\begin{aligned} c & \equiv & 1 \; (2) \\ c & \equiv & 0 \; (3) \end{aligned}\] qui sont nécessaires pour qu’une solution existe. Réciproquement, ces conditions sont aussi suffisantes car si elles sont vérifiées, la ([two]) est une conséquence de ([one]), et ([four]) est une conséquence de ([three]) de façon que le système tout entier est équivalent à un système de deuxs \[\begin{aligned} x & \equiv & c \; (4) \newline x & \equiv & 3 \; (9)\end{aligned}\] Nous avons l’équation de $-2\times 4 + 9 =1$. Donc, d’après le, ce système est équivalent à la $x \equiv c\times 9 + 3 \times (-8) \;(36)$ ou encore $x \equiv 3c+12 \;(36)$. En conclusion, le système de départ admet une solution si et seulement si $c\equiv 3\;(6)$ et dans ce cas l’ensemble des solutions est l’ensemble des entiers $x$ tels que $x\equiv 3c+12\;(36)$.

Classes de congruence inversibles

Soit $n\geq 2$ un entier. Une classe de congruence $\overline{a}\in{ \mathbb Z}/n{ \mathbb Z}$ est inversible s’il existe une classe $\overline{b}$ telle que $\overline{a} \overline{b} =\overline{1}$. On note $({ \mathbb Z}/n{ \mathbb Z})^*$ l’ensemble des classess.

Muni de la multiplication naturelle, l’ensemble des classess est un d’élément neutre $\overline{1}$.

Le lemme implique que si la classe $\overline{a}$ est, alors la classe $\overline{b}$ telle que $\overline{a}\overline{b}=\overline{1}$ est unique. On l’appelle la classe inverse de $\overline{a}$.

Il s’agit d’abord de vérifier que la loi de multiplication est bien définie, c’est-à-dire que le produit de deux classess est encore. En effet, si $\overline{a}\overline{b}=\overline{1}$ et $\overline{a'} \overline{b'} = \overline{1}$, alors $(\overline{a} \overline{a'}) ( \overline{b'}\overline{b})=\overline{1}$. La loi est associative car la multiplication de ${ \mathbb Z}/n{ \mathbb Z}$ est associative. Elle admet l’élément $\overline{1}$ pour élément neutre. Finalement, par définition, tout élément de $({ \mathbb Z}/n{ \mathbb Z})^*$ admet un inverse.

Une classe $\overline{a}$ est ssi $a$ et $n$ sont premiers entre eux.

En effet, la classe $a$ est, ssi l’équation $ab=1+kn$ admet des solutions $b,k\in{ \mathbb Z}$. Or cette équation est une variante de l’équation de $a b + (-n) k =1$ aux inconnues $b$, $k$. L’affirmation en résulte.

Supposons que la classe $\overline{x}$ est. Alors la congruence $a\equiv b\; (n)$ est équivalente à $ax\equiv bx \;(n)$.

L’affirmation du lemme est fausse si la classe $\overline{x}$ n’est pas inversible.

Supposons que $\overline{x}\overline{y}=\overline{1}$. Alors $x y \equiv 1\; (n)$ et donc la congruence $ax y \equiv bx y\;(n)$ implique $a\equiv b\;(n)$.

Anneaux, groupes et lemme chinois

(anneau).

Un anneau est un triplet $(A,+,\;\cdot)$ formé d’un ensemble $A$ et deux deux applications \[+\;: A\times A \rightarrow A \: , \;(a,b) \mapsto a+b \\ \quad\mbox{ et } \quad \cdot\; : A \times A \rightarrow A \: , \;(a,b) \mapsto ab\] appelées l’addition et la multiplication de $A$ et qui vérifient les axiomes suivants

Le couple $(A,+)$ est un groupe commutatif. On note $0_A$ ou $0$ son élément neutre.
La multiplication $\cdot$ est associative et admet un élément neutre noté $1_A$ ou $1$.
L’addition et la multiplication vérifient les règles de distributivité \[\begin{aligned} a(b+c) & = & ab + ac \\ (a+b) c & = & ac + bc\end{aligned}\] quels que soient $a,b,c$ éléments de $A$.

Un est commutatif si sa multiplication est.

Les ensembles ${ \mathbb Z}$, ${\mathbb Q}$, ${\mathbb R}$ et ${\mathbb C}$ munis de leurs opérations d’addition et de multiplication habituelles sont desx commutatifs. L’anneau $M_2({\mathbb R})$ dess \[\left[\begin{array}{cc} a & b \\ c & d \end{array} \right]\] avec l’addition et la multiplication des matrices est un non-commutatif. En effet, si on pose \[A= \left[\begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right] \; \: , \; B= \left[\begin{array}{cc} 0 & 0 \newline 1 & 0 \end{array} \right]\] on a $AB\neq BA$.

(inversible).

Soit $A=(A, + , \; \cdot)$ un. Un élément $a\in A$ est inversible s’il existe un élément $b\in A$ tel que $ab=1_A=ba$. On note $A^*$ l’ensemble des élémentss de $A$. L’anneau $A$ est un corps si $A^*=A\setminus \{0\}$, c’est-à-dire que tout élément non nul de $A$ est inversible (et que $A\neq \{0_A\}$).

Pour le cas de l’anneau $A={ \mathbb Z}/n{ \mathbb Z}$, cette définition est celle de la section précédente. Lesx ${\mathbb Q}$, ${\mathbb R}$ et ${\mathbb C}$ sont des.

L’anneau ${ \mathbb Z}/n{ \mathbb Z}$ est un corps si et seulement si $n$ est premier. Soit $p$ un. Alors $({ \mathbb Z}/p{ \mathbb Z})^*$ est formé des $p-1$ classes $\overline{1}, \overline{2}, \ldots, \overline{p-1}$. Soit $n$ un entier $\geq 1$. Alors $({ \mathbb Z}/p^n{ \mathbb Z})$ est le complémentaire dans ${ \mathbb Z}/p^n { \mathbb Z}$ des $p^{n-1}$ classes $\overline{p}, \overline{2p}, \ldots, \overline{(p^{n-1}-1)p}$. Donc \[|({ \mathbb Z}/p{ \mathbb Z})^*| = p-1 \mbox{ et } |({ \mathbb Z}/p^n{ \mathbb Z})^*| = p^n - p^{n-1}= p^{n-1}(p-1).\]

Si l’élément $0_A$ est dans l’anneau $A$, alors nous avons $0_A = 1_A$ et $A=\{0_A\}=\{1_A\}$. En effet, supposons que $0\; b= 1$. Nous affirmons que $0 b = 0$; en effet, il suffit de rajouter $-0\;b$ des deux côtés de léquation $0 \; b= (0+0)\;b= 0\; b + 0\; b$.

Soit $A=(A,+,\;\cdot)$ un. Alors si deux éléments sonts, leur produit l’est encore. L’ensemble $A^*$ muni de la multiplication déduite de celle de $A$ est un d’élément neutre $1_A$.

Il s’ensuit que l’inverse d’un élément d’un est unique (car l’inverse d’un élément d’un est unique).

Supposons que $a$ et $b$ sonts et que $aa'=1=a'a$ et $bb'=1=b'b$. Alors nous avons $(ab)(b' a')=1=(b' a')(a b)$ de façon que $ab$ est inversible. L’associativité de la multiplication est conséquence de la même propriété pour la multiplication dans un et de même l’existence d’un élément neutre. L’existence des inverses résulte de la définition de $A^*$.

Soient $(A_1, +, \cdot)$ et $(A_2, +, \cdot)$ deuxx. L’ensemble $A_1 \times A_2$ muni des lois définies par \[\begin{aligned} (a_1, a_2) + (a_1', a_2')=(a_1+a_1', a_2'+a_2') \newline (a_1, a_2)\cdot (a_1', a_2')=(a_1 a_1', a_2 a_2')\end{aligned}\] est un appelé l’anneau produit de $A_1$ par $A_2$. L’élément neutre pour l’addition de $A_1\times A_2$ est le couple $(0, 0)$ et celui pour la multiplication le couple $(1,1)$.

En appliquant plusieurs fois ce résultat nous obtenons un grand nombre de nouveaux exemples d’anneaux. Par exemple, tous lesx suivants sont de cardinal 24 \[{ \mathbb Z}/24{ \mathbb Z}\: , \; { \mathbb Z}/3{ \mathbb Z}\times { \mathbb Z}/8 { \mathbb Z}\: , \; { \mathbb Z}/8{ \mathbb Z}\times { \mathbb Z}/3{ \mathbb Z}\: , \; { \mathbb Z}/2{ \mathbb Z}\times { \mathbb Z}/4{ \mathbb Z}\times { \mathbb Z}/3{ \mathbb Z}.\] Nous allons voir que certains de ces anneaux sont “isomorphes”, c’est-à-dire qu’ils ne se distinguent pas de façon essentielle.

Il s’agit de vérifier les troiss d’axiomes pour les lois définies sur $A_1\times A_2$. A titre d’exemple, vérifions que la multiplication est associative. En effet, en utilisant la définition de la multiplication sur $A_1\times A_2$ et l’accociativité de la multiplication dans $A_1$ et $A_2$, nous avons \[\begin{aligned} ((a_1, a_2) \cdot (a_1', a_2')) \cdot (a_1'', a_2'') & = & (a_1 a_1', a_2 a_2') \cdot (a_1'', a_2'') = ((a_1 a_1') a_1'', (a_2 a_2') a_2'') \\ & = & (a_1 (a_1' a_1''), a_2 (a_2' a_2'')) = (a_1, a_2)\cdot (a_1' a_1'', a_2' a_2'') \newline & = & (a_1, a_2) \cdot ((a_1', a_2') \cdot (a_1'', a_2'')).\end{aligned}\] Nous laissons au lecteur le soin d’écrire les démonstrations des autres propriétés.

Soient $(G_1, \star)$ et $(G_2, \star)$ deuxs. L’ensemble $G_1\times G_2$ muni de la loi \[(g_1, g_2)\star (g_1', g_2')= (g_1 \star g_1', g_2 g_2')\] est un d’élément neutre le couple $(e, e)$.

La démonstration est analogue à celle du lemme-définition précédent.

Soient $(A_1, +, \cdot)$ et $(A_2, +, \cdot)$ deuxx. Alors nous avons l’égalité \[(A_1 \times A_2)^\star = A_1^\star \times A_2^\star.\] En outre la loi de sur $(A_1\times A_2)^\star$ est celle du produit $A_1^\star \times A_2^\star$.

Soit $(a_1, a_2)$ un couple d’élémentss. Soient $a_1'$ et $a_2'$ les inverses de $a_1$ et $a_2$. Alors nous avons \[(a_1', a_2')\cdot (a_1, a_2)= (1,1) = (a_1, a_2) \cdot (a_1', a_2')\] ce qui signifie que $(a_1, a_2)$ est dans $A_1\times A_2$ d’inverse $(a_1', a_2')$. Ainsi l’ensemble $A_1^\star\times A_2^\star$ est inclus dans $(A_1\times A_2)^\star$. Réciproquement, soit $(a_1, a_2)$ un élément de $A_1\times A_2$ et soit $(a_1', a_2')$ son inverse. Alors on vérifie aussitôt que $a_1'$ est inverse à $a_1$ dans $A_1$ et que $a_2'$ est inverse à $a_2$ dans $A_2$. La dernière affirmation est une conséquence immédiate des définitions.

(homomorphisme d’anneaux).

Soient $(A, +,\cdot)$ et $(B, +, \cdot)$ deuxx. Une application $f: A \rightarrow B$ est un homomorphisme d’anneaux si elle vérifie \[\begin{aligned} f(a+a') & = & f(a) + f(a') \\ f(a \cdot a') & = & f(a) \cdot f(a') \newline f(1_A) & = & 1_B\end{aligned}\] quels que soient $a,a'\in A$. C’est un isomorphisme d’anneaux si en plus, elle est bijective. Lesx $A$ et $B$ sont isomorphes s’il existe un de $A$ vers $B$.

Soient $A_1$ et $A_2$ deuxx. Considérons l’application \[f : A_1 \times A_2 \rightarrow A_2 \times A_1\: , \; (a_1, a_2) \mapsto (a_2, a_2).\] Alors on vérifie que $f$ est un.

Soient $A$ et $B$ deuxx et $f:A \rightarrow B$ un. Soit $g: B \rightarrow A$ l’application réciproque de $f$. Alors $g$ est un homomorphisme et même un isomorphisme.

En effet, soient $b, b'$ des éléments de $B$. Pour vérifier qu’on a égalité entre $g(b\,b')$ et $g(b) \,g(b')$ il suffit de voir que less par $f$ de ces deux éléments coı̈ncident. Or nous avons \[f(g(b\,b'))=b\;b'= f(g(b))\, f(g(b'))= f(g(b)\,g(b')).\] De même on vérifie que $g(b+b')=g(b)+g(b')$. Finalement, l’égalité $f(1_A)=1_B$ entraı̂ne que $1_A= g(1_B)$.

(homomorhisme de groupes).

Soit $G$ et $H$ deuxs. Une application $f: G \rightarrow H$ est un homomorhisme de groupes si elle vérifie \[f(g_1 \star g_2) = f(g_1) \star f(g_2)\] quels que soient $g_1, g_2\in G$. C’est un isomorphisme si en plus elle est bijective. Less $G$ et $H$ sont isomorphes s’il existe un de $G$ vers $H$.

On peut s’étonner de ne pas trouver l’axiome $f(e_G)=f(e_H)$ dans cette définition. Or cet axiome est une conséquence de la définition. En effet, nous avons \[f(e_G) = f(e_G \star e_G)= f(e_G) \star f(e_G).\] Si nous multiplions cette égalité des deux côtés à gauche par l’inverse de $f(e_G)$ dans $H$, nous trouvons $e_H= f(e_G)$. Notons que cette démonstration utilise l’existence des inverses et qu’elle n’a donc pas d’analogue pour les lois de multiplication des anneaux.
Si $f:G \rightarrow H$ est un isomorphisme de groupes et que $g: H \rightarrow G$ est l’application réciproque à $f$, alors $g$ est un homomorphisme de groupes et même un isomorphisme. Nous laissons au lecteur le soin d’adapter au cadre des groupes la démonstration donnée ci-dessus pour les anneaux.

Soient $A$ et $B$ deuxx et $f: A \rightarrow B$ un homomorphime d’anneaux. Alors nous avons $f(A^\star)\subset B^\star$ et l’application \[f^\star: A^\star \rightarrow B^\star, a \mapsto f(a)\] est un homomorphisme des. C’est un des si $f$ est un d’anneaux.

Supposons que $a\in A$ est inversible d’inverse $a'$. Alors $f(a')$ est inverse à $f(a)$. En effet, nous avons \[f(a) f(a')= f(a a')=f(1_A)= 1_B = f(a') f(a).\] Ainsi, l’application $f$ nous fournit bien une application entre less des élémentss \[f^\star :A^\star \rightarrow B^\star \: , \;a \mapsto f(a).\] Il est immédiat de constater que cette application est un homomorphisme des. Supposons maintenant que $f$ est un d’anneaux et soit $g:B \rightarrow A$ son application réciproque. Alors $g$ est un homomorphisme et donc $g(B^\star)$ est contenu dans $A^\star$. Ceci montre que $a\in A$ est si et seulement si $f(a)$ est dans $B$. Donc dans ce cas $f^*$ est bijective et c’est donc un isomorphisme des.

(Lemme chinois en termes d’anneaux résiduels).

Soient $r$ et $s$ deux entiers $\geq 2$ et premiers entre eux. Alors l’application \[\Phi : { \mathbb Z}/rs{ \mathbb Z}\rightarrow{ \mathbb Z}/r{ \mathbb Z}\times { \mathbb Z}/s{ \mathbb Z}\: , \; ^{rs}\overline{a} \mapsto (^{r}\overline{a}, ^{s}\overline{a})\] est un d’anneaux.

Ainsi nous voyons que tous lesx suivants sont isomorphes \[{ \mathbb Z}/24{ \mathbb Z}\: , \; { \mathbb Z}/3{ \mathbb Z}\times { \mathbb Z}/8{ \mathbb Z}\: , \; { \mathbb Z}/8{ \mathbb Z}\times { \mathbb Z}/3{ \mathbb Z}.\] Nous verrons plus tard que cesx ne sont pas isomorphes à ${ \mathbb Z}/6{ \mathbb Z}\times { \mathbb Z}/4{ \mathbb Z}$.

Vérifions que $\Phi$ est un homomorphisme. En effet pour $a,b\in{ \mathbb Z}$, nous avons \[\begin{aligned} \Phi(^{rs}\overline{a} + ^{rs}\overline{b}) & = & \Phi(^{rs}\overline{a+b}) = (^{r}\overline{a+b}, ^{s}\overline{a+b}) \\ & = & (^{r}\overline{a}+^{r}\overline{b}, ^{s}\overline{a}+^{s}\overline{b}) \\ & = & (^{r}\overline{a}, ^{s}\overline{a}) + (^{r}\overline{b}, ^{s}\overline{b}).\end{aligned}\] De même, on vérifie que $\Phi$ est compatible à la multiplication. Vérifions que $\Phi$ est injective. En effet, si $\Phi(^{rs}\overline{a})=\Phi(^{rs}\overline{b})$, alors nous avons $(^{r}\overline{a}, ^{s}\overline{a})=(^{r}\overline{b}, ^{s}\overline{b})$ et donc \[\begin{aligned} a & \equiv & b\; (r) \\ a & \equiv & b \; (s) .\end{aligned}\] Ainsi la différence $a-b$ est par $r$ est $s$ et donc par le produit $r\,s$, puisque $r$ et $s$ sont premiers entre eux. Donc les classes $^{rs}\overline{a}$ et $^{rs}\overline{b}$ sont égales. Vérifions que $\Phi$ est surjective. En effet soient $a_1, a_2\in { \mathbb Z}$. Alors nous cherchons $a\in { \mathbb Z}$ tel que $(^{r}\overline{a}, ^{s}\overline{a})=(^{r}\overline{a_1}, ^{s}\overline{a_2})$. De façon équivalente, nous cherchons $a\in{ \mathbb Z}$ solution du système \[\begin{aligned} a & \equiv & a_1 \;(r)\newline a & \equiv & a_2 \;(s) \end{aligned}\] Or, puisque $r$ et $s$ sont premiers entre eux, d’après le lemme chinois pour less, il existe une solution $a\in{ \mathbb Z}$.

Lesx ${ \mathbb Z}/rs{ \mathbb Z}$ et ${ \mathbb Z}/r{ \mathbb Z}\times { \mathbb Z}/s{ \mathbb Z}$ ont même cardinal (égal à $r\,s$). Dans la démonstration, il aurait donc suffi de montrer soit la surjectivité soit l’injectivité de l’application $\Phi$ pour conclure qu’elle est en fait bijective. Nous avons donné les deux démonstrations pour mieux établir le lien avec le en termes de congruences.

Soient $r,s$ des entier $\geq 2$ et premiers entre eux. Alors l’application \[\Phi^* : ({ \mathbb Z}/rs{ \mathbb Z})^\star \rightarrow({ \mathbb Z}/r{ \mathbb Z})^\star \times ({ \mathbb Z}/s{ \mathbb Z})^\star \: , \; ^{rs}\overline{a} \mapsto (^{r}\overline{a}, ^{s}\overline{a})\] est un des. En particulier, elle est bijective et le deuxs sont donc du même ordre.

Le corollaire résulte du lemme précédent et du lemme ([anneaux-groupes]).

(l’indicatrice d’Euler).

Soit $n$ un entier $\geq 2$. On définit $\phi(n)$ comme le cardinal du des élémentss de l’anneaux ${ \mathbb Z}/n{ \mathbb Z}$. La fonction $\phi$ est l’indicatrice d’Euler.

Si $r$ et $s$ sont deux entiers $\geq 2$ et premiers entre eux on a \[\phi(rs)=\phi(r)\, \phi(s).\]

Ceci résulte aussitôt de la définition de $\phi(rs)$ et du corollaire ([groupes-mult-iso]).

Le corollaire précédent nous permet de calculer la valeur de $\phi(n)$ pour tout entier dont nous connaissons la décompositions en facteurs premiers. En effet, si nous avons \[n= p_1^{e_1} \, p_2 ^{e_2} \, \ldots \, p_r^{e_r}\] alors en applicant le corollaire plusieurs fois nous trouvons \[\phi(n) = \phi(p_1^{e_1}\, \phi(p_2^{e_2}) \,\ldots \, \phi(p_r^{e_r}).\] Mais d’après [empty], nous savons que pour un $p$ nous avons \[\phi(p^k)= p^k-p^{k-1}.\] Donc \[\phi(n)=(p_1^{e_1}-p_1^{e_1-1}) (p_2^{e_2} - p_2^{e_2-1}) \ldots (p_r^{e_r} - p_r{e_r-1}).\] Par exemple, \[\phi(36)=\phi(4 \times 9) = \phi(4) \, \phi(9) = (4-2)\times (9-3) = 12\] et \[\phi(1995)= \phi(3\times 5\times 7 \times 19) = 864.\]

Notion d’ordre d’un élément d’un groupe

Soit $(G,\star)$ un et $g$ un élément de $G$. Alors il existe une application \[\exp_g : { \mathbb Z}\rightarrow G\] et une seule telle que \[\begin{aligned} \exp_g(1) & = & g \newline \exp_g(k+l) & = & \exp_g(k) \star \exp_g(l)\end{aligned}\] quels que soient $k,l \in{ \mathbb Z}$.

Nous admettons ce résultat.

La seconde condition de la définition signifie que $\exp_g$ est un homomorphisme de groupes de ${ \mathbb Z}$ vers $G$.
Supposons que $(G,\cdot)$ est un groupe dont la loi est notée multiplicativement. Alors pour tout $n$ entier positif, nous avons \[\begin{aligned} \exp_g(n) & = & \underbrace{g\cdot g \cdots g}_{n}= g^n \\ \exp_g(-n) & = & \exp_g(n)^{-1}= (g^{-1})^n.\end{aligned}\] Nous écrirons $g^n$ pour $exp_g(n)$ pour tout $n$ entier.
Supposons que $(A, +)$ est un groupe dont la loi est notée additivement. Alors pour tout $n$ entier positif, nous avons \[\begin{aligned} \exp_a(n) & = & \underbrace{a + a +\cdots + a}_{n} = n\,a \newline \exp_a(-n) & = & - \exp_a(n) = -n\, a.\end{aligned}\] Nous écrirons $n\, a$ pour $\exp_a(n)$ pour tout $n$ entier.

Soit $(G,\cdot)$ un groupe dont la loi est notée multiplicativement et $g$ un élément de $G$. Pour $k,l\in{ \mathbb Z}$, on a les égalités suivantes \[\begin{aligned} g^1 & = & g \\ g^{k+l} & = & g^k \star g^l \\ g^0 & = & e_G \\ (g^k)^l & = & g^{kl}\end{aligned}\]
Soit $(A,+)$ un groupe commutatif dont la loi est notée additivement et $a$ un élément de $A$. Pour $k,l\in{ \mathbb Z}$ on a les égalités suivantes \[\begin{aligned} 1\,a & = & a \\ (k+l) \, a & = & k\, a + l\, a \\ 0 \, a & = & 0_A \newline k \, (l\, a) & = & (kl)\, a\end{aligned}\]

Les deux parties sont des traductions dans la nouvelle notation de certaines propriétés de la fonction $\exp$. Montrons-les dans les de a). Les premières deux égalités ne font que traduire dans la nouvelle notation les propriétés de la définition de $\exp_g$. La troisième propriété résulte du fait que $\exp_g$ est un homomorphisme. Pour la dernière propriété, fixons $k\in{ \mathbb Z}$ et considérons l’application \[f: { \mathbb Z}\rightarrow G, \: , \;l \mapsto g^{kl}.\] Nous avons clairement $f(1)=g^k$ et \[f(l+l')=g^{k(l+l')}= g^{kl+kl'} = g^{kl} \star g^{kl'} = f(l)\star f(l').\] Par l’unicité de l’application $\exp_{g^k}$ nous pouvons conclure que $f(l)=\exp_{g^k}(l)$ pour tout $l\in { \mathbb Z}$ et donc que $f(l)=(g^k)^l$ pour tout $l\in{ \mathbb Z}$.

(L’ordre de $g$).

Soit $(G,\star)$ un et $g$ un élément de $G$. L’ordre de $g$ est le plus petit entier $n\geq 1$ tel que $\exp_g(n)=e_G$ s’il existe un tel entier. Sinon, l’ordre de $g$ est infini. On note $\mbox{ord}_G(g)$ ou $\mbox{ord}\,(g)$ dans $G$.

Supposons que $(G,\cdot)$ est un groupe dont la loi est notée multiplicativement et soit $g\in G$. Alors nous avons \[\mbox{ord}_G\,(g)=\inf\{ n\in{\mathbb N}\; | \; n\geq 1\mbox{ et } g^n=e\}.\] Supposons que $(A,+)$ est un groupe commutatif dont la loi est notée additivement et soit $a\in A$. Alors nous avons \[\mbox{ord}_G\,(a)=\inf\{ n\in{\mathbb N}\; | \; n\geq 1\mbox{ et } n a = 0_A\}.\]
Soit $(G,\cdot)$ un groupe dont la loi est notée multiplicativement (pour alléger les notations). Supposons que $g\in G$ est d’ordre fini $n$. Alors nous avons \[g^{k+n}= g^k\cdot g^n = g^k \cdot e = g^k\] pour tout entier $k$ et $n$ est le plus petit entier $\geq 1$ avec cette propriété. Autrement dit, la suite des puissances de $g$ \[g^0=e\: , \;g \: , \;g^2 \: , \;\ldots, g^k, \ldots\] est périodique de période $n$. Nous avons aussi \[g^{a+kn}= g^a g^{kn}= g^a (g^n)^k = g^a e^k = g^a\] pour tout entier $a\in{ \mathbb Z}$ et tout entier $k\in{ \mathbb Z}$. Autrement dit la valeur de $g^{a}$ ne dépend que de la classe de congruence de $a$ modulo $n$.

Soit $n$ un entier $\geq 2$ et soit $\overline{a}$ une classe modulo $n$ considérée comme élément du $(A,+)=({ \mathbb Z}/n{ \mathbb Z}, +)$. Alors \[\mbox{ord}_{{ \mathbb Z}/n{ \mathbb Z}} (\overline{a}) = \frac{\mbox{PPCM}(a,n)}{a} = \frac{n}{\mbox{PGCD}(a,n)}.\]

Nous avons $k\overline{a}=\overline{0}$ ssi $ka$ est un multiple de $n$, c’est-à-dire un multiple commun à $a$ et $n$. Donc $ka$ doit être un multiple de $\mbox{PPCM}(a,n)$ et $k$ un multiple de $\mbox{PPCM}(a,n)/a$. Compte tenu de l’égalité \[\mbox{PPCM}(a,n) = \frac{a\,n}{\mbox{PGCD}(a,n)}\] nous obtenons aussi la seconde égalité.

Il n’existe pas de formule analogue pour l’ordre d’un élément $\overline{x}$ dans le multiplicatif $({ \mathbb Z}/n{ \mathbb Z})^*$. Cependant nous verrons que cet ordre est toujours un diviseur de $\phi(n)$, l’ordre du $({ \mathbb Z}/n{ \mathbb Z})^*$.

Soit $(G,\star)$ un et $g$ élément de $G$. Alors $g$ est d’ordre infini ssi l’application \[\exp_g: { \mathbb Z}\rightarrow G\] est injective. En particulier, tous les éléments d’un fini sont d’ordre fini.

Si l’application $\exp_g$ est injective nous avons $\exp_g(n)\neq \exp_g(0)$ pour tout $n>0$. Puisque $\exp_g(0)=e$, nous avons donc $\exp_g(n)\neq e$ pour tout $n>0$ et $g$ est d’ordre infini.

Réciproquement supposons $g$ d’ordre infini. Soient $k\leq l$ des entiers tels que $\exp_g(k)=\exp_g(l)$. Alors nous avons $\exp_g(l-k)=e$. Puisque $l-k\geq 0$ et que $g$ est d’ordre infini, il s’ensuit que $k=l$ et donc que $\exp_g$ est injective.

Soit $(G,*)$ un et $g\in G$ un élément d’ordre fini $n$. Alors l’application \[{ \mathbb Z}/n{ \mathbb Z}\rightarrow G\: , \;\overline{a} \mapsto \exp_g(a)\] est bien définie et injective. En particulier, l’ensemble des éléments de la forme $\exp_g(a)$, $a\in{ \mathbb Z}$, est de cardinal $n$.

Supposons pour alléger les que la loi de $G$ est notée multiplicativement. Nous avons donc \[exp_g(a)=g^a \mbox{ et } g^n=e\] pour tout $a\in{ \mathbb Z}$. Donc \[exp_g(a+kn)= g^{a+kn} = g^a g^{kn} = g^a (g^n)^k = g^a e^k = g^a.\] L’application est donc bien définie. Supposons que $a\leq b$ sont deux entiers dont les classes ont même. Alors nous avons $g^a=g^b$ et donc $g^{b-a}=e$. Pour montrer que $n$ divise $b-a$, effectuons la $b-a=qn+r$ de $b-a$ par $n$. Par définition, nous avons $0 \leq r \leq (n-1)$. De l’autre côté, nous avons $e=g^{b-a}= g^r$. Puisque $g$ est d’ordre $n$, il s’ensuit que $n$ divise $b-a$ et donc que $\overline{a}=\overline{b}$.

(Lagrange).

Soit $(G,*)$ un fini. L’ordre de tout élément de $G$ divise l’ordre de $G$.

Considérons le $G=({ \mathbb Z}/11{ \mathbb Z})^*$. L’ordre de $G$ est de $10$. Voici les ordres des éléments de $G$ :

$g$	$\overline{1}$	$\overline{2}$	$\overline{3}$	$\overline{4}$	$\overline{5}$	$\overline{6}$	$\overline{7}$	$\overline{8}$	$\overline{9}$	$\overline{10}$
$\mbox{ord}\,(g)$	$1$	$10$	$5$	$5$	$5$	$10$	$10$	$10$	$5$	$2$

Notons que le nombre d’éléments d’ordre $10$ est de $4=\phi(10)$, le nombre d’éléments d’ordre $5$ est de $4=\phi(5)$ et le nombre d’élḿents d’ordre $2$ est de $1=\phi(2)$. Nous verrons que ce n’est pas un hasard ([nombre-delements-dordre-d]). Nous verrons aussi comment calculer facilement ce tableau (exemples [calcul-ordre])

Pour alléger les, supposons que la loi de $G$ est notée multiplicativement. Soit $g\in G$. La démonstration se fait en plusieurs étapes :

Première étape : la relation définie par \[x \equiv x' \; (g) \Longleftrightarrow x = x' \,g^k \mbox{ pour un } k\in{ \mathbb Z}\: , \;\] est une relation d’équivalence. Nous laissons cette vérification au lecteur. Notons $\overline{x}$ la classe d’équivalence d’un élément $x$. Par définition, la classe de $x$ est formée de tous les éléments de la forme $x\,g^k$, $k\in { \mathbb Z}$.

Seconde étape : le cardinal de la classe de $e$ est l’ordre de $g$. En effet, la classe de $e$ est formée de tous les éléments de la forme $g^k$, $k\in{ \mathbb Z}$. C’est donc l’image de l’application $\exp_g: { \mathbb Z}\rightarrow G$. Nous avons vu au lemme ([sous-groupe-el-fini]) qu’elle est en bijection avec ${ \mathbb Z}/n{ \mathbb Z}$ où $n$ est.

Troisième étape : toutes les classes d’équivalence ont même cardinal que la classe de $e$. En effet, si $x$ est un élément de $G$, nous avons des bijections inverses l’une de l’autre entre $\overline{e}$ et $\overline{x}$ données par les applications $y \mapsto xy$ resp. $z \mapsto x^{-1} z$.

Quatrième étape : le cardinal de la classe de $e$ divise l’ordre de $G$. En effet, nous savons que $G$ est la réunion disjointe des classes d’équivalence. L’ordre de $G$ est donc la somme des cardinaux des classes. Or toutes les classes ont même cardinal que $\overline{e}$. L’ordre de $G$ est donc égal au cardinal de la classe de $e$ multiplié par le nombre de classes d’équivalence.

Conclusion :, qui est égal au cardinal de la classe de $e$ (seconde étape), divise l’ordre de $G$ (troisième étape).

(Théorème d’Euler).

Soit $n$ un entier $\geq 2$ et $a$ un entieravec $n$. Alors on a \[a^{\phi(n)} \equiv 1 \; (n),\] où $\phi$ est.

Comme $a$ estavec $n$, la classe $g=\overline{a}$ appartient au $G=({ \mathbb Z}/n{ \mathbb Z})^*$. L’affirmation résulte du théorème de car $\phi(n)$ est l’ordre du $({ \mathbb Z}/n{ \mathbb Z})^*$ par définition.

(Petit Théorème de Fermat).

Si $p$ est un nombreet $a$ un entier qui n’est pas par $p$, on a \[a^{p-1}\equiv 1\;(p).\]

On applique le théorème d’Euler en utilisant que $\phi(p)=p-1$ pour un.

Les théorèmes de Fermat (petit) et d’Euler permettent de calculer très rapidement certains restes de puissances. Dans les exemples suivants, on cherche le reste $r$ de la de $a$ par $b$ :

$a=67^{100}$, $b=101$ : le nombre $101$ est premier et $67$ n’est pas divisible par $101$. D’après le petit théorème de Fermat, on a $67^{100} \equiv 1 \;(101)$ et donc $r=1$.
$a=1995^{540}$, $b=541$ : le nombre $541$ est premier et $1995$ n’est pas divisible par $541$. D’après le petit théorème de Fermat, on a $1995^{540}\equiv 1\; (541)$ et donc $r=1$.
$a=25^{24}$, $b=72$ : nous avons $\phi(72)= \phi(8\times 9) = \phi(8) \phi(9)= 4\times 6= 24$. Les nombres $72$ et $25$ sont premiers entre eux. Nous pouvons donc appliquer le théorème d’Euler pour conclure que $25^{24}\equiv 1\; (72)$. Donc $r=1$.
$a=51^{24}$, $b=72$ : nous avons $\phi(72)=24$ (voir le numéro précédent). Or, les nombres $51$ et $72$ ne sont pas premiers entre eux et nous ne pouvons pas appliquer le théorème d’Euler. Cependant, soit $x = 51^{24}$. D’après le lemme chinois, pour connaı̂tre la classe de $x$ modulo $72$, il suffit de connaı̂tre les restes de $x$ modulo $8$ et modulo $9$. Or \[\begin{aligned} x & \equiv & 51^{24} \equiv 3^{24} \equiv 1 \;\;(8) \\ x & \equiv & 51^{24} \equiv 6^{24} \equiv 0 \;\;(9).\end{aligned}\] Ici, nous avons appliqué le théorème d’Euler à $3$ et $8$ ($\phi(8)=4$) et nous avons utilisé le fait que $6^2\equiv 0 \;(9)$. Le lemme chinois nous permet de conclure que $x \equiv 9\;(72)$ et le reste recherché est donc $r=9$.

Algorithme de calcul rapide des puissances

Soit $G$ un dont la loi est notée multiplicativement. Soit $g$ un élément de $G$ et $n$ un entier $\geq 2$. Pour calculer $g^n$, on utilise l’algorithme suivant qui consiste à construire récursivement des suites $x_k, y_k, q_k$, $k\geq 1$, où $x_k, y_k \in G$ et $q_k \in {\mathbb N}$ :

Initialisation : on pose $x_1=g$, $y_1=e$, $q_k=n$.
Passage à l’étape $k$ : on pose $x_k=x_{k-1}^2$, on prend pour $q_k$ le quotient de la division de $q_{k-1}$ par $2$ et on pose \[y_k= \left\{ \begin{array}{cc} y_{k-1} & \mbox{si $q_{k-1}$ est pair} \\ x_{k-1} y_{k-1} & \mbox{si $q_{k-1}$ est impair} \end{array} \right.\]
Arrêt : quand $q_k=1$, l’algorithme s’arrête et la puissance recherchée est $g^n=x_k y_k$.

Dans la pratique, on organise les suites $x_k, y_k, q_k$ dans un tableau. Voir les exemples ci-dessous.

Calculons $2^{50}$ dans $({ \mathbb Z}/101{ \mathbb Z})^*$ :

$k$	$x_k$	$y_k$	$q_k$
1	2	1	50
2	4	1	25
3	16	4	12
4	54	4	6
5	88	4	3
6	68	49	1
		100

Nous trouvons donc que $2^{50} \equiv -1 \; (101)$. La première colonne ne dépend que de $g=2$ et nous pouvons la réutiliser. Dans le tableau suivant, nous utilisons deux fois la même première colonne pour calculer $3^{50}$ et $3^{20}$ dans $({ \mathbb Z}/101{ \mathbb Z})^*$.

$x_k$	$y_k$	$q_k$	$y_k$	$q_k$
3	1	50	1	20
9	1	25	1	10
81	9	12	1	5
97	9	6	81	2
16	9	3	81	1
54	43	1
	100		84

L’algorithme décrit ci-dessus est correct.

Nous allons montrer par récurrence que nous avons $x_k^{q_k}\,y_k=g^n$. Ceci entraı̂nera l’affirmation car pour $q_k=e$, cette égalité se spécialise en $x_k y_k=g^n$. A l’étape $k=1$, l’affirmation est vraie par définition de l’initialisation de l’algorithme. Supposons qu’elle est vraie pour l’étape $k-1$ et montrons-la pour l’étape $k$. Soit $q_{k-1}= 2\, q_k+r_k$ la division euclidienne de $q_{k-1}$ par $2$. Par l’hypothèse de récurrence, nous avons \[x_{k-1}^{q_{k-1}} y_{k-1}=g^n.\] Si nous substituons le résultat de la division euclidienne pour $q_{k-1}$, nous trouvons \[g^n= x_{k-1}^{2\, q_k +r_k}y_{k-1} = (x_{k-1}^2)^{q_k} (x_{k-1}^{r_k}) y_{k-1} = x_k^{q_k} y_k.\] Pour la dernière égalité, nous avons utilisé la définition de $x_k$ et $y_k$ (le nombre $q_{k-1}$ est pair ssi $r_k=0$).

Calcul de l’ordre d’un élément

Soit $n$ un entier. Un diviseur positif $d$ de $n$ est maximal s’il est de la forme $n/p$ où $p$ est un diviseurde $n$. Soit $G$ un fini dont la loi est notée multiplicativement. Soit $g$ un élément de $G$. Soit $n$ un entier positif.

On a $g^n=e$ si et seulement si $n$ est un multiple de l’ordre de $g$.
L’élément $g$ est d’ordre $n$ si et seulement si $g^n=e$ et $g^d\neq e$ pour tout diviseur maximal de $n$.
Si $g$ est d’ordre $n$ et $d$ divise $n$, alors $g^d$ est d’ordre $n/d$.
Plus généralement, si $g$ est d’ordre $n$ et $a$ un entier quelconque, alors $g^a$ est d’ordre $n/\mbox{PGCD}(a,n)$.

a) Ceci est clair d’après le lemme [Zn-iso-puiss-g] qui affirme que l’application ${ \mathbb Z}/\mbox{ord}(g){ \mathbb Z}\rightarrow G$, $\overline{k} \mapsto g^k$ est injective.

b) La condition est clairement nécessaire. Supposons réciproquement qu’elle est vérifié. Alors $n$ est multiple de l’ordre de $g$ d’après a), mais aucun diviseur propre de $n$ n’est multiple de l’ordre de $g$. (tout diviseur propre divise un diviseur maximal de $n$). Donc $n=\mbox{ord}(g)$.

c) Nous avons $(g^d)^k=g^{dk}$ ce qui donne immédiatement l’affirmation.

d) D’après le lemme [Zn-iso-puiss-g], nous avons $g^k=e$ ssi $\overline{k}=\overline{0}$ dans ${ \mathbb Z}/n{ \mathbb Z}$. Donc l’ordre de $g^a$ est égal à l’ordre de $\overline{a}$ dans ${ \mathbb Z}/n{ \mathbb Z}$. Ce dernier est égal à $n/\mbox{PGCD}(a,n)$ d’après le lemme [ordre-dans-Zn-additif].

Pour déterminer l’ordre de $g$, on calcule les puissances $g^d$ pour les diviseurs maximaux $d$ de $n$. Si on a $g^d\neq e$ pour tout diviseur maximal, alors $g$ est d’ordre $n$ (et $G$ est engendré par $g$ voir ci-dessous). Sinon, on a $g^d=e$ pour un diviseur maximal $d$ de $n$ et on recommence avec $n$ remplacé par $d$. Dans le calcul des puissances $g^{d'}$ pour les diviseurs maximaux $d'$ de $d$ on pourra cependant omettre tous ceux qui divisent un diviseur maximal $d''$ de $n$ pour lequel $g^{d''}\neq e$. Voir l’exemple suivant.

)

Calculons l’ordre de $2$ dans $({ \mathbb Z}/113{ \mathbb Z})^*$. Ce est d’ordre $n=112=7\times 16$. Les diviseurs maximaux de $n$ sont $16$ et $56$. Calculons donc $2^{56}$ et $2^{16}$.

$x_k$	$y_k$	$q_k$	$y_k$	$q_k$
2	1	56	1	16
4	1	28	1	8
16	1	14	1	4
30	1	7	1	2
109	30	3	1	1
16	106	1
	1		109

Ainsi $2^{16}\neq e$ et $2^{56}=e$. Les diviseurs maximaux de $56$ sont $8$ et $28$. Puisque $2^{16}\neq e$ nous avons $2^8\neq e$ et il suffit de calculer $2^{28}$. On trouve $2^{28}=1$. Les diviseurs maximaux de $28$ sont $4$ et $14$. Puisque $2^{8}\neq 1$, nous avons $2^4\neq 1$ et il suffit de calculer $2^{14}$. On trouve $2^{14}=-1$ et l’ordre de $2$ dans $({ \mathbb Z}/113{ \mathbb Z})^*$ est donc de $28$.

Déterminons les ordres des éléments de $({ \mathbb Z}/11{ \mathbb Z})^*$. Calculons l’ordre de $2$. Nous avons $2^{10}\equiv 1\;(11)$ par le petit théorème de Fermat. Les diviseurs maximaux de $10$ sont $2$ et $5$. Nous avons \[2^2=4\: , \;2^5 \equiv 2\times 4\times 4 \equiv -1 \;(11).\] Donc $2$ est d’ordre $10$ et tout élément de $({ \mathbb Z}/11{ \mathbb Z})^*$ est une puissance de $2$ d’après le lemme ([Zn-iso-puiss-g]). Calculons ces puissances

$k$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$2^k$	$1$	$2$	$4$	$8$	$5$	$10$	$9$	$7$	$3$	$6$

Maintenant, on calcule facilement les ordres de tous les éléments à l’aide des parties b) et c) du lemme. Par exemple, on a \[\begin{aligned} \mbox{ord}(3) & = & \mbox{ord}(2^8) = \frac{10}{\mbox{PGCD}(10,8)} = 5 \\ \mbox{ord}(4) & = & \mbox{ord}(2^2) = \frac{10}{2} = 5.\end{aligned}\] On trouve la table suivante (voir [exemple-lagrange])

$g$	$\overline{1}$	$\overline{2}$	$\overline{3}$	$\overline{4}$	$\overline{5}$	$\overline{6}$	$\overline{7}$	$\overline{8}$	$\overline{9}$	$\overline{10}$
$\mbox{ord}\,(g)$	$1$	$10$	$5$	$5$	$5$	$10$	$10$	$10$	$5$	$2$

Groupes cycliques

(sous-groupe).

Soit $(G,*)$ un. Un sous-groupe de $G$ est une partie $H$ de $G$ vérifiant les trois conditions suivantes

$e_G\in H$,
$h\star k \in H$ pour tous les $h,k\in H$,
$h^{-1}\in H$ pour tous les $h\in H$.

Les parties $\{e_G\}$ et $G$ de $G$ sont toujours des sous-groupes. L’intersection de toute famille de sous-groupes est un sous-groupe.
Pour tout $n\in{ \mathbb Z}$, la partie $n{ \mathbb Z}$ est un sous-groupe de $({ \mathbb Z},+)$. Réciproquement, tout sous-groupe de ${ \mathbb Z}$ est de cette forme : en effet, soit $S\subset { \mathbb Z}$ un sous-groupe. Si $S=\{0\}$, alors $S=0{ \mathbb Z}$ et il n’y a rien à démontrer. Sinon, la partie $S$ contient un entier non nul et donc un entier non nul positif (car $x$ appartient à $S$ si $-x$ appartient à $S$). Soit $n$ le plus petit des entiers strictements positifs contenus dans $S$. Alors on a clairement $n{ \mathbb Z}\subset S$. Réciproquement, si $x$ appartient à $S$ et que $x=q\,n+r$ est la division euclidienne de $x$ par $n$, alors $r=x-q\, n$ appartient à $S$ et est positif et inférieur à $n$. Donc $r=0$ et $x\in n{ \mathbb Z}$.
Si $n$ est un entier $\geq 2$ et $d$ un diviseur de $n$, alors $d { \mathbb Z}/n{ \mathbb Z}= \{ \overline{dx} \;| \; x\in{ \mathbb Z}\}$ est un sous-groupe de $({ \mathbb Z}/n{ \mathbb Z},+)$ et tout sous-groupe de ${ \mathbb Z}/n{ \mathbb Z}$ est de cette forme : en effet, si $A\subset { \mathbb Z}/n{ \mathbb Z}$ est un sous-groupe alors $\tilde{A}\subset { \mathbb Z}$ est un sous-groupe qui contient $n{ \mathbb Z}$. Donc $\tilde{A}=d{ \mathbb Z}$ pour un entier $d$. La condition $n{ \mathbb Z}\subset d{ \mathbb Z}$ montre que $n$ est un multiple de $d$.

(sous-groupe engendré par $X$).

Soit $G$ un et $X$ une partie de $G$. On note $<X>$ et on appelle sous-groupe engendré par $X$ la partie de $G$ formée de tous les d’éléments de $X$ et de leurs inverses (par convention on pose $<X>=\{e_G\}$ si $X$ est vide).

Il s’agit bien d’un.

Soit $G$ un (dont la loi est notée multiplicativement) et $g$ un élément de $G$. Alors le engendré par la partie $X=\{g\}$ est égale à $\{ g^k\; | \; k\in{ \mathbb Z}\}$. Ce est isomorphe à ${ \mathbb Z}$ si $g$ est d’ordre infini et isomorphe à ${ \mathbb Z}/n{ \mathbb Z}$ si $g$ est d’ordre fini $n$ d’après les lemmes ([sous-groupe-el-infini]) et ([sous-groupe-el-fini]).

(cyclique).

Un est cyclique s’il contient un élément qui l’engendre : un générateur.

D’après l’exemple précédent, un groupe est soit isomorphe à ${ \mathbb Z}$ soit à ${ \mathbb Z}/n{ \mathbb Z}$ pour un entier $n\geq 1$. Réciproquement, un isomorphe à ${ \mathbb Z}$ ou ${ \mathbb Z}/n{ \mathbb Z}$ est (engendré par l’image de $1$ resp. $\overline{1}$ par un isomorphisme choisi). Un fini d’ordre $n$ est si et seulement si il contient un élément d’ordre $n$.

(1).

$({ \mathbb Z}/p{ \mathbb Z})^*$ est Soit $p$ un. Alors le $({ \mathbb Z}/p{ \mathbb Z})^*$ est.

Le théorème sera démontré plus tard ([dem-cyclique]).

Le théorème ne donne pas de générateur de ce et c’est un problème ouvert de construire un ‘générateur universel et explicite’. On ignore par exemple si la classe de $2$ engendre $({ \mathbb Z}/p{ \mathbb Z})^*$ pour une infinité de nombres premiers $p$ ou non.

Racines de l’unité

(racines).

Soit $G$ un et $l$ un entier $\geq 1$. Nous appellerons racine $l$-ièmes de l’unité dans $G$ les solutions $g\in G$ de l’équation $g^l=e$.

Les $l$-ièmes de l’unité sont exactement les éléments de $G$ dont l’ordre est un diviseur de $l$.

Soit $G$ un d’ordre fini $n$ et $g$ un générateur de $G$. Soit $l$ un entier $\geq 2$ et $R$ l’ensemble des solutions de l’équation \[x^l=e\] dans $G$.

Si $l$ divise $n$, on a \[R=\{ g^{k\,(n/l)} \; | \; k=0, 1, \ldots , l-1\}.\]
Si $l$ est premier avec $n$, on a \[R=\{ e\}.\]
Dans le cas général, posons $l'=\mbox{PGCD}(n,l)$. Alors \[R= \{ g^{k\,(n/l')} \; | \; k=0, 1, \ldots, l'-1\}.\]

On cherche les solutions de l’équation $x^5=1$ dans ${ \mathbb Z}/2011{ \mathbb Z}$. Si $x\in { \mathbb Z}/2011{ \mathbb Z}$ est solution de cette équation, alors $x x^4=1$ et donc $x$ est inversible (d’inverse $x^4$). Ainsi, il revient au même de chercher les solutions de cette équation dans $({ \mathbb Z}/2011{ \mathbb Z})^*$. Or le nombre $p=2011$ estet le $G=({ \mathbb Z}/2011{ \mathbb Z})^*$ est donc ([zpz-cyclique]). En outre $5$ divise l’ordre de $G$ qui est 2010. L’équation admet donc exactement $5$ solutions et ces solutions sont de la forme \[g^0\: , \;h=g^{402}\: , \;h^2=g^{804}\: , \;h^3=g^{1206}\: , \;h^4=g^{1608} \: , \;\] où $g$ est un générateur de $({ \mathbb Z}/p{ \mathbb Z})^*$. Il reste à trouver un générateur et à calculer ces puissances. Si on calcule les puissances maximales de $2$, on trouve que $2^{2010/5}=1$. Donc $2$ n’est pas un générateur. Par contre, les puissances maximales de $3$ sont toutes différentes de $1$ et $3$ engendre donc $({ \mathbb Z}/2011{ \mathbb Z})^*$. Si on calcule $h=3^{402}$, on trouve $h=1328$. L’ensemble des solutions de l’équation $x^5=1$ est donc formé de \[1\: , \;h=1328\: , \;h^2=1948 \: , \;h^3=798 \: , \;h^4= 1958.\]

Comme $G$ est, toute solution $x$ de $x^l=e$ est de la forme $x=g^a$ pour un $a\in{ \mathbb Z}$. Dans le cas de a), on a donc $al \equiv 0\;(n)$ d’après le lemme ([sous-groupe-el-fini]). Cela signifie que $a$ est multiple de $n/l$.

Dans le cas de b), la $al \equiv 0\;(n)$ implique $a\equiv 0\; (n)$ car $l$ est modulo $n$.

Finalement, dans le cas de c), écrivons $l=l' l''$ où $l''$ et $n$ sont premiers entre eux. Alors la congruence $al'l''\equiv 0\;(n)$ est équivalente à $a l'\equiv 0\; (n)$ qui, elle, exprime que $a$ est multiple de $n/l'$.

Soit $G$ un d’ordre $n<\infty$ et $g$ un générateur de $G$. Soit $d$ un diviseur de $n$. Alors l’ensemble des éléments d’ordre $d$ de $G$ est formé des puissances \[g^{k\,n/d}\] où $k$ parcourt les classess modulo $d$. Ces éléments sont deux à deux distincts. En particulier, le nombre d’éléments d’ordre $d$ dans $G$ est égal à $\phi(d)$, le nombre de générateurs de $G$ est égal à $\phi(n)$ et on a \[n= \sum_{d| n} \phi(d).\]

Le nombre $p=2011$ estet le $G=({ \mathbb Z}/p{ \mathbb Z})^*$ est donc cyclique (théorème [zpz-cyclique]) d’ordre $2010= 2\times 3\times 5 \times 67$. Ce groupe contient donc $\phi(2010)= 2\times 4 \times 66= 528$ générateurs.

Soit $x=g^a$ un élément d’ordre $d$ de $G$. Alors d’après le théorème [racines-liemes], nous avons $a=k\, n/d$ pour un $k\in{ \mathbb Z}$. Si $f$ est un facteur commun à $k$ et $d$, alors on a $(g^a)^{(d/f)}=e$. Puisque $g^a$ est d’ordre $d$, il s’ensuit $f=\pm 1$. Les éléments de l’affirmation sont deux à deux distincts d’après le lemme ([sous-groupe-el-fini]). La dernière affirmation s’ensuit parce que $G$ est la réunion disjointe de ses parties formées des éléments d’ordre $d$, où $d$ parcourt les diviseurs $d$ de $n$, d’après le théorème de ([lagrange]).

Structure du groupe des classes inversibles modulo un nombre premier

Nous démontrerons dans cette section le théorème ([zpz-cyclique]) qui affirme que le $({ \mathbb Z}/p{ \mathbb Z})^*$ est cyclique lorsque $p$ est premier. Nous aurons besoin du

Soit $p$ un. Si \[P(X)=a_n X^n + a_{n-1} X^{n-1} + \ldots + a_1 X + a_0\] est un polynôme de degré $n$ à coefficients $a_i$ dans ${ \mathbb Z}/p{ \mathbb Z}$, alors l’équation $P(x)=0$ admet au plus $n$ solutions $x$ dans ${ \mathbb Z}/p{ \mathbb Z}$.

On appelle racines de $P(X)$ les solutions $x$ de $P(x)=0$.

Nous procédons par récurrence sur $n$. Si $n=1$, l’équation $P(x)=0$ devient $a_1 x + a_0=0$. Elle admet $x=-a_0/a_1$ pour unique solution (le coefficient $a_1$ est non nul car $P(X)$ est de degré $1$). Supposons l’affirmation démontrée pour des de degré $<n$ et soit $P(X)$ de degré $n$. Supposons que $P(x)=0$. Comme pour des à coefficients réels (ou à coefficients dans tout autre) nous pouvons écrire la du polynôme $P(X)$ par le polynôme $(X-x)$ \[P(X)=(X-x)\, Q(X) + R(X)\: , \;\] où $Q(X)$ est un polynôme de degré $n-1$ (le quotient) et $R(X)$ un polynôme de degré $<1$ (le reste) car $X-x$ est de degré $1$. Donc $R(X)=c_0$ pour un $c_0\in{ \mathbb Z}/p{ \mathbb Z}$. Si nous remplaçons $X$ par $x$ dans l’équation de la division euclidienne nous trouvons \[0=0\times Q(x) + c_0\] et donc $c_0=0$. Ainsi, nous avons $P(X)=Q(X)\,(X-x)$. Si $P(X)$ s’annule en $y$, alors on a $Q(y)=0$ ou $y-x=0$ car ${ \mathbb Z}/p{ \mathbb Z}$ est un. Ainsi toute solution $y\neq x$ de $P(X)=0$ est solution de $Q(X)=0$ et par l’hypothèse de récurrence on conclut que $P(X)$ admet au plus $n-1$ différentes de $x$, c’est-à-dire $n$ au total.

Soit $G$ un d’ordre fini $n$ et tel que l’équation $x^d=e$ admet au plus $d$ solutions dans $G$ pour tout diviseur $d$ de $n$. Alors $G$ est.

Pour un diviseur $d$ de $n$, notons $\psi(d)$ le nombre d’éléments d’ordre $d$ de $G$. Supposons que $d$ est un diviseur de $n$ et qu’il existe dans $G$ un élément $g$ d’ordre $d$. Considérons le $<g>$ engendré par cet élément. Il est d’ordre $d$ et chacun de ses éléments est solution de l’équation $x^d=e$ dans $G$. Ainsi, d’après l’hypothèse sur $G$, toute solution de $x^d=e$ dans $G$ se trouve en fait dans le $<g>$. En particulier, tout élément d’ordre $d$ de $G$ se trouve dans ce. Or nous savons qu’un contient exactement $\phi(d)$ éléments d’ordre $d$ (lemme [nombre-delements-dordre-d]). Ainsi, le $G$ contient exactement $\phi(d)$ éléments d’ordre $d$. Nous avons donc $\psi(d)=\phi(d)$ si $\psi(d)>0$ et $\psi(d)=0$ sinon. De toute façon, nous avons $\psi(d)\leq \phi(d)$. Par conséquent, nous avons \[n= \sum_{d | n} \psi(d) \leq \sum_{d | n} \phi(d) =n\: , \;\] où la dernière égalité provient du lemme ([nombre-delements-dordre-d]). Nous avons donc $\psi(d)=\phi(d)$ pour tout diviseur $d$ de $n$ et en particulier, le $G$ contient $\phi(n)$ éléments d’ordre $n$. Il nous aurait suffi d’un seul pour conclure que $G$ est d’ordre $n$.

(=Théorème [zpz-cyclique]) Si $p$ est premier, le $({ \mathbb Z}/p{ \mathbb Z})^*$ est cyclique.

En effet, appliquons le lemme précédent à $G=({ \mathbb Z}/p{ \mathbb Z})^*$. D’après le lemme ([racines-dans-un-corps]), l’équation $X^d -1 =0$ admet au plus $d$ solutions pour tout diviseur $d$ de $n$ (et même pour tout $d\in{\mathbb N}$).

Structure du groupe des classes inversibles modulo une puissance d’un nombre premier

Soit $p$ un et $1\leq k \leq p-1$. Alors le coefficient binomial $C^k_p$ est par $p$.

En effet, nous avons \[C^k_p = \frac{p !}{k! \, (p-k)!} = \frac{p\, (p-1)\, (p-2) \, \ldots \,(p-k+1)}{1\times 2\times 3\times \ldots \times k}.\] Puisque $0<k<p$, le numérateur comporte un facteur $p$, mais le dénominateur n’en comporte pas.

Soit $p$ un nombre premier $>2$ et $k$ un entier $\geq 1$. Alors le groupe $G=({ \mathbb Z}/p^k{ \mathbb Z})^*$ est cyclique d’ordre $(p-1)\,p^{k-1}$. La classe de $1+p$ est un élément d’ordre $p^{k-1}$ dans $G$.
Le groupe $({ \mathbb Z}/2{ \mathbb Z})^*$ est trivial, le groupe $({ \mathbb Z}/4{ \mathbb Z})^*$ est cyclique d’ordre $2$ et pour $k\geq 2$, le groupe $({ \mathbb Z}/2^k{ \mathbb Z})^*$ est isomorphe à ${ \mathbb Z}/2{ \mathbb Z}\times { \mathbb Z}/2^{k-2}{ \mathbb Z}$. Dans ce dernier cas, l’élément $5$ est d’ordre $2^{k-2}$ dans $({ \mathbb Z}/2^k{ \mathbb Z})^*$ et tout élément de ce groupe est de la forme $\pm 5^a$, $a\in{ \mathbb Z}$.

Posons $G=({ \mathbb Z}/p^k{ \mathbb Z})^*$ resp. $G=({ \mathbb Z}/2^k{ \mathbb Z})^*$.

a) Première étape : pour $e\geq 0$, nous avons \[(1+p)^{(p^e)} \equiv 1+ p^{e+1} \; (p^{e+2}).\] Procédons par récurrence sur $e$. Pour $e=0$ l’affirmation est trivialement vraie. Supposons la démontrée pour $e$. Nous avons donc \[(1+p)^{(p^e)} = 1 + p^{e+1}(1 + x p)\] pour un $x\in { \mathbb Z}$. Alors \[\begin{aligned} (1+p)^{p^{e+1}} & = & ((1+p)^{(p^e)})^p = (1 + p^{e+1}(1+xp))^p \\ & = & 1+ p\, p^{e+1}(1+xp) + (\sum_{k=2}^{p-1} C^k_p p^{k(e+1)}(1+xp)^k) + p^{p(e+1)}(1+xp)^{p}.\end{aligned}\] Si nous réduisons modulo $p^{e+3}$ nous trouvons $1+p^{e+2}$ car les $C^k_p$ sonts par $p$ et $p(e+1)\geq 3$ puisque $p\geq 3$.

Notons $\phi: ({ \mathbb Z}/p^k{ \mathbb Z})^* \rightarrow({ \mathbb Z}/p{ \mathbb Z})^*$ l’application qui à $x$ associe sa classe modulo $p$. Clairement, $\phi$ est un homomorphisme de. Notons $H$ le noyau de $\phi$, c’est-à-dire l’ensemble de $x\in G$ tels que $\phi(x)=e$. C’est clairement un sous-groupe.

Seconde étape : L’élément $1+p$ est un générateur de $H$. En particulier, il est d’ordre $p^{k-1}$. Clairement, $H$ est formé des éléments $1+x$ où $x$ est par $p$ (dans ${ \mathbb Z}/p^k{ \mathbb Z}$). Donc $H$ est d’ordre $p^{k-1}$. L’élément $1+p$ appartient à $H$. Son ordre est donc une puissance de $p$. D’après la première partie c’est $p^{k-1}$.

Troisième étape : construction d’un élément d’ordre $p-1$. Soit $x_0$ un générateur de $({ \mathbb Z}/p{ \mathbb Z})^*$ et $x_1\in G$ un élément tel que $\phi(x_1)=x_0$. Si on a $x_1^k=e$ alors on a $\phi(x_1)^k=e$ et l’ordre de $x_1$ est donc un multiple de l’ordre de $x_0$. Par conséquent, l’ordre de $x_1$ est de la forme $(p-1)\, p^l$ pour un $l\in {\mathbb N}$. Posons $x=x_1^{p^l}$. Alors $x$ est d’ordre $p-1$ d’après le lemme [calcul-des-ordres].

Quatrième étape : l’affirmation. Avec les notations introduites ci-dessus, considérons l’élément $x\, (1+p)$. Il est d’ordre $(p-1)\,p^{k-1}$ d’après le lemme ci-dessous.

b) Première étape : pour $e\geq 0$, nous avons \[5^{(2^e)} \equiv 1+ 2^{e+2} \; (2^{e+3}).\] Procédons par récurrence. Pour $e=0$, l’affirmation est trivialement vraie. Supposons-la démontrée pour $e$. Alors nous avons \[\begin{aligned} 5^{(2^{e+1})} & = & (1+2^{e+2}(1+2\,x))^2 \newline & = & 1 + 2\times 2^{e+2}(1+2\,x) + 2^{2\,e+4}(1+2\,x)^2.\end{aligned}\] Si nous réduisons modulo $2^{e+4}$, nous trouvons bien $1+2^{e+3}$.

Notons $\phi: ({ \mathbb Z}/2^k{ \mathbb Z})^* \rightarrow({ \mathbb Z}/4{ \mathbb Z})^*$ l’application qui à $x$ associe sa classe modulo $4$. Clairement, $\phi$ est un homomorphisme de. Notons $H$ le noyau de $\phi$, c’est-à-dire l’ensemble de $x\in G$ tels que $\phi(x)=e$. C’est clairement un sous-groupe.

Seconde étape : L’élément $5$ est un générateur de $H$. En particulier, il est d’ordre $2^{k-2}$. Clairement, $H$ est formé des éléments $1+x$ où $x$ est par $4$ (dans ${ \mathbb Z}/2^k{ \mathbb Z}$). Donc $H$ est d’ordre $2^{k-2}$. L’élément $5$ appartient à $H$. Son ordre est donc une puissance de $2$. D’après la première partie c’est $2^{k-2}$.

Troisième étape : l’affirmation. Considérons l’application \[f: { \mathbb Z}/2{ \mathbb Z}\times { \mathbb Z}/2^{k-2}{ \mathbb Z}\rightarrow({ \mathbb Z}/2^k{ \mathbb Z})^* \: , \; (\overline{a},\overline{b}) \mapsto (-1)^a\,5^b.\] On vérifie aisément que c’est un homomorphisme de. En outre, $f$ est surjectif (quel que soit $x\in G$, on a $x\in H$ ou $-x\in H$). Comme les deuxs sont d’ordre $2^{k-1}$, il s’ensuit que $f$ est bijectif. Donc $f$ est un.

Soit $G$ un noté multiplicativement et soient $g,h$ deux éléments d’ordre fini $a,b$ de $G$ tels que $gh=hg$ et $a$, $b$ sont premiers entre eux. Alors $gh$ est d’ordre $ab$.

En effet, pour $k\in{ \mathbb Z}$, nous avons $(gh)^k=g^k\,h^k=e$ si et seulement si $g^k=h^{-k}$. L’ordre de l’élément $g^k=h^{-k}$ est donc un diviseur commun à $\mbox{ord}g$ et $\mbox{ord}h$. Comme ces nombres sont premiers entre eux, l’ordre de $g^k=h^{-k}$ est égal à $1$ et $g^k=h^{-k}=e$. Cela veut dire que $k$ est multiple de $a$ et de $-b$. Puisque les deux sont premiers entre eux, $k$ doit être multiple du produit $ab$. Réciproquement, nous avons $(gh)^{ab}= (g^a)^b \, (h^b)^a=e$.

En combinaison avec le lemme chinois, le théorème [structure-inversibles-p-puissance] permet de déterminer la structure du $({ \mathbb Z}/n{ \mathbb Z})^*$ pour tout entier $n$ dont on connaı̂t la décomposition en produit de facteurs premiers. Par exemple, considérons $n=3\times 5^3\times 7^2$. Alors, par le théorème chinois, nous avons un \[({ \mathbb Z}/n{ \mathbb Z})^* \stackrel{_\sim}{\rightarrow}({ \mathbb Z}/3{ \mathbb Z})^* \times ({ \mathbb Z}/5^3{ \mathbb Z})^* \times ({ \mathbb Z}/7^2{ \mathbb Z})^*.\] Le théorème [structure-inversibles-p-puissance] donne dess $({ \mathbb Z}/3{ \mathbb Z})^*\stackrel{_\sim}{\rightarrow}{ \mathbb Z}/2{ \mathbb Z}$, $({ \mathbb Z}/5^3{ \mathbb Z})\stackrel{_\sim}{\rightarrow}{ \mathbb Z}/100{ \mathbb Z}$, ${ \mathbb Z}/7^2{ \mathbb Z}\stackrel{_\sim}{\rightarrow}{ \mathbb Z}/42{ \mathbb Z}$. Donc on a \[({ \mathbb Z}/n{ \mathbb Z})^* \stackrel{_\sim}{\rightarrow}{ \mathbb Z}/2{ \mathbb Z}\times { \mathbb Z}/100{ \mathbb Z}\times { \mathbb Z}/42{ \mathbb Z}.\] Cela montre par exemple que le nombre de solutions de l’équation $x^4=1$ dans ${ \mathbb Z}/n{ \mathbb Z}$ est égal à $2\times 4\times 2=16$. Nous laissons au lecteur le soin de calculer explicitement ces 16 solutions.

L’indicatrice de Carmichael

(Indicatrice de Carmichael).

Soit $n$ un entier $\geq 2$. On définit $\lambda(n)$ comme le des ordres des éléments du $({ \mathbb Z}/n{ \mathbb Z})^*$. On appelle indicatrice de Carmichael l’expression $\lambda(n)$.

Si $p$ est premier, on a $\lambda(p)=\phi(p)=p-1$ car le $({ \mathbb Z}/p{ \mathbb Z})^*$ est cyclique d’ordre $p-1$.

(Théorème de Carmichael).

On a $a^{\lambda(n)}\equiv 1\; (n)$ pour tout entier $a$à $n$. Réciproquement, si $m$ vérifie $a^m\equiv 1\;(n)$ pour tout entier $a$à $n$, alors $m$ est multiple de $\lambda(n)$.

Soit $a\in({ \mathbb Z}/n{ \mathbb Z})^*$ un élément d’ordre $u=\lambda(n)$ et $b\in({ \mathbb Z}/n{ \mathbb Z})^*$ un élément d’ordre $v$. Nous allons montrer que $({ \mathbb Z}/n{ \mathbb Z})^*$ contient un élément dont l’ordre est $\mbox{PPCM}(u,v)$. Il s’ensuivra que $\lambda(n)=\mbox{PPCM}(u,v)$ et donc que $v$ divise $\lambda(n)$.

Pour cela, écrivons $\mbox{PPCM}(u,v)=u'v'$, où $u'$ divise $u$, $v'$ divise $v$ et $u'$, $v'$ sont premiers entre eux. Alors $a^{u/u'}$ est d’ordre $u'$, $b^{v/v'}$ est d’ordre $v'$ et donc leur produit est d’ordre $u'v'=\mbox{PPCM}(u,v)$ d’après le lemme [ordre-du-produit].

La deuxième affirmation est claire.

On a $\lambda(2)=1$, $\lambda(4)=2$ et $\lambda(2^k)=2^{k-2}$ pour tout $k\geq 3$.
Si $p$ est un nombre premier impair, on a $\lambda(p^k)= \phi(p^k)= (p-1)p^{k-1}$.
Si $n=rs$ où $r$ et $s$ sont premiers entre eux, on a $\lambda(n)=\mbox{PPCM}(\lambda(r),\lambda(s))$.

Ce lemme permet de calculer l’indicatrice de Carmichael de tout nombre dont on connaı̂t la décomposition en facteurs premiers. Par exemple, on a \[\lambda(561)= \lambda(3\times 11\times 17) = \mbox{PPCM}(2, 10, 16 )= 80.\] En particulier, comme $80$ divise $560$, nous avons \[a^{560}\equiv 1 \; (561)\] pour tout $a$à 561 (comme dans le petit théorème de Fermat). Un nombre $n$ tel que $a^{n-1} \equiv 1\;(n)$ pour tout entier $a$à $p$ s’appelle un nombre de Carmichael. Voici le tableau des premiers $17$ nombres de Carmichael non premiers.

$i$	$n$	décomposition	$\lambda(n)$
$1$	$561$	$3\times11\times17$	$80$
$2$	$1105$	$5\times13\times17$	$48$
$3$	$1729$	$7\times13\times19$	$36$
$4$	$2465$	$5\times17\times29$	$112$
$5$	$2821$	$7\times13\times31$	$60$
$6$	$6601$	$7\times23\times41$	$1320$
$7$	$8911$	$7\times19\times67$	$198$
$8$	$10585$	$5\times29\times73$	$504$
$9$	$15841$	$7\times31\times73$	$360$
$10$	$29341$	$13\times37\times61$	$180$
$11$	$41041$	$7\times11\times13\times41$	$120$
$12$	$46657$	$13\times37\times97$	$288$
$13$	$52633$	$7\times73\times103$	$1224$
$14$	$62745$	$3\times5\times47\times89$	$2024$
$15$	$63973$	$7\times13\times19\times37$	$36$
$16$	$75361$	$11\times13\times17\times31$	$240$
$17$	$101101$	$7\times11\times13\times101$	$300$

Les parties a) et b) résultent du théorème [structure-inversibles-p-puissance]. Pour c), nous avons l’isomorphisme des \[({ \mathbb Z}/n{ \mathbb Z})^* \stackrel{_\sim}{\rightarrow}({ \mathbb Z}/r{ \mathbb Z})^* \times ({ \mathbb Z}/s{ \mathbb Z})^*\] donné par le. L’ordre d’un couple $(a,b)\in({ \mathbb Z}/r{ \mathbb Z})^*\times({ \mathbb Z}/s{ \mathbb Z})^*$ est clairement égal au $\mbox{PPCM}$ des ordres des deux composantes. Ceci implique que l’ordre maximal d’un couple sera le $\mbox{PPCM}$ des ordres maximaux atteints dans chaque composante.

Résidus quadratiques

(résidu quadratique).

Soit $n\geq 2$ un entier. Une classe $a\in ({ \mathbb Z}/n{ \mathbb Z})^*$ est un résidu quadratique modulo $n$ si $a= b^2$ pour une classe $b$. Dans le cas contraire, la classe $a$ est un non-résidu quadratique.

Dressons les listes des résidus quadratiques modulo quelques nombres premiers \[\begin{aligned} 2 & : & 1 \\ 3 & : & 1 \\ 5 & : & 1, 4 \\ 7 & : & 1, 2, 4 \\ 11 & : & 1,3,4,5,9 \\ 13 & : & 1,3,4,9,10,12 \\ 17 & : & 1,2,4,8,9,13,15,16 \\ 19 & : & 1,4,5,6,7,9,11,16,17 \\ 23 & : & 1,2,3,4,6,8,9,12,13,16,18\newline 29 & : & 1,4,5,6,7,9,13,16,20,22,23,24,25,28\end{aligned}\] Notons qu’il y a $(p-1)/2$ résidus quadratiques pour chacun de ces nombres premiers et que $-1$ est un pour $5,13,29$.

Soit $p=2\,l+1$ un impair.

Parmi les $2l$ éléments de $({ \mathbb Z}/p{ \mathbb Z})^*$ la moitié exactement sont des résidus quadratiques.
Pour tout $a\in({ \mathbb Z}/p{ \mathbb Z})^*$ on a $a^l\equiv \pm 1\; (p)$. On $a^l\equiv 1\; (p)$ si et seulement si $a$ est un résidu quadratique modulo $p$.
La classe de $-1$ est un résidu quadratique modulo $p$ si et seulement si $p\equiv 1\;(4)$.

Le nombre $2011$ estet congru à $3$ modulo $4$. Donc $-1$ n’est pas modulo $2011$. Par contre, à l’aide de l’algorithme de calcul rapide des puissances, on vérifie aisément que $1848^{1005} \equiv 1\; (2011)$. Donc $1848$ est un modulo $2011$.

a) Nous savons que $({ \mathbb Z}/p{ \mathbb Z})^*$ est isomorphe à ${ \mathbb Z}/2l{ \mathbb Z}$. Or ce dernier contient exactement $l$ classes multiples de $2$.

b) Nous avons $(a^l)^2\equiv a^{p-1} \equiv 1\;(p)$ d’après le petit théorème de Fermat ([fermat]). Donc $a^l \equiv \pm 1\;(p)$ (car l’équation $x^2=1$ admet exactement $2$ solutions dans ${ \mathbb Z}/p{ \mathbb Z}$, d’après [racines-liemes]).

Si $a=b^2$, alors $a^k=b^{2\,k}= b^{p-1}=1$ modulo $p$, par le petit théorème de Fermat. Réciproquement, si $a^l= 1$ modulo $p$, alors si $g$ est un générateur de $({ \mathbb Z}/p{ \mathbb Z})^*$, nous avons $a=g^{2\,k}$ pour un $k\in{ \mathbb Z}$ d’après le lemme ([racines-liemes]). Donc $a$ est un carré.

c) D’après a), la classe de $-1$ est un ssi $(-1)^l \equiv 1\; (p)$, c’est-à-dire que $l$ est pair ou encore que $p=2l+1$ vérifie $p\equiv 1\;(4)$.

(Conjecture d’Euler).

Soit $a$ un entier non nul et $p$ un impair. Le fait que $a$ soit modulo $p$ ou non ne dépend que de la classe de $p$ modulo $4a$.

La conjecture, due à Euler, fut démontrée pour la première fois par C. F. Gauss en 1796 sous le nom de ‘théorème d’or’. Nous allons donner la démonstration dans une section ultérieure.

Nous avons déjà vu que $-1$ est un carré modulo $p$ si et seulement si $p$ est congru à $1$ modulo $4$, ou encore modulo $-4=4(-1)$.

D’après le théorème, le fait que $2$ soit un carré modulo $p$ ne dépend que de la classe de $p$ modulo $8$. Or $2$ est non pour $3$ et $5$, il est pour $7$ ($4^2=2$) et pour $17$ ($6^2=2$). Donc $2$ est un carré modulo $p$ ssi $p\equiv\pm 1 \;(8)$.

Nous verrons plus tard que le calcul des classes de nombres premiers $p$ modulo lesquels $a$ est un peut toujours se ramener à $a=2$ et $a=-1$.

Le symbole de Legendre

(symbole de Legendre).

Soit $p$ un et $a$ un entier. On pose \[\left(\frac{a}{p}\right) = \left\{ \begin{array}{cl} 0 & \mbox{si $p$ divise $a$} \\ 1 & \mbox{si $a$ est modulo $p$} \newline -1 & \mbox{si $a$ est non \'residu quadratique modulo $p$} \end{array} \right.\] On appelle symbole de Legendre l’expression $(\frac{a}{p})$.

Par définition, le symbole de Legendre $(\frac{a}{p})$ ne dépend que de la classe de $a$ modulo $p$. Pour un impair, onn a $(\frac{-1}{p})=1$ ssi $p$ est congru à $1$ modulo $4$ et $(\frac{2}{p})=1$ ssi $p$ est congru à $\pm 1$ modulo $8$. Si on tient à des formules explicites, on peut écrire \[(\frac{-1}{p})= (-1)^{\frac{p-1}{2}} \quad (\frac{2}{p})= (-1)^{\frac{p^2-1}{8}}.\]

Soit $p=2\,l+1$ un impair.

On a $(\frac{a}{p})\equiv (-1)^l \; (p)$.
On a $(\frac{ab}{p})= (\frac{a}{p}) (\frac{b}{p})$ pour tous entiers $a,b$ et $(\frac{a^2\, b}{p})=(\frac{b}{p})$ si $a$ n’est pas divisible par $p$.

a) résulte du lemme [lemme-prelim] a) et b) de a).

Pour deux entiers $a$, $b$, on pose \[\theta(a,b)=\left\{ \begin{array}{cl} -1 & \mbox{si $a\equiv 3\;(4)$ et $b\equiv 3\;(4)$} \newline 1 & \mbox{sinon} \end{array} \right.\]

On peut vérifier aisément que pour $a$ et $b$ impairs, on a \[\theta(a,b)= (-1)^{\frac{a-1}{2} \frac{b-1}{2}}.\]

(Loi de réciprocité quadratique).

Si $p$ et $q$ sont deux nombres premiers impairs distincts, on a \[(\frac{p}{q}) (\frac{q}{p})= \theta(p,q).\]

Le théorème est équivalent à la conjecture d’Euler. Il signifie que $(\frac{p}{q})=(\frac{q}{p})$ si $p$ ou $q$ est congru à $1$ modulo $4$, et $(\frac{p}{q})=-(\frac{q}{p})$ dans le cas contraire.

On a toujours $p-q=4a$ ou $p+q=4a$ pour un $a\in { \mathbb Z}$. Supposons d’abord que $p-q=4a$. Alors on a \[(\frac{p}{q})=(\frac{q+4a}{q})= (\frac{4a}{q})=(\frac{a}{q}).\] où nous avons utilisé le lemme [lemme-trivial]. De l’autre côté, nous avons \[(\frac{q}{p})=(\frac{p-4a}{p})=(\frac{-4a}{p})=(\frac{-1}{p}) (\frac{a}{p}).\] Or, d’après la conjecture d’Euler, nous avons $(\frac{a}{p})=(\frac{a}{q})$. Puisque $p$ et $q$ ont même reste par $4$, il s’ensuit que $\theta(p,q)=(\frac{-1}{p})$ ce qui termine la démonstration dans ce cas.

Supposons maintenant que $p+q=4a$. Alors nous avons \[(\frac{p}{q})=(\frac{4a-q}{q})= (\frac{4a}{q})= (\frac{a}{q})\] et de même \[(\frac{q}{p})=(\frac{4a-p}{p})= (\frac{4a}{p})= (\frac{a}{p}).\] Donc d’après la conjecture d’Euler, nous avons $(\frac{p}{q})=(\frac{q}{p})$.

Résumé des propriétés du symbole de Legendre.

Les règles suivantes permettent de calculer tout symbole de Legendre ($p$ et $q$ sont des nombres premiers impairs distincts; $a,a',b$ sont des entiers)

Modularité : \[(\frac{a}{p})=(\frac{a'}{p})\] si $a \equiv a'\;(p)$.
Multiplicativité : \[(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p}).\]
Réciprocité : \[(\frac{p}{q})= \left\{ \begin{array}{cl} -(\frac{q}{p}) & \mbox{si $p\equiv 3\;(4)$ et $q\equiv 3\;(4)$} \\ (\frac{q}{p}) & \mbox{sinon} \end{array} \right.\]
Valeurs particulières : \[(\frac{-1}{p}) = \left\{ \begin{array}{cl} 1 & \mbox{si $p\equiv 1\;(4)$} \\ -1 & \mbox{si $p\equiv 3\;(4)$} \end{array} \right. \: , \;\quad\quad (\frac{2}{p}) = \left\{ \begin{array}{cl} 1 & \mbox{si $p\equiv \pm 1\;(8)$} \newline -1 & \mbox{sinon} \end{array} \right. .\]

Nous montrons comment les règles ci-dessus permettent de calculer $(\frac{541}{2011})$ : \[\begin{aligned} (\frac{541}{2011}) & = & (\frac{2011}{541}) \quad \mbox{ (réciprocité, $541\equiv 1\;(4)$)}) \\ & = & (\frac{388}{541}) \quad \mbox{(modularité, $2011 \equiv 388\;(541)$)} \\ & = & (\frac{2}{541})^2 \,(\frac{97}{541}) \quad \mbox{(multiplicativité, $388=2^2\times 97$)} \\ & = & (\frac{541}{97}) \quad \mbox{(réciprocité, $541\equiv 1\;(4)$)} \\ & = & (\frac{56}{97}) \quad \mbox{(modularité, $541\equiv 56\;(97)$)} \\ & = & (\frac{7}{97})\,(\frac{2}{97})^3 \quad \mbox{(multiplicativité)} \\ & = & (\frac{97}{7})\,(\frac{2}{97})^3 \quad \mbox{(\'reciprocité, $97\equiv 1\;(4)$)} \\ & = & (\frac{-1}{7})\, (\frac{2}{97})^3 \quad \mbox{(modularité)} \newline & = & -1 \quad \mbox{(valeurs particuli\`eres, $(\frac{-1}{7})=-1$, $(\frac{2}{97})= 1$)}\end{aligned}\]

Démonstration de la conjecture d’Euler

Soit $p=2\,l+1$ un impair et $a$ un entier qui n’est pas par $p$. Pour $1\leq k \leq l$, soit $r_k$ le reste de la division de $ka$ par $p$ et soit $\nu$ le nombre de restes $r_k>l$. Alors \[a^l \equiv (-1)^\nu \; (p)\] et en particulier, $a$ est un résidu quadratique modulo $p$ si et seulement si $\nu$ est pair.

Si $a\,i\equiv \pm a\,j\;(p)$, alors comme $a$ est modulo $p$, nous avons $i\equiv \pm j\; (p)$ ce qui est impossible si $i$ et $j$ sont compris entre $1$ et $l$. Donc si nous posons \[s_i=\left\{ \begin{array}{cc} r_i & \mbox{si $1 \leq r_i \leq l$} \newline p-r_i & \mbox{si $l < r_i$} \end{array} \right.\] les $s_i$ sont deux à deux distincts et compris entre $1$ et $l$. Puisque ils sont au nombre de $l$, tout entier entre $1$ et $l$ est égal à un $s_j$. Nous avons \[r_1 r_2 \cdots r_l \equiv (-1)^\nu s_1 s_2 \cdots s_l \equiv (-1)^\nu l\,! \; (p).\] De l’autre côté, nous avons \[r_1 r_2 \cdots r_l \equiv l\, !\, \, a^l\; (p).\] Puisque $l\,!$ est inversible modulo $p$, nous obtenons l’affirmation. La dernière partie résulte du lemme précédent.

Prenons $p=11$ et donc $l=5$. Dans le dessin suivant, nous calculons $\nu$ pour $a$ variant entre $-5$ et $5$. Par exemple, la ligne qui commence par le nombre $2$ comporte $l=5$ points aux abscisses $2,4,6,8,10$. Le nombre de points qui se trouvent dans dess ‘sous-lignés’ est égal à $\nu$. Donc $\nu=3$ et $2$ est un non-résidu quadratique modulo $11$. Les résidus quadratiques modulo 13 sont $-2,1,3,4,5$.

(Conjecture d’Euler).

Soit $a$ un entier non nul et $p$ un impair. Le fait que $a$ soit modulo $p$ ou non ne dépend que de la classe de $p$ modulo $4a$.

D’après le lemme [lemme-cle] et l’exemple qui le suit, il s’agit de compter le nombre $\nu$ de points $ka$, $1\leq k \leq l$, qui se trouvent dans l’un quelconque dess $I_i=[ip/2, (i+1)p/2]$, où $i$ est impair et compris entre $1$ et $a$. En effet, le dernier point, $la=(p-1) a/2$, se trouve dans l’intervalle $[(a-1)p/2, ap/2]$. Supposons que $p'=p+4a$ et que $\nu'$ est le nombre de points correspondant (peu importe si $p'$ n’est pas premier). Alors le nombre d’intervalles $I'_i$ reste le même ($=a$), mais le nombre de points $ka$ augmente de $l'-l=2a$. Je dis que chacun des $a$s $I'_i$ comporte $2$ points $ka$ de plus que l’intervalle $I_i$ correspondant. Ceci impliquera que $\nu'-\nu$ est pair et donc que $(-1)^{\nu'}=(-1)^\nu$. Comparons en effet l’intervalle $I_i$ à l’intervalle $I'_i$ : nous avons \[\begin{aligned} I_i & = & [i\, \frac{p}{2}, (i+1)\, \frac{p}{2}] \\ I'_i & = & [i\, (\frac{p}{2}+2a), (i+1)\, (\frac{p}{2}+2a)] \\ & = & [ i\, \frac{p}{2}+2ia, (i+1)\, \frac{p}{2}+2ia] \cup [ (i+1)\,\frac{p}{2}+2ia, (i+1)\,\frac{p}{2}+2ia+2a].\end{aligned}\] L’intervalle $I'_i$ est donc obtenu à partir de $I_i$ par deux opérations : décalage de $2ia$ et rajout d’un disjoint de longueur $2a$ dont les extrémités ne sont pas multiples de $a$. Or le décalage d’un multiple de $a$ laisse invariant le nombre de points $ka$ contenus dans l’intervalle, et le rajout d’un disjoint de longueur $2a$ dont les extrémités ne sont pas multiples de $a$ rajoute $2$ points $ka$ car tout de longueur $2a$ dont les extrémités ne sont pas des multiples de $a$ comporte exactement $2$ points $ka$ (par mise à l’échelle, on peut supposer que $a=1$ : tout de longueur $2$ dont les extrémités ne sont pas entières comporte exactement $2$ points entiers.)

Bibliographie

Les livres suivants peuvent servir à approfondir les connaissances sur certains sujets traités en cours. Le livre de Weiss [weiss] est rédigé de façon élémentaire et son contenu est relativement proche de celui du cours. Le livre de Gindikin [gindikin] contient des biographies de mathématiciens et physiciens de la renaissance à nos jours et donne des explications élémentaires mais complètes d’un grand nombre de résultats qu’ils ont obtenus. Le chapitre sur est un trésor de perles d’arithmétique. Le cours de Michel Demazure [demazure] contient entièrement le programme de ce cours et le dépasse de loin. Il s’adresse à un public un peu plus avancé. Le livre d’Artin [artin] est très complet, bien rédigé et peut servir du DEUG jusqu’à la maı̂trise.

Les chiffres en gras se reportent à la bibliothèque de Mathématiques du second, Tour 56, rez de chaussée.

Bibliographie

[weiss] Edwin Weiss, A first course in algebra and number theory, Academic Press, 1971. 10 WEI 71.
[gindikin] Simon Gindikin, Horloges, pendules et mécanique céleste, Diderot Editeur, 1995.
[demazure] Michel Demazure, Cours d’algèbre, Notes d’un cours à l’Ecole Polytechnique en Majeure Algèbre et Informatique, Polycopié à paraı̂tre sous forme de livre chez Cassini Editeurs.
[artin] Michael Artin, Algebra, Prentice Hall, 1991. 10 ART 91.

Barre utilisateur

[ID: 88] [Date de publication: 22 janvier 2022 16:24] [Catégorie(s): Le cours d'arithmétique ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Bernhard Keller ]

\(k\)	\(r_k\)	\(q_k\)	\(x_k\)	\(y_k\)
\(1\)	a	\(*\)	\(1\)	\(0\)
\(2\)	b	\(q_2\)	\(0\)	\(1\)	\(a=q_2\,b+ r_3\) est une div. eucl.
\(3\)	\(r_3\)	…	…	…
\(\vdots\)
\(k-1\)	\(r_{k-1}\)	\(q_{k-1}\)	\(x_{k-1}\)	\(y_{k-1}\)
\(k\)	\(r_k\)	\(q_k\)	\(x_k\)	\(y_k\)	\(r_{k-1}=q_k\,r_k+r_{k+1}\) est une div. eucl.
\(k+1\)	\(r_{k+1}\)	\(q_{k+1}\)	\(x_{k+1}\)	\(y_{k+1}\)	\(x_{k+1}=x_{k-1}-q_k x_k\), \(y_{k+1}=y_{k-1}-q_k y_k\)
\(\vdots\)
\(N\)	\(r_N\)	\(q_N\)	\(x_N\)	\(y_N\)
\(N+1\)	\(r_{N+1}=0\)	\(*\)	\(x_{N+1}\)	\(y_{N+1}\)

\(k\)	\(r_k\)	\(q_k\)	\(x_k\)	\(y_k\)
\(1\)	\(198\)	\(*\)	\(1\)	\(0\)
\(2\)	\(75\)	\(2\)	\(0\)	\(1\)
\(3\)	\(48\)	\(1\)	\(1\)	\(-2\)
\(4\)	\(27\)	\(1\)	\(-1\)	\(3\)
\(5\)	\(21\)	\(1\)	\(2\)	\(-5\)
\(6\)	\(6\)	\(3\)	\(-3\)	\(8\)
\(7\)	\(3\)	\(2\)	\(11\)	\(-29\)
\(8\)	\(0\)	\(*\)	\(-25\)	\(66\)

\(i\)	\(n\)	décomposition	\(\lambda(n)\)
\(1\)	\(561\)	\(3\times11\times17\)	\(80\)
\(2\)	\(1105\)	\(5\times13\times17\)	\(48\)
\(3\)	\(1729\)	\(7\times13\times19\)	\(36\)
\(4\)	\(2465\)	\(5\times17\times29\)	\(112\)
\(5\)	\(2821\)	\(7\times13\times31\)	\(60\)
\(6\)	\(6601\)	\(7\times23\times41\)	\(1320\)
\(7\)	\(8911\)	\(7\times19\times67\)	\(198\)
\(8\)	\(10585\)	\(5\times29\times73\)	\(504\)
\(9\)	\(15841\)	\(7\times31\times73\)	\(360\)
\(10\)	\(29341\)	\(13\times37\times61\)	\(180\)
\(11\)	\(41041\)	\(7\times11\times13\times41\)	\(120\)
\(12\)	\(46657\)	\(13\times37\times97\)	\(288\)
\(13\)	\(52633\)	\(7\times73\times103\)	\(1224\)
\(14\)	\(62745\)	\(3\times5\times47\times89\)	\(2024\)
\(15\)	\(63973\)	\(7\times13\times19\times37\)	\(36\)
\(16\)	\(75361\)	\(11\times13\times17\times31\)	\(240\)
\(17\)	\(101101\)	\(7\times11\times13\times101\)	\(300\)

Groupes et Arithmétique : Chapitres choisis

Groupes et Arithmétique : Chapitres choisis

Construction de \({ \mathbb Z}\) à partir de \({\mathbb N}\)

La division euclidienne et ses conséquences

Congruences

Critères de divisibilité

Généralisation à d’autres systèmes de numération

L’algorithme d’Euclide-Bézout

Une autre approche de l’équation de Bézout

Interprétation géométrique

Le lemme chinois en termes de congruences

Systèmes de congruences

Classes de congruence inversibles

Anneaux, groupes et lemme chinois

Notion d’ordre d’un élément d’un groupe

Algorithme de calcul rapide des puissances

Calcul de l’ordre d’un élément

Groupes cycliques

Racines de l’unité

Structure du groupe des classes inversibles modulo un nombre premier

Structure du groupe des classes inversibles modulo une puissance d’un nombre premier

L’indicatrice de Carmichael

Résidus quadratiques

Le symbole de Legendre

Démonstration de la conjecture d’Euler

Bibliographie

Bibliographie

Barre utilisateur

Documents à télécharger

Crédits

Télécharger au format PDF

Sommaire

Catégorie(s)

Continuer à lire

Guide pour les auteures et auteurs de
Les-Mathematiques.net

Les-Mathematiques.net Mathématiques vivantes

Thématiques

À propos

Groupes et Arithmétique : Chapitres choisis

Groupes et Arithmétique : Chapitres choisis

Groupes et Arithmétique : Chapitres choisis

Construction de \({ \mathbb Z}\) à partir de \({\mathbb N}\)

La division euclidienne et ses conséquences

Congruences

Critères de divisibilité

Généralisation à d’autres systèmes de numération

L’algorithme d’Euclide-Bézout

Une autre approche de l’équation de Bézout

Interprétation géométrique

Le lemme chinois en termes de congruences

Systèmes de congruences

Classes de congruence inversibles

Anneaux, groupes et lemme chinois

Notion d’ordre d’un élément d’un groupe

Algorithme de calcul rapide des puissances

Calcul de l’ordre d’un élément

Groupes cycliques

Racines de l’unité

Structure du groupe des classes inversibles modulo un nombre premier

Structure du groupe des classes inversibles modulo une puissance d’un nombre premier

L’indicatrice de Carmichael

Résidus quadratiques

Le symbole de Legendre

Démonstration de la conjecture d’Euler

Bibliographie

Bibliographie

Barre utilisateur

Documents à télécharger

Crédits

Télécharger au format PDF

Sommaire

Catégorie(s)

Guide pour les auteures et auteurs de Les-Mathematiques.net

Lettre d'information

Les-Mathematiques.net Mathématiques vivantes

Thématiques

À propos

Guide pour les auteures et auteurs de
Les-Mathematiques.net