Site http://www.epsilon-publi.net/ - espace http://www.epsilon-publi.net/b/bycart/ de B. Ycart, professeur de mathématique, Université Joseph-Fourier
Niveau bac+1 sciences, cours et QCM : structures algébriques, nombres réels, suites, limites, dérivées, etc.

Pour visualiser le document avec epsilonwriter, cliquer ici

Arithmétique

Bernard Ycart

Licence CC-BY

Origine : M@ths en ligne - Université Joseph Fourier

Document produit en ouvrant un fichier Tex

Mots-clés: nombre premier, division euclidienne, PGCD, PPCM, facteurs premiers, sous-groupe, congruence

 

 

Sommaire

1. Nombres premiers

2. Division euclidienne

3. PGCD et PPCM

4. Lemme de Gauss et décomposition en facteurs premiers

5. Sous-groupes de ℤ 

6. Congruences

7. ℤ/nℤ 


Guère d'introduction tonitruante à faire, sinon pour souligner que ce chapitre a le charme de n'utiliser comme notions admises que les notations de la théorie des ensembles naïve et les connaissances évidentes sur les entiers, et qu'il présente donc l'agrément de donner une image de démonstrations (que l'on espère) totalement crédibles.

 

 

Sommaire

1. Nombres premiers

 

On appelle entier (ou entier relatif, c'est-à-dire positif ou négatif) tout élément de

ℤ={...,-3,-2,-1,0,1,2,3,... 

 

Définition  On dit qu'un entier a  est un multiple d'un entier b  , ou que b  est un diviseur de a  lorsqu'il existe un entier k  tel que a=kb  .

 

Définition  On dit qu'un entier p≥2  est premier lorsqu'il possède pour seuls diviseurs positifs 1  et lui-même.

 

On notera au passage qu'au hasard des définitions, on parlera parfois d'entiers relatifs (les éléments de ℤ  ) et parfois d'entiers naturels (les éléments de ℕ  ). Ce n'est qu'exceptionnellement très significatif ; la principale fonction est d'être cohérent avec le reste du monde. Ainsi, comme partout ailleurs, dans ce cours, le nombre 3  est un nombre premier alors que -3  n'en est pas un. En revanche, les nombres négatifs étant autorisés dans la définition de «diviseurs», l'entier 3  possède en tout et pour tout quatre diviseurs (à savoir -3  , -1  , 1  et 3  ).

 

Et tout de suite un joli théorème, qui remonte aux Éléments d'Euclide, écrits au IIIème siècle avant notre ère (c'est la proposition 20 du livre IX).

 

Théorème  Il existe une infinité de nombres premiers.

 

Vous connaissez probablement déjà une démonstration, il en existe plusieurs qui sont toutes bonnes à connaître, en voici une qui est très proche de celle du traité d'Euclide lui-même.

 

Soit A  l'ensemble des nombres premiers. A  est une partie de ℕ  , et est non vide car 2  est premier. On va supposer A  finie et aboutir à une absurdité.

 

Supposons donc A  finie. Dès lors que A  est une partie finie de ℕ  , évidemment non vide car 2  est premier, A  possède un plus grand élément. Notons P  ce plus grand élément, le mystérieux «plus grand nombre premier».

 

Considérons alors l'entier N=P!+1  (la factorielle de P  , plus 1  ). Pour tout entier k  tel que 2≤k≤P  , comme k  divise P!  et ne divise pas 1  , k  ne peut diviser N  . Tout diviseur de N  , et en particulier tout diviseur premier de N  , est donc strictement supérieur à P  .

 

Or tout entier, et par exemple N  , possède au moins un diviseur premier (pourquoi ? exercice...). Mais alors, chacun de ces diviseurs premiers contredit la maximalité de P  . Absurdité !

 

 

Sommaire

2. Division euclidienne

 

Il s'agit de formaliser avec précision la bonne vieille division euclidienne, celle que vous connaissez depuis l'école primaire.

 

Théorème  Soit a  un entier (relatif) et b≥1  un entier strictement positif. Alors il existe un couple (q,r)  unique (d'entiers) vérifiant la double condition :

a=bq+ret0≤r<b 

 

On va prouver successivement l'existence et l'unicité de (q,r)  .

 

Existence de (q,r)  : la démonstration se prête bien à discuter selon le signe de a  . Le cas où a≥0  est le cas contenant l'essentiel de la démonstration ; lorsque a<0  , on ne peut utiliser mot à mot la même preuve, mais on se ramène alors sans mal au cas intéressant déjà traité.

 

∙  Premier cas (le cas significatif) : si a≥0  .

 

L'idée de la démonstration est de dire que le quotient de a  par b  est le plus grand entier q  tel que bq  soit encore plus petit que a  .

 

Introduisons donc l'ensemble A={c∈ℕ,bc≤a}  . L'ensemble A  est un ensemble d'entiers naturels ; il est non vide, car il contient 0  . Il est fini : en effet soit d  un entier tel que d≥a+1  ; on a alors bd≥b(a+1)≥a+1>a  , donc d∉A  et ainsi A  ne contient que des entiers inférieurs ou égaux à a  .

 

L'ensemble A  possède donc un plus grand élément q  . Posons r=a-bq  . La première condition sur (q,r)  est alors évidemment vérifiée, c'est la seconde qui nécessite une vérification.

 

Comme q∈A  , par définition de A  , on a bq≤a  . Donc r=a-bq≥0  .

 

Comme q  est maximal parmi les éléments de A  , q+1∉A  . Donc b(q+1)>a  , donc r=a-bq<b  .

 

L'existence est démontrée dans ce cas.

 

∙  Second cas (preuve sans imagination) : si a<0  .

 

Posons a'=a(1-b)  . Comme a<0  et 1-b≤0  , on obtient a'≥0  .

 

On peut donc, en appliquant le premier cas, faire la division euclidienne de a'  par b  ; notons (q',r)  le couple ainsi obtenu : on a alors a'=bq'+r  , avec en outre 0≤r<b  . En réinjectant la définition de a'  , on écrit alors a-ba=bq'+r  , donc a=b(q'+a)+r  . Si on pose q=q'+a  , on constate qu'on a réussi la division euclidienne de a  par b  .

 

 

Unicité de (q,r)  : soit (q_1,r_1)  et (q_2,r_2)  des couples vérifiant les deux conditions exigées dans l'énoncé du théorème.

 

On déduit de a=bq_1+r_1=bq_2+r_2  que b(q_1-q_2)=r_1-r_2  . Ainsi, r_1-r_2  est un multiple de b  .

 

Des conditions 0≤r_1  et r_2<b  , on déduit que -b<r_1-r_2  .

 

Des conditions r_1<b  et 0≤r_2  , on déduit que r_1-r_2<b  .

 

Ainsi r_1-r_2  est un multiple de b  compris strictement entre -b  et b  . La seule possibilité est que r_1-r_2  soit nul. On en déduit r_1=r_2  , puis, en allant reprendre l'égalité b(q_1-q_2)=r_1-r_2  , que q_1=q_2  .

 

 

Sommaire

3. PGCD et PPCM

 

Les deux théorèmes qui se suivent sont agréablement parallèles ; il est donc amusant de constater que leurs preuves sont plus différentes qu'on ne pourrait s'y attendre. Il est possible de les déduire l'un de l'autre, mais il est instructif de les prouver très séparément. Vous verrez donc plusieurs preuves de l'un comme de l'autre.

 

Théorème Soit a≥1  et b≥1  deux entiers. Alors il existe un unique entier m≥1  tel que pour tout entier c≥1  ,

c  est un multiple de a  et de b  si et seulement si c  est un multiple de m  .

 

Théorème Soit a≥1  et b≥1  deux entiers. Alors il existe un unique entier d≥1  tel que pour tout entier c≥1  ,

c  divise a  et b  si et seulement si c  divise d  .

 

Ces théorèmes sont vendus avec deux compléments, le premier occasionnellement utile, le second totalement fondamental.

 

Complément 1 Pour tous a  et b  , md=ab  .

 

Complément 2 (Identité de Bézout)  Pour tous a  et b  , il existe deux entiers (relatifs) s  et t  tels que d=sa+tb  .

 

Et tant qu'on y est avant de passer aux démonstrations :

 

Définition  Le plus petit multiple commun de deux entiers a  et b  est l'entier m  apparaissant dans l'énoncé du théorème d'existence du PPCM.

 

Notation  Le plus petit multiple commun de a  et b  sera noté ppcm(a,b)  .

 

Définition  Le plus grand commun diviseur de deux entiers a  et b  est l'entier d  apparaissant dans l'énoncé du théorème d'existence duPGCD.

 

Notation  Le plus grand commun diviseur de a  et b  sera noté pgcd(a,b)  .

 

 

Première démonstration du théorème d'existence du PPCM

 

Cette démonstration est la plus élémentaire ; elle consiste à choisir pour m  le multiple commun de a  et b  le plus «petit» au sens de la relation habituelle ≤  , puis à vérifier qu'il marche. La preuve est en deux parties : d'abord l'existence de m  (partie significative) puis son unicité (partie très facile).

 

 

Existence de m 

 

Introduisons l'ensemble A  formé des entiers strictement positifs simultanément multiples de a  et de b  . L'ensemble A  n'est pas vide, puisqu'il contient l'entier ab  . Il admet donc un plus petit élément m  . On va vérifier que cet entier m  convient.

 

Pour faire cette vérification, soit un entier n≥1  ; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens.

 

∙  Preuve de l'implication directe : Supposons donc que n  est un multiple commun de a  et b  , et montrons que n  est un multiple de m  . Pour ce faire, effectuons la division euclidienne de n  par m  , soit n=mq+r  , avec 0≤r<m  . Comme n  et m  sont des multiples de a  , r=n-mq  aussi ; de même avec b  . Ainsi r  est un multiple commun de a  et b  . Si r  était un entier strictement positif, vu l'inégalité r<m  il contredirait la minimalité de m  . C'est donc que r=0  et donc que n  est un multiple de m  .

 

∙  Preuve de l'implication réciproque : Supposons ici que n  est un multiple de m  . Comme m  est lui-même multiple de a  , n  est à son tour multiple de a  ; de même avec b  . C'est réglé.

 

Unicité de m 

 

Soit m  et m'  vérifiant les hypothèses du théorème. Comme m  est un multiple de m  (eh oui !), c'est un multiple commun de a  et b  , donc un multiple de m'  . De même, m'  est un multiple de m  . Cela implique que m  et m'  sont forcément égaux au signe près. Comme ils sont tous deux strictement positifs, ils sont égaux. Fin de la démonstration.

 

Voici maintenant une première démonstration de l'existence (et l'unicité) du pgcd, qui l'obtient à partir du ppcm. Cette démonstration a le confort d'être dépourvue d'idée subtile et l'avantage de prouver le Complément 1. Elle a l'inconvénient de ne pas prouver le Complément 2 et de ne pas fournir une méthode rapide de calcul du pgcd.

 

Première démonstration du théorème d'existence du PGCD

 

 

Existence de d 

 

On note m  le ppcm de a  et b  et on pose d=ab/m  . Remarquons que ce nombre d  est bien un entier : en effet, ab  étant un multiple commun évident de a  et b  , c'est un multiple de leur ppcm. Reste à prouver qu'il convient.

 

Pour faire cette vérification, soit n≥1  un entier ; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens.

 

∙  Preuve de l'implication directe : supposons que n  est un diviseur commun de a  et b  . On peut donc introduire deux entiers k  et ℓ  tels que a=kn  et b=ℓn  . Pour travailler sur ce sur quoi nous avons des informations, à savoir les multiples de a  et b  , introduisons le nombre n'=ab/n  . Ce nombre n'  vaut aussi (a/n)b=kb  et (b/n)a=ℓa  . C'est donc un entier, et même un multiple commun de a  et b  . C'est donc un multiple de m  . Il existe donc un entier c  tel que n'=cm  , soit ab/n=cab/d  , donc d=cn  . On a bien prouvé que n  divise d  .

 

∙  Preuve de l'implication réciproque : puisque a=d(m/b)  où m/b  est un entier, d  divise a  ; symétriquement puisque b=d(m/a)  , d  divise b  . Supposons maintenant que n  divise d  . On voit alors aussitôt que n  divise a  et b  .

 

Unicité de d 

 

C'est exactement le même principe que pour le ppcm, on laisse donc cette partie de la démonstration en exercice (très) facile.

 

Preuve du Complément 1 : Il tombe immédiatement au vu de la formule qui donne d  à partir de m  . Fin de la démonstration.

 

Comme promis, voici maintenant une deuxième démonstration du théorème existenceDuPGCD, très différente dans son esprit, et qui permet pour guère plus cher de montrer simultanément le Complément 2.

 

 Deuxième démonstration du théorème d'existence du PGCD

 

La démonstration est une récurrence sur b  ; techniquement, on gagne sérieusement en confort si on autorise b  à être nul, ce que l'on n'a pas fait, volontairement, en énonçant le théorème dans l'espoir qu'il soit plus clair. On montrera donc légèrement mieux que l'énoncé de la page précédente, puisqu'on prouvera le résultat sous l'hypothèse « a≥1  et b≥0  ».

 

Avant de se lancer dans la récurrence proprement dite, on va donner un «résumé de la preuve» sous forme de programme informatique récursif.

 

Début du programme

* pgcd(a,0)=a  .

* Soit r  le reste de la division euclidienne de a  par b  .

Les diviseurs communs de a  et b  sont les diviseurs communs de b  et r  .

D'où : * pgcd(a,b)=pgcd(b,r)  .

Fin du programme

 

Ce résumé de démonstration convaincra peut-être les esprits les plus agiles, mais à notre niveau d'entraînement, il est plus prudent de faire ce qui est derrière les formulations récursives : une bonne vieille récurrence.

 

On va démontrer par «récurrence forte» sur b≥0  l'hypothèse (H_b)  suivante :  (H_b)  Pour tout entier a≥1  , il existe deux entiers (relatifs) s  et t  tels que, pour tout n≥1  , n  divise a  et b  si et seulement si n  divise sa+tb  .

 

Vérifions (H_0)  .

Soit a  un entier avec a≥1  ; tout entier n≥1  qui divise a  divise aussi b=0  puisque 0n=0  . Pour tout n≥1  , on a donc : n  divise a  et 0  si et seulement si n  divise a  . Prenons alors s=1  et t=0  . On a donc bien pour tout n≥1  : n  divise a  et 0  si et seulement si n  divise sa+t*0  .

 

 

Soit b  un entier fixé, avec b≥1  . Supposons la propriété (H_c)  vraie pour tout c  avec 0≤c<b  et montrons (H_b)  .

 

Soit a  un entier avec a≥1  . Notons a=bq+r  la division euclidienne de a  par b  (qu'on peut réaliser puisque b≥1  ).

 

Vérifions l'affirmation intermédiaire suivante : pour tout n≥1  , n  est un diviseur commun de a  et b  si et seulement si n  est un diviseur commun de b  et r  . C'est-à-dire, avec des mots peut-être plus lisibles : «les diviseurs communs de a  et b  sont les mêmes que ceux de b  et r  .»

 

Soit n  un diviseur commun de a  et b  , alors n  divise aussi r=a-bq  ; réciproquement soit n  un diviseur commun de b  et r  , alors n  divise aussi a=bq+r  .

 

L'affirmation intermédiaire est donc démontrée.

 

On peut alors appliquer l'hypothèse de récurrence (H_r)  (puisque précisément 0≤r<b  ) sur l'entier b≥1  .

 

On en déduit qu'il existe deux entiers relatifs s'  et t'  tels que pour tout n≥1  , n  divise b  et r  si et seulement si n  divise s'b+t'r  .

 

Remarquons enfin que s'b+t'r=s'b+t'(a-bq)=t'a...  , et qu'ainsi, si on pose s=t'  et t=s'-q  , on a bien prouvé que, pour tout n≥1  , n  divise a  et b  si et seulement si n  divise sa+tb  .

 

(H_b)  est donc démontrée.

 

On a donc bien prouvé (H_b)  pour tout b≥0  , donc a fortiori pour tout b≥1  , ce qui prouve le théorème d'existence du PGCD et son Complément 2.

 

En fait, il reste à prouver l'unicité de d  , pour laquelle on renvoie à la démonstration précédente (où on écrivait qu'on la laissait en exercice).

 

Fin de la démonstration.

 

À présent, donnons un petit exemple sur des vrais nombres concrets, pour nous soulager l'esprit après tant de lettres.

 

 Calcul du pgcd de 137  et 24 

 

On fait des divisions euclidiennes successives et on écrit dans la colonne de droite les conséquences de ces divisions.

 

(1)  137  =  5  *  24  +  17  ?  pgcd(137,24)=pgcd(24,17) 
(2)  24  =  1  *  17  +  7  ?  pgcd(24,17)=pgcd(17,7) 
(3)  17  =  2  *  7  +  3  ?  pgcd(17,7)=pgcd(7,3) 
(4)  7  =  2  *  3  +  1  ?  pgcd(7,3)=pgcd(3,1) 

 

 

Donc pgcd(137,24)=1  .

 

Ces calculs permettent ensuite sans mal de reconstituer une identité de Bézout.

 

 

La dernière division avec un reste non nul est (4) qui donne 1=7-2*3  .

 

On va repêcher une expression de 3  comme un reste dans la relation précédente, soit (3), ce qui donne 3=17-2*7  .

 

On reporte cette expression de 3  donc 1=7-2*(17-2*7)  .

 

On regroupe les termes en 17  et 7  donc 1=-2*17+5*7  .

 

On va repêcher une expression de 7  comme un reste dans la relation précédente, soit (2), ce qui donne 7=24-1*17  .

 

On reporte cette expression de 7  donc 1=-2*17+5*(24-1*17)  .

 

On regroupe les termes en 24  et 17  donc 1=5*24-7*17  .

 

On va repêcher une expression de 17  comme un reste dans la relation précédente, soit (1), ce qui donne 17=137-5*24  .

 

On reporte cette expression de 17  donc 1=5*24-7*(137-5*24)  .

 

On regroupe les termes en 137  et 24  donc 1=-7*137+40*24 

 

Et voilà !

 

Voici un autre exemple.

 

Calcul du pgcd de 141  et 24 

 

Voici les divisions euclidiennes successives et leurs conséquences en termes de pgcd.

 

(1)  141  =  5  *  24  +  21  ?  pgcd(141,24)=pgcd(24,21) 
(2)  24  =  1  *  21  +  3  ?  pgcd(24,21)=pgcd(21,3) 
(3)  21  =  7  *  3  +  0  ?  pgcd(21,3)=pgcd(3,0)=3 

 

 

Donc pgcd(141,24)=3  et on vérifiera que ces calculs permettent de reconstituer l'identité de Bézout -141+6*24=3 

 

Donnons une dernière définition avant de quitter les pgcd.

 

Définition  On dit que deux entiers a≥1  et b≥1  sont premiers entre eux lorsque leur seul diviseur commun positif est 1  .

 

On veillera à ne pas confondre cette notion avec celle de nombre premier. (Par exemple, les calculs ci-dessus montrent que 137  et 24  sont premiers entre eux mais 24  n'est pas premier.)

 

 

Sommaire

4. Lemme de Gauss et décomposition en facteurs premiers

 

Le lemme de Gauss permet de démontrer l'unicité de la décomposition en facteurs premiers. Ce dernier résultat semble plus facile d'usage pour un utilisateur peu expérimenté, donc on énonce le lemme de Gauss sans commentaire, ou plus exactement sans autre commentaire que ce commentaire négatif.

 

Lemme  Soit a  , b  et c  trois entiers strictement positifs. Si a  divise le produit bc  et si a  est premier avec c  , alors a  divise b  .

 

Puisque a  est premier avec c  , le pgcd de a  et c  est 1  , donc il existe des entiers relatifs s  et t  tels que sa+tc=1  . Multiplions cette identité par b  : on obtient b=asb+tbc  . Mais dans cette écriture, asb  est évidemment multiple de a  tandis que tbc  l'est parce que bc  est multiple de a  . On en déduit que b  , somme des deux multiples de a  que sont asb  et tbc  , est lui-même un multiple de a  .

 

Théorème (énoncé approximatif)  Tout entier n≥2  peut être écrit de façon unique comme produit de facteurs premiers.

 

L'énoncé est approximatif car il n'est pas si clair de savoir ce que signifie «unique» : on peut écrire 6=2*3=3*2  mais il faut évidemment considérer que c'est la même chose. Pour pouvoir comprendre voire utiliser le théorème, cet énoncé suffira bien ; mais pour le démontrer, il faut être plus précis.

 

Théorème (énoncé précis) Tout entier n≥2  peut être écrit comme produit de facteurs premiers. De plus, si on dispose de deux écritures

n=p_1^α_1p_2^α_2...p_k^α... 

dans lesquelles k≥1  , i≥1  , les entiers p_1<p_2<...<p_k  et q_1<q_2<...<q_i  sont tous premiers et rangés en ordre croissant, les exposants α_1  , α_2  , ..., α_k  et β_1  , β_2  , ..., β_i  sont tous des entiers strictement positifs, alors ces deux écritures sont les mêmes au sens précis suivant : k=i  et pour tout j  avec 1≤j≤k=i  , p_j=q_j  et α_j=β_j  .

 

À énoncé indigeste, démonstration indigeste.

 

L'existence provient d'une récurrence élémentaire. Pour tout entier n≥2  , considérons l'hypothèse de récurrence (forte) suivante :  (E_n)  Tout entier 2≤k≤n  peut s'écrire comme un produit de facteurs premiers comme dans l'énoncé du théorème.

 

Alors (E_2)  est évidente car 2  est premier.

 

Soit n≥2  un entier fixé, supposons (E_n)  vraie et montrons (E_n+1)  .

 

Si n+1  est premier, (E_n+1)  est évidente.

 

Si n+1  n'est pas premier, il existe un entier 2≤k≤n  qui divise n+1  . Notons ℓ  l'entier ℓ=(n+1)/k  . Alors 2≤ℓ≤n  donc on peut appliquer l'hypothèse (E_n)  aux deux entiers k  et ℓ  . Il existe donc des entiers premiers p_i  et q_j  et des exposants a_i  et b_j  strictement positifs tels que k=p_1^a_1p_2^a_2...p_u^a...  avec p_1<p_2<...<p_u  et q_1<q_2<...<q_v  . Par conséquent, n+1=k*ℓ=p_1^a_1p_2^a_2.....  L'ensemble {p_1,p_2,...,p_u}∪{q_1,q...  comporte w≤u+v  éléments. Notons et ordonnons ces éléments comme r_1<r_2<...<r_w  . En regroupant les entiers qui apparaissent dans les deux factorisations, on obtient n+1=r_1^c_1r_2^c_2...r_w...  où les exposants c_k  sont définis comme suit :

 

c_k=a_i  si r_k=p_i  et r_k≠q_j  pour tout j  ,

c_k=b_j  si r_k=q_j  et r_k≠p_i  pour tout i  ,

 

et enfin c_k=a_i+b_j  si r_k=p_i=q_j  .

 

Donc (E_n+1)  est vraie.

 

Ceci conclut la preuve de l'existence.

 

Passons à l'unicité. On va donc montrer par récurrence (forte) sur n  le résultat d'unicité (H_n)  écrit dans l'énoncé du théorème.

Démonstration de (H_2)  , et en fait même de (H_p)  pour tout nombre premier p 

 

Supposons n=p  premier écrit sous forme de produit p=p_1^α_1p_2^α_2...p_k^α...  . Chaque p_i  est un diviseur positif de p  non égal à 1  , donc chaque p_i  est égal à p  . Ceci entraîne aussitôt que k=1  et que α_1=1  (sans cela le produit serait supérieur ou égal à p²  donc distinct de p  ). L'écriture p=p  est donc la seule possible pour p  , ce qui démontre (H_p)  quand p  est premier.

 

Soit maintenant n  un entier fixé, non premier, avec n>2  , et supposons l'hypothèse d'unicité (H_m)  prouvée pour tout entier m  avec 2≤m<n  .

 

 Première étape Montrons que p_k=q_i  (toujours dans les notations de l'énoncé du théorème).

 

Supposons tout d'abord que p_k>q_i  et montrons que l'on aboutit à une absurdité.

 

Puisque les q_j  sont supposés rangés dans l'ordre croissant, p_k  est alors forcément distinct de tous les q_j  ; p_k  et chaque q_j  étant premiers, on en conclut que leur seul diviseur commun positif est 1  : p_k  et q_j  sont donc premiers entre eux.

Fixons un j  entre 1  et i  et montrons par récurrence sur b≥0  l'énoncé fort intuitif suivant : (H'_b)   : p_k  est premier avec q_j^b  .

 

(H'_0)  est évident puisque q_j^0=1  .

 

Soit b≥0  un entier fixé, supposons (H'_b)  vrai et montrons (H'_b+1)  .

 

Si (H'_b+1)  était faux, le pgcd de p_k  et q_j^b+1  ne serait pas 1  ; comme c'est un diviseur positif de p_k  , ce serait p_k  qui diviserait donc q_j^b+1  . On peut alors appliquer le lemme de Gauss : comme p_k  divise q_j^b+1=q_j^bq_j  et que p_k  est premier avec q_j  , p_k  divise q_j^b  . Mais ceci contredit l'hypothèse (H'_b)  . L'hypothèse (H'_b+1)  est donc vraie.

 

On a donc bien montré que pour tout b≥0  , p_k  est premier avec q_j^b  . En particulier, p_k  est premier avec q_j^β_j  . Comme on a prouvé cette affirmation pour un j  quelconque, on a prouvé que pour tout j  entre 1  et i  , p_k  est premier avec q_j^β_j  . Ce qu'on a fait avec les puissances de chaque q_j  , on va maintenant le recommencer avec le produit de ces puissances. Précisément, on va montrer par récurrence sur l'entier j  que pour tout j  avec 1≤j≤l  , on a l'énoncé (H''_j)  : p_k  est premier avec q_1^β_1q_2^β_2...q_j^β_j  .

 

Les lecteurs encore éveillés (s'il en reste) comprendront que la preuve est à peu près la même que celle des (H'_b)  , pour les autres, la voilà :

 

Pour j=1  , on doit prouver que p_k  est premier avec q_1^β_1  . C'est déjà fait.

 

Fixons un entier j  avec 1≤j<i  et supposons l'hypothèse (H''_j)  vraie.

 

Si (H''_j+1)  était fausse, le pgcd de p_k  et q_1^β_1q_2^β_2...q_j^β_j...  ne serait pas 1  ; comme c'est un diviseur positif de p_k  , ce serait p_k  qui diviserait donc q_1^β_1q_2^β_2...q_j^β_j...  . On peut alors appliquer le lemme de Gauss : comme p_k  divise le nombre q_1^β_1q_2^β_2...q_j^β_j...  et comme p_k  est premier avec q_j+1^β_j+1  , p_k  divise q_1^β_1q_2^β_2...q_j^β_j  . Mais ceci contredit l'hypothèse (H''_j)  . L'hypothèse (H''_j+1)  est donc vraie.

 

On a donc montré (H''_j)  pour tout j  entre 1  et i  ; en particulier on a montré (H''_i)  , à savoir que p_k  est premier avec q_1^β_1q_2^β_2...q_i^β_i...  . Mais pourtant p_k  figure dans l'autre décomposition en facteurs premiers de n  (ce n'est pas une illusion d'optique, puisqu'on a pris soin de supposer α_k≥1  ), donc p_k  divise n  . D'où contradiction. Ouf !

 

On ne peut donc avoir p_k>q_i  . En échangeant les rôles des coefficients p  et q  , on voit qu'on ne peut pas non plus avoir q_i>p_k  . On en déduit donc que q_i=p_k  .

 

Fin de la première étape

 

Deuxième étape On va profiter de ce tout petit morceau d'égalité pour arriver à utiliser l'hypothèse de récurrence et faire tomber toutes les autres égalités requises en cascade.

 

Notons N=n/p_k=n/q_i  , on a ainsi : N=p_1^α_1p_2^α_2...p_k^α...  De plus N  est strictement inférieur à n  , et N  est strictement plus grand que 1  car on a fort opportunément supposé n  non premier. On va donc appliquer l'hypothèse de récurrence (H_N)  à ces deux écritures de N  en facteurs premiers. Si on n'est pas méticuleux, on oubliera de s'assurer que tous les exposants sont strictements positifs, et on aura fini tout de suite ; ce sera faux, mais de peu. Hélas, un enseignant scrupuleux ne peut se le permettre et doit donc veiller à ce petit détail, qui nous force à distinguer deux sous-cas.

 

Premier sous-cas : α_k=1  . Dans ce cas, la première écriture de m  se lit en réalité, après effacement du p_k^0  qui l'encombre : N=p_1^α_1p_2^α_2...p_k-1...  Ainsi N  possède une décomposition en facteurs premiers dans laquelle p_k  ne figure pas. Comme sa décomposition est unique, p_k  ne peut non plus figurer dans l'autre décomposition, et comme q_i=p_k  , la seule possibilité est que l'exposant β_i-1  soit nul ; ainsi β_i=α_k  =1, et les deux représentations N=p_1^α_1p_2^α_2...p_k-1...  sont deux décompositions de N  en facteurs premiers. On en déduit que k-1=i-1  , donc k=i  , puis l'égalité de tous les facteurs premiers et exposants encore en attente d'élucidation.

 

Second sous-cas : α_k>1  . C'est la même chanson. On remarque tout d'abord qu'on a aussi β_i>1  (sans cela, en échangeant les rôles des coefficients p  et q  et en utilisant le premier cas, on montrerait que α_k=1  ) ; donc les deux décompositions N=p_1^α_1p_2^α_2...p_k^α...  vérifient bien les hypothèses du théorème. Elles sont égales, donc k=i  et chaque coefficient p  est égal au coefficient q  correspondant, avec le même exposant.

 

Fin de la deuxième étape

 

(H_n)  est donc prouvée.

 

La récurrence est donc terminée, et avec elle la démonstration.

 

La décomposition en facteurs premiers permet d'énumérer facilement les diviseurs d'un entier.

 

Proposition  Soit n  un entier et n=p_1^α_1p_2^α_2...p_k^α...  sa décomposition en facteurs premiers. L'ensemble des diviseurs positifs de n  est : D={N=p_1^β_1p_2^β_2...p_... 

 

Par exemple l'ensemble des diviseurs positifs de 60=2²*3^1*5^1  est :

 

D={2^0*3^0*5^0,2^1*3^0*5...  {2^1*3^0*5^1,2²*3^1*5^0,... 

 

soit, D={1,2,3,4,5,6,10,12,15,...   Soit n=p_1^α_1p_2^α_2...p_k^α...  Si pour tout i=1,...,k  , 0≤β_i≤α_i  , alors : n=N*(p_1^α_1-β_1p_2^α_2-...  Donc tout élément de l'ensemble D  est diviseur de n  .

 

Réciproquement, soit N  un diviseur de n  . Tout facteur premier de N  divise n  , donc c'est l'un des p_i  . Si p_i^β_i  divise N  , alors p_i^β_i  divise aussi n  , donc β_i≤α_i  . Ceci montre que tout diviseur de n  est élément de D  .

 

Quand on connaît la décomposition en facteurs premiers de deux nombres, il est facile de calculer leur pgcd et leur ppcm.

 

Proposition  Soient m  et n  deux entiers. Quitte à admettre des exposants nuls, nous pouvons considérer que leurs facteurs premiers sont les mêmes. Ecrivons donc : n=p_1^α_1p_2^α_2...p_k^α...  où pour i=1,...,k  , α_i≥0  et β_i≥0  .

 

Alors : pgcd(m,n)=p_1^δ_1p_2^δ_2...  où pour tout i=1,...,k  , δ_i= min {α_i,β_i} et γ_... 

 

Considérons par exemple : n=172872=2³*3²*7^4 et m=...  Quitte à admettre des puissances nulles, nous pouvons écrire la décomposition sur les mêmes facteurs. n=2³*3²*5^0*7^4*11^0*13^...  Donc : pgcd(m,n)=2^0*3^1*5^0*7²...  et ppcm(m,n)=2³*3²*5²*7^4*1... 

 

Posons : d=p_1^δ_1p_2^δ_2...p_k^δ...  On vérifie facilement que d  est bien un diviseur commun de m  et de n  . Réciproquement, soit d'  un diviseur commun de m  et n  . Tout facteur premier p  de d  est aussi un facteur premier de m  et de n  . Si p_i^δ  divise n  et m  , alors δ≤α_i  et δ≤β_i  , donc δ≤δ_i= min {α_i,β_i}  Ceci entraîne que d'  est diviseur de d  . Donc d  est bien le pgcd de m  et n  .

 

L'expression du ppcm se déduit de celle du pgcd par la formule : pgcd(m,n)*ppcm(m,n)=m*n 

 

 

Sommaire

5. Sous-groupes de ℤ 

 

Notation  Soit b  un entier. On note bℤ  l'ensemble des multiples de b  .

 

Par exemple 0ℤ={0}  et 2ℤ  est l'ensemble des entiers relatifs pairs.

 

L'objet de la section est un théorème d'énoncé très simple, et assez pratique.

 

Théorème  Les sous-groupes de ℤ  sont exactement les ensembles bℤ  avec b≥0  .

 

Il y a deux choses à démontrer : que les ensembles bℤ  sont des sous-groupes, et que tout sous-groupe est un ensemble bℤ  .

 

Commençons donc par vérifier (c'est très facile) que pour b≥0  fixé, bℤ  est un sous-groupe de ℤ  .

 

∙  0  est multiple de b  , donc bℤ  n'est pas vide.

∙  Soit x  et y  deux éléments de bℤ  , c'est-à-dire deux multiples de b  . Il est clair que x-y  est aussi un multiple de b  , donc appartient à bℤ  .

 

C'est fait. Pour les amateurs d'abstraction, on pouvait remarquer que bℤ=<b>  (le sous-groupe engendré par b  ), ce qui est camouflé par la notation additive de l'opération.

 

Soit maintenant H  un sous-groupe de ℤ  , montrons qu'il existe un entier b≥0  tel que H=bℤ  . On distinguera deux cas.

 

Premier cas : Si H={0}  , on remarque que H=0ℤ  et on a fini.

 

Second cas : Si H≠{0}  , H  possède au moins un élément non nul x  , donc au moins un élément strictement positif y  (on prendra y=x  ou y=-x  selon le signe de x  ). Si on introduit l'ensemble B=H∩ℕ^*  , B  est donc un ensemble d'entiers positifs non vide. Il possède un plus petit élément b  . On va montrer que b  convient.

 

Il semble raisonnablement clair que bℤ⊂H  . (Hum, est-ce si clair ou est-ce un petit moment de paresse du rédacteur ? Le lecteur est invité à se forger par lui-même une opinion sur cette épineuse question.)

 

Réciproquement soit a  un élément de H  . Si on fait la division euclidienne de a  par b  , soit a=qb+r  , on en déduit que r=a-bq  est aussi un élément de H  . Comme r<b  , r∉B  , et comme r∈H∩ℕ  la seule possibilité est que r=0  . On en déduit donc que a=bq∈bℤ  . Ceci prouve l'inclusion H⊂bℤ  .

 

On a donc montré que H=bℤ  .

 

On a donc montré, dans les deux cas, que H  est de la forme bℤ  .

 

En application de ce théorème, donnons de nouvelles et élégantes démonstrations des théorèmes existenceDuPPCM et existenceDuPGCD ; l'outil à la base reste la division euclidienne, mais il aura été utilisé une seule fois, dans la preuve du théorème qui précède, et on ne fait plus que d'assez simples manipulations ensemblistes.

 

Deuxième démonstration du théorème d'existence du PPCM :

 

Introduisons les sous-groupes de ℤ  que sont H=aℤ  et K=bℤ  . Pour tout n≥1  , n  est un multiple commun de a  et b  si et seulement si n  est dans H∩K  . Or H∩K  , comme intersection de deux sous-groupes de ℤ  , est lui-même un sous-groupe de ℤ  (bon, d'accord, on n'a pas mentionné ce résultat dans le cours sur les sous-groupes, mais on aurait dû, et de toutes façons c'est très facile). Il existe donc un entier m≥0  tel que H∩K=mℤ  (et il est clair que m>0  , car H∩K  contient d'autres entiers que 0  , par exemple ab  ). On a alors pour tout n≥1  les équivalences : n  est un multiple commun de a  et b  si et seulement si n  appartient à H∩K  si et seulement si n  appartient à mℤ  si et seulement si n  est un multiple de m  .

 

L'unicité reste à prouver comme dans la preuve initiale.

 

Fin de la démonstration.

 

Troisième démonstration du théorème d'existence du PGCD :

 

Introduisons l'ensemble L⊂ℤ  défini par L={sa+tb,s∈ℤ,t∈ℤ}  .

 

On vérifie sans mal que L  est un sous-groupe de ℤ  . C'est si facile, qu'on va le laisser au lecteur.

 

Il existe donc un entier d≥0  tel que L=dℤ  . De plus L  n'est manifestement pas réduit à {0}  (il contient par exemple a=1a+0b  , et même aussi b=0a+1b  ), donc d>0  . Montrons que d  convient.

 

On a remarqué que a  et b  sont dans L=dℤ  . En d'autres termes, ils sont tous deux multiples de d  , ou, pour dire cela encore autrement, d  est un diviseur commun de a  et b  . Il est donc clair que tout diviseur de d  est à son tour un diviseur commun de a  et b  .

 

Par ailleurs, d  est dans L  , donc peut être mis sous forme sa+tb  pour des entiers relatifs s  et t  . Si on part d'un diviseur commun n≥1  de a  et b  , sa  et tb  sont à leur tour des multiples de n  , donc aussi d  , et n  est donc bien un diviseur de d  .

 

Là aussi, on renvoie à la preuve initiale pour l'unicité.

 

Fin de la démonstration.

 

 

Sommaire

6. Congruences

 

Juste quelques notations pratiques. La section se réduit à quasiment rien.

 

Définition Soit a  et b  des entiers relatifs et n≥1  un entier strictement positif. On dit que a  est congru à b  modulo n  lorsque b-a  est un multiple de n  .

 

Il est tellement évident de vérifier que, pour n  fixé, la relation «est congru à» est une relation d'équivalence sur ℤ  que cet énoncé n'aura pas même l'honneur d'être qualifié de proposition.

 

Notation  Lorsque a  est congru à b  modulo n  , on note : a≡b|(n)| 

 

Exemple On repère les jours de l'année par leur numéro de 1  à 365  ou 366  selon les cas. Alors les numéros de tous les lundis sont congrus les uns aux autres modulo 7  .

 

L'intérêt des congruences est d'être compatibles avec l'addition et la multiplication, au sens suivant :

 

Proposition  Soit n≥1  fixé et soit a  , b  et c  trois entiers relatifs. Alors : si  a≡b|(n)|  alors  a+c≡b+c|(n)|etac≡bc|(n)| 

 

C'est vraiment trop facile.

 

Exemple 911 Quel est le reste de la division par 9  de 12345  ? On commence par écrire 12345=10^4+2.10³+3.10²+4...  Comme 10≡1|(9)|  , on en déduit 12345≡1^4+2.1³+3.1²+4.1+...  et 12345≡1.10+5≡1.1+5=1+5=6  donc la réponse est 6  . Et par 11  ? Ici, on utilise le fait que 10≡-1|(11)|  , donc 12345≡(-1)^4+2.(-1)³+3.(...  et la réponse est 3  .

 

 Exercice : Formaliser les règles de calcul des congruences modulo 9  et modulo 11  utilisées dans l'exemple 911.

 

Exercice : Montrer qu'une règle de calcul possible pour calculer des congruences modulo 7  est la suivante. On décompose l'écriture de n  en base 10  en groupes de 3  chiffres consécutifs en commençant par le chiffre des unités. Si un bloc vaut B=abc  , on note s(B)=2a+3b+c  . Puis on effectue la somme alternée s(n)  des s(B)  en commençant par le bloc du chiffre des unités. Alors n  et s(n)  sont congrus modulo 7  .

 

Par exemple, si n=12345678  , les blocs sont B_3=012  , B_2=345  et B_1=678  . On calcule s(B_3)=2*0+3*1+1*2=5  , s(B_2)=2*3+3*4+1*5=23  , s(B_1)=2*6+3*7+1*8=41  , puis s(n)=s(B_1)-s(B_2)+s(B_3...  donc n≡23|(7)|  et enfin n≡2|(7)|  .

 

 

Sommaire

7. ℤ/nℤ 

 

En apparence, cette section est consacrée à un formalisme assez gratuit consistant à remplacer l'écriture : a≡b|(n)|  par l'écriture équivalente : (cℓ)(a)=(cℓ)(b)  dans  ℤ/nℤ  où cℓ  est l'abréviation de «classe». Maigre progrès en apparence ! Toutefois, comme des exemples judicieusement choisis le montreront en fin de section, on a fait plus qu'un simple changement de notations : on a construit un pont entre ce chapitre et le chapitre précédent, pont par lequel on pourra rapatrier des résultats connus sur les groupes pour effectivement affiner notre connaissance des entiers.

 

Définition  Soit n≥1  un entier fixé. On appelle ℤ/nℤ  l'ensemble-quotient de ℤ  par la relation d'équivalence «est congru à» (modulo n  ).

 

Exemple  Pour n=2  , soit a  un entier. Si a  est pair, la classe d'équivalence (cℓ)(a)  pour la relation de congruence modulo 2  est l'ensemble P  de tous les nombres pairs  ; si a  est impair, (cℓ)(a)  est l'ensemble I  de tous les nombres impairs, et finalement ℤ/2ℤ={I,P} 

 

Proposition  Pour tout n≥1  , ℤ/nℤ  possède exactement n  éléments.

 

Montrons tout d'abord que ℤ/nℤ={(cℓ)(0),(cℓ)(1),.....  , d'où on déduit aussitôt que ℤ/nℤ  possède au plus n  éléments.

 

Soit x  un élément de ℤ/nℤ  ; il existe alors a∈ℤ  tel que x=(cℓ)(a)  . Effectuons la division euclidienne de a  par n  , soit a=nq+r  ; on voit alors que a≡r|(n)|  ou encore que x=(cℓ)(a)=(cℓ)(r)  . Mais 0≤r<n  , donc on a bien prouvé que x  était dans l'ensemble proposé.

 

Montrons maintenant que ces n  éléments sont deux à deux distincts, prouvant ainsi que ℤ/nℤ  possède au moins n  éléments.

 

Soit a  et b  deux entiers distincts avec 0≤a<n  et 0≤b<n  . Des inégalités 0≤a  et b<n  on déduit que -n<b-a  ; des inégalités a<n  et 0≤b  on déduit que b-a<n  et de l'hypothèse a≠b  on déduit que b-a≠0  . On en conclut que anon≡b|(n)|  , c'est-à-dire que (cℓ)(a)  et (cℓ)(b)  sont deux éléments distincts de ℤ/nℤ  .

 

On a donc bien prouvé que ℤ/nℤ  possède exactement n  éléments.

 

 

Définition  Soit (cℓ)(a)  et (cℓ)(b)  deux éléments de ℤ/nℤ  . On définit la somme de (cℓ)(a)  et (cℓ)(b)  par (cℓ)(a)+(cℓ)(b)=(cℓ)(a+b...  et leur produit par (cℓ)(a)*(cℓ)(b)=(cℓ)(ab)  .

 

Prudence ! Cette définition est aussi innocente en apparence que celles qui l'ont précédée. Et pourtant, elle pourrait n'avoir rigoureusement aucun sens.

 

En effet, la définition de la somme de deux éléments x  et y  de ℤ/nℤ  nécessite implicitement de les mettre préalablement sous forme x=(cℓ)(a)  et y=(cℓ)(b)  . Mais il y a plusieurs façons de les mettre sous cette forme ! Il faut donc vérifier que la définition ne dépend pas du choix fait dans cette phase préparatoire. Pour montrer à quel point c'est indispensable, donnons une

 

Fausse définition (buggée) Soit (cℓ)(a)  et (cℓ)(b)  deux éléments de ℤ/nℤ  . On dira que (cℓ)(a)≤(cℓ)(b)  lorsque a≤b  .

 

Il est facile de comprendre pourquoi cette «définition» est bonne pour la corbeille à papier : dans ℤ/3ℤ  , prenons x=(cℓ)(0)  et y=(cℓ)(2)  . En les écrivant ainsi, la «définition»  nous donne : x≤y  . Mais on peut aussi écrire x=(cℓ)(3)  et comme précédemment y=(cℓ)(2)  . En s'y prenant ainsi, y≤x  . Cette «définition» n'a donc en fait aucun sens.

 

Sermon (ou : Prudence II, le retour) Malgré ses dehors anecdotiques, il est indispensable de comprendre cette remarque. La fausse définition et la bonne sont semblables formellement, alors que l'une est absurde et l'autre non. Fin du sermon.

 

Procédons donc à cette indispensable vérification. Soit x=(cℓ)(a)=(cℓ)(α)  et y=(cℓ)(b)=(cℓ)(β)  deux éléments de ℤ/nℤ  . La cohérence de la définition exige de prouver que (cℓ)(a+b)=(cℓ)(α+β)  . La vérification est alors évidente (α+β)-(a+b)=(α-a)+(β-b)  étant un multiple de n  parce que α-a  et β-b  le sont tous les deux. De même (cℓ)(ab)=(cℓ)(αβ)  car αβ-ab=αβ-αb+αb-ab=α(β-b)...  .

 

Ainsi au point où nous en sommes, ℤ/nℤ  est muni d'une addition et d'une multiplication. Traçons un exemple de tables, pour voir quelle tête elles ont. Ce sera l'exemple de ℤ/5ℤ  .

 

On note dans cette table et dans les suivantes å=(cℓ)(a) 

 

image image1 

 Après la présentation de l'objet, un peu de théorie à son sujet.

 

Proposition  Pour tout n≥1  , ℤ/nℤ  est un anneau commutatif.

 

Elle est d'un ennui mortel, et ne présente aucune difficulté. Pour en faire un tout petit bout, montrons que l'addition est associative : soit x  , y  et z  trois éléments de ℤ/nℤ  . On peut les écrire sous forme x=(cℓ)(a)  , y=(cℓ)(b)  , z=(cℓ)(c)  . Vu la définition de l'addition dans ℤ/nℤ  , on a alors

(x+y)+z=((cℓ)(a)+(cℓ)(b)... 

=(cℓ)(a+(b+c))=(cℓ)(a)+(... 

 

Et toutes les vérifications seraient de ce genre. Nous décidons donc de les laisser au lecteur.

 

Plus intéressant et légèrement plus subtil est le résultat suivant.

 

Théorème  Pour tout n≥1  , ℤ/nℤ  est un corps commutatif si et seulement si n  est un nombre premier.

 

Montrons tour à tour les deux sens de l'équivalence.

 

Preuve de l'implication directe. On va montrer cette implication par contraposition. Supposons donc que n  n'est pas premier, et montrons que ℤ/nℤ  n'est pas un corps commutatif (on verra même en passant que ce n'est même pas un anneau intègre).

 

Traitons à part le cas, «stupide», où n  vaudrait 1  . Dans ce cas, ℤ/1ℤ  ne possède qu'un élément, donc n'est pas un corps commutatif.

 

Examinons le cas, significatif, où n  n'est pas premier, mais n'est pas non plus égal à 1  . Dans ce cas, on peut écrire n=ab  , où 1<a<n  et 1<b<n  . Dans l'anneau ℤ/nℤ  , on obtient alors la relation (cℓ)(n)=(cℓ)(a)(cℓ)(b)  , soit (cℓ)(a)(cℓ)(b)=(cℓ)(0)  . Pourtant, au vu des inégalités vérifiées par a  et b  , ni (cℓ)(a)  ni (cℓ)(b)  n'est nul. Donc ℤ/nℤ  n'est pas intègre, et a fortiori n'est pas un corps commutatif.

 

On a bien prouvé dans les deux cas que ℤ/nℤ  n'est pas un corps commutatif.

 

Preuve de l'implication inverse. Supposons n  premier, et montrons que ℤ/nℤ  est alors un corps commutatif.

 

Nous savons déjà que la multiplication sur ℤ/nℤ  est commutative.

 

Comme ℤ/nℤ  possède n  éléments, il en possède au moins deux.

 

Soit x  un élément non nul de ℤ/nℤ  . On peut écrire x=(cℓ)(a)  pour un entier a  dans l'ensemble {1,...,n-1}  . Puisque n  est premier, a  ne possède d'autre diviseur positif commun avec n  que 1  et donc a  et n  sont premiers entre eux. Il existe donc deux entiers relatifs s  et t  tels que 1=sa+tn  . En passant aux classes d'équivalence, on obtient : (cℓ)(1)=(cℓ)(s)(cℓ)(a)+(...  , soit (cℓ)(1)=(cℓ)(s)(cℓ)(a)+(...  .

 

On a donc trouvé un inverse de x  , à savoir (cℓ)(s)  .

 

Finalement, ℤ/nℤ  est donc bien un corps commutatif.

 

Remarque On retiendra de cette démonstration la technique pratique de calcul de l'inverse d'un élément non nul de ℤ/nℤ  : écrire une identité de Bézout entre un représentant de cet élément et n  , et redescendre aux classes d'équivalence.

 

Et voilà, on sait tout. Reste à donner quelques illustrations afin de convaincre de l'utilité de l'introduction de cette notion abstraite.

 

Exemple  Résoudre dans ℤ  l'équation suivante, d'inconnue x  : 24x+5≡0|(137)|  On peut traiter cet exemple avec ou sans usage de ℤ/137ℤ  . Faisons les deux successivement ; on constatera que les énoncés simples sur les propriétés algébriques de ℤ/137ℤ  remplacent avantageusement les techniques, il est vrai elles aussi simples, d'arithmétique classique.

 

Première résolution (sans ℤ/137ℤ  )

 

Remarquons que 137  est premier, et donc que 137  et 24  sont premiers entre eux ; cherchons à écrire une identité de Bézout entre 137 et 24 ; en utilisant l'algorithme décrit plus haut, on découvre que : 1=40*24-7*137  d'où on déduit (par une simple multiplication par 5  ) que : 5=200*24-35*137  Reportons cette identité dans l'équation, qui devient donc : 24x+200*24-35*137≡0|(137...  À son tour, cette équation est équivalente à la condition suivante : 24(x+200)≡0|(137)|  qui signifie que 137 divise 24(x+200)  , donc, en utilisant le lemme de Gauss puisque 137 et 24 sont premiers entre eux, que 137 divise x+200  . Finalement, x  est solution si et seulement si x+200≡0|(137)|  , c'est-à-dire x≡-200|(137)|  , c'est-à-dire x≡74|(137)|  .

 

Deuxième résolution (avec ℤ/137ℤ  )

 

Remarquons que 137  est premier, et donc que ℤ/137ℤ  est un corps commutatif. Faisons tous les calculs dans ce corps.

 

L'équation proposée se réécrit (cℓ)(24)(cℓ)(x)+(cℓ)(5)=...  , soit (cℓ)(24)(cℓ)(x)=-(cℓ)(5)  , soit (cℓ)(x)=-(cℓ)(5)((cℓ)(24...  .

 

Calculons donc ((cℓ)(24))^-1  ; pour cela nous connaissons la bonne méthode : écrire une identité de Bézout entre 24  et 137  , à savoir 1=40*24-7*137  puis redescendre aux classes d'équivalence dans ℤ/137ℤ  : (cℓ)(1)=(cℓ)(40).(cℓ)(24...  soit : ((cℓ)(24))^-1=(cℓ)(40) 

 

On en conclut que l'équation proposée équivaut à : (cℓ)(x)=-(cℓ)(5)((cℓ)(24... 

 

Exemple  Résoudre dans ℤ  l'équation suivante, d'inconnue x  : x^4≡81|(73)|  Là aussi, écrire deux solutions serait possible, mais celle utilisant ℤ/73ℤ  est tellement plus agréable à écrire que l'on s'en contentera.

 

Tout d'abord, l'équation s'écrit x^4-81≡0|(73)|  et, dans ℤ  , x^4-81=(x²-9)(x²+9)=(x-3...  Dans ℤ/73ℤ  , l'équation s'écrit donc ((cℓ)(x)-(cℓ)(3))((cℓ)(x...  Mais (cℓ)(9)=-(cℓ)(64)  donc (cℓ)x²+(cℓ)(9)=(cℓ)x²-(c...  Finalement, en utilisant (cℓ)(8)=-(cℓ)(65)  et (cℓ)(3)=-(cℓ)(70)  , on voit que l'équation de départ s'écrit

((cℓ)(x)-(cℓ)(3))((cℓ)(x... 

soit (cℓ)(x)=(cℓ)(3)  ou (cℓ)(x)=(cℓ)(8)  ou (cℓ)(x)=(cℓ)(65)  ou (cℓ)(x)=(cℓ)(70)  , car ℤ/73ℤ  est un corps commutatif, donc intègre.

 

Les solutions de l'équation proposée sont donc x≡3|(73)|oux≡8|(73)|oux≡... 

 

Exemple  Résoudre dans ℤ  l'équation suivante, d'inconnue x  : x^17≡3|(19)|  Là encore, on ne saurait trop recommander le passage dans ℤ/19ℤ  . L'équation s'écrit dès lors : (cℓ)(x)^17=(cℓ)(3)  . Notons a  l'inconnue auxiliaire a=(cℓ)(x)  et remarquons que (cℓ)(0)^17≠(cℓ)(3)  . Il suffit donc de résoudre a^17=(cℓ)(3)  dans ℤ/19ℤ∩{(cℓ)(0)}  .

 

Mais, si a≠(cℓ)(0)  , alors a^17=(cℓ)(3)  si et seulement si a^18=(cℓ)(3)a  . Maintenant, pour tout a  dans le groupe multiplicatif ℤ/19ℤ∩{(cℓ)(0)}  , on sait que l'ordre de a  , qui est le nombre d'éléments du groupe <a>  , divise le nombre d'éléments de ℤ/19ℤ∩{(cℓ)(0)}  , c'est-à-dire 18  .

 

Ainsi, pour tout élément a  de ℤ/19ℤ∩{(cℓ)(0)}  , a^18=(cℓ)(1)  . L'équation étudiée se simplifie donc grandement en (cℓ)(1)=(cℓ)(3)a  , c'est-à-dire a=((cℓ)(3))^-1  . Sa résolution se ramène donc à la recherche de l'inverse de (cℓ)(3)  dans ℤ/19ℤ  ; on écrit alors une relation de Bézout : 13*3-2*19=1  et on en déduit que ((cℓ)(3))^-1=(cℓ)(13)  .

 

Finalement les solutions de l'équation initiale sont donc x≡13|(19)| 

 

Exemple  Résoudre dans ℤ  l'équation suivante, d'inconnue x  : x^14≡1|(19)|  Ce sont les mêmes idées que dans l'exemple précédent qui font marcher cet exercice, en un peu plus astucieux encore.

 

Comme dans l'exemple prédédent, on commence par passer dans ℤ/19ℤ  , où l'équation s'écrit dès lors : (cℓ)(x)^14=(cℓ)(1)  . On note a=(cℓ)(x)  , on remarque que (cℓ)(0)  n'est pas solution, et on décide donc de résoudre a^14=(cℓ)(1)  dans ℤ/19ℤ∩{(cℓ)(0)}  .

 

Maintenant, on remarque que pour tout a  de ℤ/19ℤ∩{(cℓ)(0)}  , dire que a^14=(cℓ)(1)  équivaut à dire que l'ordre de a  divise 14  . Par ailleurs, comme dans l'exemple précédent, pour tout élément a  de ℤ/19ℤ∩{(cℓ)(0)}  , l'ordre de a  divise 18  . Ainsi, l'ordre de a  divise 14  si et seulement s'il divise 14  et 18  , donc si et seulement s'il divise pgcd(14,18)=2  .

 

On a donc montré que pour tout a  de ℤ/19ℤ∩{(cℓ)(0)}  , a^14=(cℓ)(1)  si et seulement si a²=(cℓ)(1)  .

 

Cette nouvelle équation est alors très facile à résoudre : a²=(cℓ)(1)  si et seulement si (a+(cℓ)(1))(a-(cℓ)(1))=(...  si et seulement si a=(cℓ)(1)  ou a=-(cℓ)(1)=(cℓ)(18)  .

 

Les solutions de l'équation initiale sont donc x≡1|(19)|oux≡18|(19)|