École Supérieure du Professorat et de l’Éducation 2015–16Master MEEF — Semestre 1S. Vinatier

Arithmétique1 L’anneau ZProposition 1 (Z, +,×) est un anneau.

Cela signifie que :• (Z, +) est un groupe ((a + b) + c = a + (b + c) ; 0 + a = a ; ∀a ∈ Z,∃b ∈ Z, a + b = 0) abélien

(a + b = b + a) ;• × est associative : (ab)c = a(bc) ;• × est distributive sur + : a(b + c) = ab + ac.Étant donné a, l’élément b tel que a + b = 0 s’appelle l’opposé de a (b = −a).

De plus, 1 est élement neutre pour × : l’anneau est unitaire ; × est commutative (ab = ba) :l’anneau est commutatif.

Attention : même si × est associative et admet un élément neutre, (Z,×) n’est pas un groupe :très peu d’entiers ont un inverse ; en fait les seuls éléments inversibles (on dit aussi unités) de Z sont1 et −1.

Exercice 1 Le prouver en utilisant des propriétés de divisibilité.

Rappelons que Z est un ensemble totalement ordonné (a ≤ b⇔ b− a ≥ 0). Si l’on suppose quea, b ∈ Z vérifient ab = 0, on a alors par distributivité et unicité de l’opposé −a = (b− 1)a. On peutde plus supposer que b ≥ 0 (car ab = 0 ⇔ a(−b) = 0). Il s’ensuit que b = 0 ou b ≥ 1. Dans ledeuxième cas, b− 1 ≥ 0, donc (b− 1)a est de signe opposé à celui de −a ; comme ces deux nombressont égaux et de signes opposés, ils valent 0, c’est-à-dire a = 0. On obtient finalement la propriétésuivante.

Proposition 2 Z est un anneau intègre : ab = 0⇒ a = 0 ou b = 0.

Ceci entraîne que Z est un sous-anneau de son corps des fractions Q.On rappelle qu’un sous-groupe de (Z, +) est une partie A ⊂ Z telle que A 6= ∅ et A est stable

par addition et passage à l’opposé : ∀a, b ∈ A, a− b ∈ A. Ceci entraîne en particulier que 0 ∈ A.

Proposition 3 Tout sous-groupe de (Z, +) est de la forme (aZ, +) pour un entier a.

La preuve utilise le fait que Z est ordonné : A étant non vide, on peut considérer le plus petit élémentstrictement positif a de A et on montre que A = aZ = {na, n ∈ Z}.

Les sous-groupes additifs de Z sont en fait des idéaux de l’anneau Z : ils sont aussi stables par×. Ce sont même des idéaux principaux, c’est-à-dire qu’ils sont engendrés (multiplicativement) parun seul élément. De fait aZ n’est autre que l’ensemble des multiples (entiers) de a. Remarquons aupassage que a et −a engendrent le même idéal : aZ = −aZ.

Exercice 2 Montrer que si deux entiers a et b engendrent le même idéal, alors a = ±b.

Un anneau dont tout idéal est principal est dit principal, on a donc :

Proposition 4 Z est un anneau principal.

1

En fait Z vérifie une propriété plus forte : il est euclidien, c’est-à-dire :

∀(a, b) ∈ Z2, ∃!(q, r) ∈ Z2, a = bq + r et 0 ≤ r < b .

Le point d’exclamation ( !) signifie que le couple (q, r) vérifiant la propriété est unique. On montreque tout anneau euclidien est principal.

Exercice 3 Quels sont les entiers qui, dans la division par 29, donnent un quotient égal au reste ?

2 DivisibilitéDéfinition 1 Étant donnés a, b ∈ Z, on dit que a divise b s’il existe n ∈ Z tel que b = na ; on notecette relation a | b.

On dit aussi, dans cette situation, que b est un multiple de a, que b est divisible par a, que a est undiviseur de b,... Notons que a | b si et seulement si le reste de b dans la division euclidienne par a estnul. Par ailleurs, on a l’équivalence :

a | b ⇔ b ∈ aZ ⇔ bZ ⊂ aZ .

Exercice 4 Des cas particuliers : quels entiers divisent 0 ? lesquels divisent tous les entiers ? Quelsentiers sont divisibles par 2 ? par 5 ?Vérifier que tout entier a non inversible (a 6= ±1) a au moins quatre diviseurs.

Définition 2 Un entier p est dit premier si p n’est pas inversible et p = ab⇒ a ou b inversible.

On dit aussi irréductible. On en déduit la caractérisation :

Proposition 5 p ∈ Z est premier si et seulement si p a exactement quatre diviseurs.

On ne considère souvent que les diviseurs entiers naturels (positifs), auquel cas cette caractérisationdevient : p premier si et seulement si p a exactement deux diviseurs positifs.

Si l’on s’en tient aux entiers naturels, 0 et 1 ne sont pas premiers, 2 et 3 le sont, 4 ne l’est pas(combien de diviseurs / comment l’écrire produit de deux entiers non inversibles ?), 5, 7, 11 le sont...La propriété suivante est connue depuis l’Antiquité.

Proposition 6 Z contient une infinité de nombres premiers.

En considérant le plus petit diviseur ≥ 2 d’un entier (Z est ordonné), on montre le résultat fonda-mental :

Théorème 1 Tout entier non inversible admet un diviseur premier. Si n ≥ 2, il admet un diviseurpremier p ≤

√n.

Exercice 5 En déduire que 167 est premier : combien de tests de divisibilité faut-il faire ?

On peut voir le crible d’Eratosthène comme une application de ce résultat : pour connaître tousles nombres premiers inférieurs à un entier naturel n, on écrit la liste des entiers de 2 à n puis, enpartant du plus petit, on barre tous ses multiples qui apparaissent dans la liste, jusqu’à arriver à lapartie entière de

√n. Les entiers non barrés sont premiers :

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

On déduit le théorème fondamental de l’arithmétique du théorème précédent, en itérant le pro-cessus de factorisation (n = pn′, n′ = p′n′′,...) jusqu’à obtenir un quotient inversible (à chaque étape,il diminue strictement en valeur absolue : |n| > |n′| > |n′′| > . . .).

2

Corollaire 1 Tout n ∈ Z \ {0} s’écrit de façon unique sous la forme ±1 multiplié par un produitde puissances de nombres premiers.

L’unicité de la décomposition est bien sûr à l’ordre près des facteurs. On traduit cette propriété endisant que Z est un anneau factoriel. Par exemple

120 = 2× 60 = 22 × 30 = 23 × 15 = 23 × 3× 5 .

Exercice 6 Quel est le nombre de diviseurs de 120 ?

Étant donné un entier n 6= 0, on note quelquefois vp(n) l’exposant (∈ N) d’un nombre premier pdans sa décomposition (unique !) donnée par le théorème fondamental de l’arithmétique. On a alors :

p | n⇔ vp(n) ≥ 1 ,

donc vp(n) = 0 pour presque tout nombre premier p (tous sauf un nombre fini).

Exercice 7 Montrer que si m est aussi un entier non nul, on a :

n | m⇔(∀p premier, vp(n) ≤ vp(m)

).

3 pgcd, ppcmTout entier non nul admet un nombre fini de diviseurs positifs, tandis que l’ensemble de ses

multiples strictement positifs est infini mais minoré par sa valeur absolue, ce qui justifie les définitionssuivantes.

Définition 3 Étant donnés a, b ∈ Z avec a 6= 0 ou b 6= 0, on définit• a ∧ b = pgcd(a, b) le plus grand diviseur (positif) commun à a et b ;• a ∨ b = ppcm(a, b) le plus petit multiple (strictement positif) commun à a et b.Enfin on pose 0 ∧ 0 = 0 ∨ 0 = 0.

Exercice 8 Que valent a ∧ 0 et a ∨ 0 pour a 6= 0 ?

Le théorème fondamental de l’arithmétique donne un moyen de calculer le pgcd et le ppcm dedeux entiers non nuls.

Proposition 7 Soient a, b ∈ Z \ {0} et {p1, . . . , pr} l’ensemble des diviseurs premiers de a ou b, sibien qu’on a :

a = ±r∏

i=1p

vpi (a)i , b = ±

r∏i=1

pvpi (b)i .

Alorsa ∧ b =

r∏i=1

pmin{vpi (a),vpi (b)}i , a ∨ b =

r∏i=1

pmax{vpi (a),vpi (b)}i

Exercice 9 En déduire le pgcd et le ppcm de 120 et −54. Le retrouver en utilisant l’algorithmed’Euclide (divisions euclidiennes réitérées).

Il en découle immédiatement :

Corollaire 2 On a : |ab| = (a ∧ b)(a ∨ b).

3

Le pgcd et le ppcm ont une interprétation en termes d’idéaux. Notons d’abord que si a, b ∈ Z,les ensembles

I = aZ + bZ = {an + bm, n ∈ Z, m ∈ Z} et J = aZ ∩ bZ

sont des idéaux de Z (sous-groupes stables par ×). En fait, aZ + bZ est le plus petit idéal de Zcontenant aZ ∪ bZ. Or Z est principal donc il existe n, m ∈ Z tels que I = nZ et J = mZ.

Théorème 2 Soient a, b ∈ Z, alors

aZ + bZ = (a ∧ b)Z et aZ ∩ bZ = (a ∨ b)Z .

La démonstration du théorème se fait en traduisant la relation de divisibilité en termes d’idéaux.On en déduit le théorème de Bézout.

Corollaire 3 Étant donnés a, b ∈ Z, il existe u, v ∈ Z tels que au + bv = a ∧ b.

Définition 4 a et b sont dits premiers entre eux si a ∧ b = 1.

Corollaire 4 a et b sont premiers entre eux si et seulement si il existe u, v ∈ Z tels que au+bv = 1.

Comment trouver une relation de Bézout entre a et b, c’est-à-dire trouver u, v ∈ Z tels queau + bv = a ∧ b ? On utilise l’algorithme d’Euclide étendu : pour a = 150 et b = 32 :

150 = 32× 4 + 22 ; 32 = 22× 1 + 10 ; 22 = 10× 2 + 2 ; 10 = 5× 2 + 0

donc 150 ∧ 32 = 2 et

2 = 22−10×2 = 22−(32−22×1)×2 = 22×3−32×2 = (150−32×4)×3−32×2 = 150×3−32×14

Exercice 10 Démontrer le théorème de Gauss : Si a | bc et a ∧ b = 1 alors a | c.

Exercice 11 Soit p un nombre premier. Montrer que, pour tout entier n, p | n ou p ∧ n = 1.

4 CongruencesOn fixe un entier n ∈ Z.

Définition 5 Deux entiers a et b sont congrus modulo n si n | a− b, ce que l’on note :

a ≡ b mod n .

Cette relation est clairement symétrique puisque n | a − b ⇔ n | b − a ; elle est aussi réflexive(∀a ∈ Z, a ≡ a mod n) et transitive :

∀a, b, c ∈ Z , (a ≡ b mod n et b ≡ c mod n)⇒ a ≡ c mod n .

La relation de congruence modulo n est donc une relation d’équivalence.Cette notion est plus naturelle qu’il peut sembler au premier abord.

Exercice 12 Le record actuel pour la traversée de l’Atlantique à la voile en solitaire dans le sensouest-est (le plus rapide) est de 5 jours 2h 56mn et 10s. Il a été établi par Francis Joyon en 2013 entreNew York et le Cap Lizard (Grande Bretagne). Supposons qu’il ait quitté New York à exactement12h UTC (heure du temps universel coordonné, c’est-à-dire 12h en Grande Bretagne), à quelle heureUTC est-il arrivé au Cap Lizard ?

Imaginons que vous fêtez aujourd’hui mercredi 21 octobre 2015 vos 22 ans. Quel jour de lasemaine êtes-vous né ? (Les années 1996, 2000, 2004, 2008 et 2012 étaient toutes bissextiles.)

4

L’utilisation d’une congruence correspond le plus souvent à une « perte d’information » : dans lesexemples précédents, on oublie les jours (resp. les années, mois et semaines) pour ne garder que lesheures, minutes et secondes (resp. les jours), ce qui simplifie les calculs menant au résultat recherché.

Exercice 13 Soient k ∈ Z et ε ∈ {0, 1}, développer (2k + ε)2. En déduire que le carré d’un entierest toujours congru à 0 ou 1 modulo 4. Faire un raisonnement analogue pour montrer que le cubed’un entier est toujours congru à −1, 0 ou 1 modulo 9.

Ces considérations élémentaires permettent de résoudre certains équations diophantiennes (en nombresentiers), par exemple de prouver le 1er cas du théorème de Fermat pour l’exposant 3. Il s’agit demontrer que l’équation x3 + y3 = z3 n’a pas de solution en nombres entiers x, y et z premiers à 3.

Exercice 14 On suppose que (x, y, z) est solution du problème, montrer qu’alors x3 + y3 ≡ −2, 0ou 2 mod 9 ; en déduire une contradiction. On remplace 3 par 5, peut-on faire de même ?

Avec 7 en exposant, la méthode ne fonctionne plus : 17 + 307 ≡ 317 mod 49.La relation de congruence modulo n s’accorde bien à la structure d’anneau de Z :

Proposition 8 Soient a, b, c, d ∈ Z, alors :

(a ≡ b mod n et c ≡ d mod n)⇒ (a + c ≡ b + d mod n et ac ≡ bd mod n)

Il s’ensuit aisément que, si k ∈ N, a ≡ b mod n⇒ ak ≡ bk mod n.

Exercice 15 Prouver ces assertions. En déduire les critères de divisibilité par 3, 9 et 11 pour lesentiers écrits en base 10.

Exercice 16 Soient m ∈ Z et d = n ∧ m. Montrer l’assertion (extraite du programme BTS) :« modulo n, les multiples de m sont les multiples de d ».

5 Les anneaux Z/nZUne relation binaire R sur un ensemble E est un sous-ensemble Γ de E×E, appelé le graphe de

R ; si (x, y) ∈ Γ, on écrit xR y.

Exemple 1 La congruence modulo un entier n est une relation binaire sur Z ; son graphe est consti-tué des couples d’entiers (x, y) tels que n | x− y.

Rappelons qu’une relation binaire sur un ensemble E est dite relation d’équivalence si elle estréflexive (xRx), symétrique (xR y ⇔ yRx) et transitive (xR y et yR z impliquent xR z).

Définition 6 Soit R une relation d’équivalence sur un ensemble E. Pour tout x ∈ E, on noteCl(x) = {y ∈ E, xR y} la classe de x et

E/R = {Cl(x), x ∈ E}

l’ensemble quotient de E par R.

Pour n ∈ Z, l’ensemble quotient de Z par la relation de congruence modulo n est noté Z/nZ.

Exemple 2 Considérons la congruence modulo 7. Pour x ∈ Z,

Cl(x) = {y ∈ Z, 7 | x− y} = {x + 7k, k ∈ Z} ⊂ Z .

En particulier Cl(0) = Cl(7) = Cl(14) = . . . est l’ensemble des multiples de 7. De même Cl(x) =Cl(x + 7) pour tout entier x ; il y a donc exactement 7 classes distinctes :

Z/7Z = {Cl(0), Cl(1), . . . , Cl(6)} .

5

Exercice 17 Décrire l’ensemble quotient Z/0Z.

Pour n ∈ Z, les éléments de l’ensemble des classes Z/nZ sont des sous-ensembles de Z. On peutpourtant faire des calculs avec eux (presque) comme avec les entiers.

Proposition 9 Soit n ∈ Z. Pour x, y ∈ Z, les classes Cl(x + y) et Cl(xy) de x + y et xy modulo nne dépendent que de Cl(x) et Cl(y), ce qui permet de définir sur Z/nZ les lois internes + et · par

Cl(x) + Cl(y) = Cl(x + y) , Cl(x) · Cl(y) = Cl(xy) .

Elles munissent Z/nZ d’une structure d’anneau commutatif unitaire.

La première assertion signifie que Cl(x + y) et Cl(xy) ne sont pas modifiées si l’on remplace x et ypar x + kn et y + lm, où k, l sont des entiers. On a clairement que Cl(0) et Cl(1) sont les élémentsneutres pour l’addition et la multiplication dans Z/nZ et que Cl(−x) est l’opposé de Cl(x) pourtout entier x.

Exercice 18 Décrire les éléments et écrire les tables d’addition et de multiplication de Z/2Z (onpourra noter x̄ la classe d’un entier x).

Remarque. La classe d’un entier x modulo n est souvent notée Cl(x) = x̄, ou Cl(x) = x mod n sil’on veut préciser l’entier n.

La propriété suivante décrit les éléments inversibles, elle se prouve facilement à l’aide du théorèmede Bézout (exercice).

Proposition 10 Les inversibles de Z/nZ sont les m̄ pour m ∈ Z tel que n ∧m = 1.

L’ensemble des éléments inversibles de Z/nZ est noté (Z/nZ)∗, c’est un groupe multiplicatif. Soncardinal ϕ(n) est l’indicatrice d’Euler de l’entier n et on a

ϕ(n) = card{m ∈ Z, 0 ≤ m ≤ n− 1, n ∧m = 1} .

Exercice 19 Décrire le groupe (Z/9Z)∗, que vaut ϕ(9) ?

Soit p un premier, on voit que ϕ(p) = p− 1 car tout entier compris entre 1 et p− 1 est premier à p.Il s’ensuit que (Z/pZ)∗ = Z/pZ \ {0̄}, autrement dit tout élément non nul de Z/pZ est inversible,donc Z/pZ est un corps. En utilisant le théorème de Lagrange (« l’ordre d’un élément divise l’ordredu groupe ») dans le groupe multiplicatif (Z/pZ)∗, on obtient le « petit » théorème de Fermat :

Corollaire 5 Soit p un nombre premier et a un entier premier à p, alors ap−1 ≡ 1 mod p.

On en déduit aisément que, pour tout entier b, bp ≡ b mod p.Donnons enfin le fameux « théorème chinois des restes ».

Théorème 3 Soient a, b des entiers premiers entre eux, alors l’application

Z/abZ −→ Z/aZ× Z/bZx mod ab 7−→ (x mod a, x mod b)

est un isomorphime d’anneaux.

Autrement dit, cette application est une bijection compatible avec les structures d’anneaux desensembles de départ et d’arrivée (structure induite par le produit cartésien dans l’ensemble d’arri-vée, c’est-à-dire que les lois sont définies coordonnée par coordonnée). Elle induit en particulier unisomorphisme de groupes sur les groupes multiplicatifs des éléments inversibles :

(Z/abZ)∗ ' (Z/aZ)∗ × (Z/bZ)∗ ,

d’où l’on tire la « multiplicativité » de l’indicatrice d’Euler :

6

Corollaire 6 Sous la même hypothèse, on a ϕ(ab) = ϕ(a)ϕ(b).

Exercice 20 Soient u, v ∈ Z tels que au + bv = 1. Vérifier que l’application réciproque est donnéepar :

(x mod a, y mod b) 7→ xbv + yau mod ab .

Exercice 21 Une bande de 17 pirates s’est emaprée d’un butin composé de pièces d’or d’égale valeur.Ils décident de se les partager également et de donner le reste au cuisinier. Celui-ci recevrait alors3 pièces. Mais les pirates se querellent et six d’entre eux sont tués. Le cuisinier recevrait alors 4pièces. Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés et le partagedonnerait alors 5 pièces d’or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisiniers’il décide d’empoisonner le reste des pirates ?

6 Compléments

6.1 Bases de numérationSoient a, b des entiers naturels avec b ≥ 1. Soit N ∈ N tel que aN ≤ b < aN+1. On montre par

des divisions euclidiennes successives (par les ak, k descendant de N à 1) qu’il existe des entiersb0, b1, . . . , bN tous compris entre 0 et a− 1 tels que

b =N∑

k=0bkak .

En effet, la division euclidienne de b par aN s’écrit b = qaN +r avec 0 ≤ r < aN et on a 0 ≤ q ≤ aN−1à cause du choix de N (on a même q ≥ 1). On pose bN = q et on recommence en divisant r paraN−1, etc. La suite finie (b0, b1, . . . , bN) s’appelle numérotation en base a de b et on note :

b = (bNbN−1 . . . b1b0)a .

La base la plus courante est la base 10 (on omet en général le 10 en indice). En informatique onutilise aussi fréquemment les bases 2 (les chiffres utilisés sont 0 et 1) et 16 (les « chiffres » utiliséssont 0, 1, 2, . . . , 9, A, B, C, D, E, F ).

Exercice 22 Écrire 201510 en base 16 ; 3110 en base 2 ; 2B116 en base 10 ; 1010101010102 en base16.

Citons aussi le théorème de Lucas, qui concerne le reste modulo un nombre premier du cœfficientbinomial

(nm

)= n!

(n−m)!m! de deux entiers naturels n et m, avec la convention(

nm

)= 0 si n < m.

Théorème 4 Soit p un nombre premier alors, pour n, m ∈ N,(n

m

)≡

N∏i=0

(ni

mi

)mod p ,

où n =N∑

i=0nip

i et m =N∑

i=0mip

i sont les numérotations en base p de n et m (c’est-à-dire ni, mi ∈

{0, 1, . . . , p− 1} pour tout 0 ≤ i ≤ N).

Corollaire 7 Avec les mêmes notations, p |(

nm

)⇔ ∃i ∈ {0, . . . , N}, mi > ni.

7

6.2 Interprétation géométrique de la coprimalité de deux entiersSoient a, b des entiers naturels. On place b points sur un cercle de façon régulière et on les

parcourt, à partir de l’un d’eux, par sauts d’amplitude a (on saute a− 1 points), jusqu’à revenir aupoint de départ.

Proposition 11 Le parcours est exhaustif si et seulement si a ∧ b = 1.

5 et 2 ne sont pas premiers à 10, 4 et 3 le sont 5, 4, 3, 2 et 1 sont premiers à 11

6.3 ApplicationsReste à traiter (vus dans les programmes de TS spé maths) :— problèmes de codages (clef des numéros ISBN, RIB, INSEE,...) ;— problèmes de chiffrement (affine, Vigenère, Hill, RSA) ;— répartition des nombres premiers, tests de primalité, premiers de Fermat, Mersenne, Carmi-

chaël ;

8