Pour deux entiers relatifs a et b avec b=0, on dit que b divise a, et l'on note b∣a, s'il existe k∈Z tel que a=kb. Pour a∈Z et b∈N∗, la division euclidienne de a par b donne un unique couple d'entiers (q;r) tel que a=bq+r et 0≤r<b. Pour un entier n≥2, a est congru à b modulo n, noté a≡b [n], si n divise a−b : a et b ont alors le même reste dans la division par n. Exemple : −47=6×(−8)+1 avec 0≤1<6, donc le reste de −47 par 6 est 1 et −47≡1 [6].
Chapitre du semestre 2 de la 1re année du baccalauréat sciences mathématiques (option française BIOF) ; les sciences expérimentales ne l'étudient pas. Il étend à Z l'arithmétique dans ℕ du tronc commun et ajoute les congruences et Z/nZ. Les entiers premiers entre eux, Bézout, Gauss et Fermat viennent en 2e année du bac SM.
Divisibilité dans Z : diviseurs, multiples et propriétés
Diviseur et multiple d’un entier relatif
Soient a∈Z et b∈Z∗. On dit que b divise a, ou que b est un diviseur de a, ou que a est un multiple de b, s'il existe k∈Z tel que a=kb. On note b∣a, et b∤a sinon. Les multiples de b forment l'ensemble bZ={kb / k∈Z}.
Comme a=kb⟺a=(−k)(−b)⟺−a=(−k)b, on a b∣a⟺−b∣a⟺b∣−a : il suffit de chercher les diviseurs positifs, puis d'ajouter leurs opposés. Tout b=0 divise 0.
Propriétés de la divisibilité
Soient a, b, c des entiers relatifs, non nuls lorsqu'ils sont placés à gauche du symbole ∣.
- Transitivité : si a∣b et b∣c, alors a∣c.
- Combinaison : si a∣b et a∣c, alors a∣ub+vc pour tous u,v∈Z.
- Si a∣b et b=0, alors ∣a∣≤∣b∣ : un entier non nul n'a qu'un nombre fini de diviseurs.
- Si a∣b et b∣a, alors ∣a∣=∣b∣, c'est-à-dire a=b ou a=−b.
Démonstration : transitivité, combinaison et majoration
Si b=ka et c=k′b avec k,k′∈Z, alors c=(k′k)a. Si b=ka et c=k′a, alors ub+vc=(uk+vk′)a avec uk+vk′∈Z. Enfin, si b=ka avec b=0, alors k=0, donc ∣k∣≥1 et ∣b∣=∣k∣∣a∣≥∣a∣ ; si de plus b∣a, on a aussi ∣b∣≤∣a∣.
Méthode : trouver les entiers n tels qu’une expression en divise une autre
On écrit An+B=A(n+α)+(B−Aα). Comme n+α divise A(n+α), la propriété de combinaison donne n+α∣An+B⟺n+α∣B−Aα : on liste les diviseurs, positifs et négatifs, de cette constante.
Exemple 1 : un diviseur qui dépend de n
Cherchons les entiers n=−2 tels que n+2∣3n+17. On écrit 3n+17=3(n+2)+11, donc n+2∣3n+17⟺n+2∣11. Les diviseurs de 11, nombre premier, sont −11, −1, 1 et 11 :
n∈{−13;−3;−1;9}.Division euclidienne dans Z
Théorème de la division euclidienne dans Z
Soient a∈Z et b∈N∗. Il existe un unique couple (q;r)∈Z×N tel que
a=bq+ret0≤r<b.q est le quotient et r le reste de la division euclidienne de a par b. De plus, b∣a⟺r=0.
Démonstration : existence et unicité du quotient et du reste
Existence : soit q=E(ba), la partie entière de ba. Alors q≤ba<q+1 ; en multipliant par b>0, bq≤a<bq+b, donc r=a−bq vérifie 0≤r<b. Unicité : si a=bq+r=bq′+r′ avec 0≤r<b et 0≤r′<b, alors b∣q−q′∣=∣r′−r∣<b, donc ∣q−q′∣<1, soit q=q′, puis r=r′. Enfin, si a=kb, l'écriture a=bk+0 est la division euclidienne, donc r=0 ; la réciproque est immédiate.
Pour b entier négatif non nul, on divise a par ∣b∣=−b : a=∣b∣q′+r avec 0≤r<∣b∣, donc a=b×(−q′)+r. Par exemple 38=5×7+3=(−5)×(−7)+3.
Exemple 2 : diviser un entier négatif
Divisons −250 par 9. D'abord 250=9×27+7, donc −250=9×(−27)−7, qui n'est pas la division euclidienne car −7<0. On retire 9 au produit et on l'ajoute au reste :
−250=9×(−28)+2.Comme 0≤2<9, le quotient est −28 et le reste 2.
Attention : le reste est toujours positif ou nul. Le reste de
−250 par 9 n'est ni
−7 ni 7, mais 2. En général, si
a=bq+r avec
0<r<b, alors
−a=b(−q−1)+(b−r).
Méthode : raisonner selon le reste de la division par b
Tout entier relatif s'écrit n=bq+r avec r∈{0;1;…;b−1}. Pour démontrer une propriété de tous les entiers, on traite chacun des b restes possibles : c'est un raisonnement par disjonction des cas.
Exemple 3 : un carré augmenté de 2 n’est jamais multiple de 5
Soit n=5q+r avec q∈Z et r∈{0;1;2;3;4}. Alors n2=5(5q2+2qr)+r2 : n2 a le même reste que r2 dans la division par 5. Pour r2=0, 1, 4, 9, 16, ce reste vaut 0, 1, 4, 4, 1. Le reste de n2+2 vaut donc 2, 3 ou 1, jamais 0 : n2+2 n'est multiple de 5 pour aucun entier n.
Nombres premiers et décomposition en facteurs premiers
Définition d’un nombre premier
Un entier naturel p est premier s'il a exactement deux diviseurs positifs, 1 et p. Cela impose p≥2 : 1 n'est pas premier. Les premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ; le crible d'Ératosthène les donne jusqu'à une borne fixée.
Plus petit diviseur premier et test de primalité
Soit n un entier naturel, n≥2.
- Le plus petit diviseur p≥2 de n est premier : tout entier n≥2 a un diviseur premier.
- Si n n'est pas premier, ce plus petit diviseur vérifie p2≤n.
- Test : si aucun nombre premier p tel que p2≤n ne divise n, alors n est premier.
Démonstration : le plus petit diviseur supérieur à 1 est premier
Soit p le plus petit diviseur de n supérieur ou égal à 2 (il en existe : n lui-même). Si p n'était pas premier, il aurait un diviseur d tel que 1<d<p, qui diviserait n par transitivité : contradiction. Si n n'est pas premier, p=n et n=pm avec m≥2 diviseur de n, donc m≥p et n=pm≥p2. Le test est la contraposée de ce second point.
Exemple 4 : tester si 419 et 667 sont premiers
202=400≤419<441=212 : on teste les nombres premiers jusqu'à 19. 419 n'est divisible ni par 2, ni par 3 (somme des chiffres 14), ni par 5, et
419=7×59+6=11×38+1=13×32+3=17×24+11=19×22+1.Aucun reste n'est nul : 419 est premier. Pour 667, 252=625≤667<676=262 ; aucun nombre premier jusqu'à 19 ne divise 667, mais 667=23×29 : 667 n'est pas premier.
Infinité des nombres premiers
L'ensemble des nombres premiers est infini.
Démonstration : il existe une infinité de nombres premiers
Raisonnons par l'absurde : supposons qu'il n'existe qu'un nombre fini de nombres premiers p1,…,pk, et posons N=p1p2⋯pk+1≥3. N admet un diviseur premier, qui est donc l'un des pi. Alors pi divise N et p1p2⋯pk, donc leur différence 1, ce qui est impossible car pi≥2.
Décomposition en produit de facteurs premiers
Tout entier naturel n≥2 s'écrit n=p1α1p2α2⋯pkαk, où p1<p2<⋯<pk sont des nombres premiers et α1,…,αk des entiers naturels non nuls. On l'obtient en divisant par le plus petit diviseur premier, puis en recommençant avec le quotient ; l'unicité est admise. Pour n∈Z, ∣n∣≥2, on décompose ∣n∣. Conséquences :
- les diviseurs positifs de n sont les p1β1⋯pkβk avec 0≤βi≤αi. Il y en a (α1+1)(α2+1)⋯(αk+1), et deux fois plus dans Z ;
- si un nombre premier p divise un produit ab de deux entiers non nuls, alors p∣a ou p∣b. En effet, ∣ab∣=pm avec m∈N∗ : décomposer m donne une décomposition de ∣ab∣ qui contient p, et mettre bout à bout celles de ∣a∣ et de ∣b∣ en donne une autre. Par l'unicité admise, elles coïncident : p figure dans celle de ∣a∣ ou dans celle de ∣b∣.
Attention : cette dernière propriété est fausse pour un diviseur qui n'est pas premier :
10∣4×15, mais
10∤4 et
10∤15. Exemple 5 : décomposer 1188 et compter ses diviseurs
On divise par les nombres premiers dans l'ordre croissant :
1188=2×594=22×297=22×33×11.Les exposants sont 2, 3 et 1 : 1 188 a (2+1)(3+1)(1+1)=24 diviseurs positifs et 48 diviseurs dans Z.
PGCD, algorithme d’Euclide et PPCM
Plus grand commun diviseur de deux entiers relatifs
Soient a et b deux entiers relatifs non tous les deux nuls. L'ensemble de leurs diviseurs communs est fini et contient 1 ; son plus grand élément est le PGCD de a et b, noté a∧b ou pgcd(a;b). On a a∧b≥1, a∧b=∣a∣∧∣b∣, a∧0=∣a∣ si a=0, et a∧b=∣b∣ si b=0 et b∣a.
Algorithme d’Euclide
Soient a∈Z, b∈N∗ et r le reste de la division euclidienne de a par b. Alors a∧b=b∧r. On divise a par b, puis b par r, et ainsi de suite : les restes sont des entiers naturels strictement décroissants, donc l'un d'eux est nul, et a∧b est le dernier reste non nul.
Démonstration : les deux couples ont les mêmes diviseurs communs
Comme r=a−bq, un diviseur commun de a et b divise r ; comme a=bq+r, un diviseur commun de b et r divise a. Les deux couples ont donc les mêmes diviseurs communs. En notant r0=b, r1=r, …, rk le dernier reste non nul, on obtient
a∧b=r0∧r1=r1∧r2=⋯=rk−1∧rk=rk,car le dernier pas s'écrit rk−1=rkq+0.
Diviseurs communs et PGCD de deux multiples
- Les diviseurs communs de a et b sont exactement les diviseurs de a∧b : chaque étape de l'algorithme conserve les diviseurs communs, et ceux du dernier reste non nul et de 0 sont les diviseurs de ce reste.
- Pour a∈Z, b∈N∗ et k∈N∗, (ka)∧(kb)=k(a∧b) : les divisions ka=(kb)q+kr, avec 0≤kr<kb, montrent que l'algorithme appliqué à ka et kb donne les mêmes quotients et des restes multipliés par k.
Exemple 6 : PGCD de 2717 et 1105 par l’algorithme d’Euclide
27171105507915239=1105×2+507=507×2+91=91×5+52=52×1+39=39×1+13=13×3+0Le dernier reste non nul est 13 : 2717∧1105=13. Les diviseurs communs de 2 717 et 1 105 sont donc −13, −1, 1 et 13.
Plus petit commun multiple
Soient a,b∈Z∗. Le plus petit multiple commun strictement positif de a et b est leur PPCM, noté a∨b ou ppcm(a;b). Il existe, car ∣ab∣ est un multiple commun strictement positif, et les multiples communs de a et b sont exactement les multiples de a∨b.
Démonstration : les multiples communs sont les multiples du PPCM
Soit m=a∨b. Un multiple de m est multiple de a et de b par transitivité. Réciproquement, soit c un multiple commun, et c=mq+r avec 0≤r<m. Alors r=c−mq est un multiple commun de a et b, positif ou nul et inférieur à m : par définition de m, il est nul. Donc m∣c.
PGCD et PPCM à partir des décompositions
Soient a,b∈Z∗. On écrit ∣a∣ et ∣b∣ avec les mêmes nombres premiers pi, quitte à mettre des exposants nuls : pi a l'exposant αi dans ∣a∣ et βi dans ∣b∣.
- Dans a∧b, chaque pi a l'exposant min(αi,βi) : un diviseur commun a des exposants au plus égaux à αi et à βi.
- Dans a∨b, chaque pi a l'exposant max(αi,βi) : un multiple commun a des exposants au moins égaux à αi et à βi.
- Comme min(α,β)+max(α,β)=α+β, on obtient (a∧b)(a∨b)=∣ab∣.
Exemple 7 : PGCD et PPCM de 440 et 396 par leurs décompositions
440=23×5×11 et 396=22×32×11. On prend, pour chaque nombre premier, le plus petit exposant, puis le plus grand :
440∧396440∨396=22×11=44,=23×32×5×11=3960.Attention : le PPCM n'est pas le produit en général ; ici, il est 44 fois plus petit que
440×396. Congruence modulo n
Définition de la congruence modulo n
Soit n un entier naturel, n≥2. Deux entiers relatifs a et b sont congrus modulo n, noté a≡b [n], si n∣a−b. Elle est réflexive, symétrique et transitive : c'est une relation d'équivalence. En particulier, n∣a⟺a≡0 [n], et le chiffre des unités d'un entier naturel est son reste modulo 10.
Congruence et reste de la division euclidienne
Soit n≥2. Alors a≡b [n] si et seulement si a et b ont le même reste dans la division euclidienne par n. Le reste de a par n est l'unique entier r tel que a≡r [n] et 0≤r≤n−1.
Démonstration : deux entiers congrus ont le même reste
Écrivons a=nq+r et b=nq′+r′, avec r et r′ dans {0;…;n−1}. Alors a−b=n(q−q′)+(r−r′), donc n∣a−b⟺n∣r−r′. Or −n<r−r′<n, et le seul multiple de n dans cet intervalle est 0 : n∣a−b⟺r=r′. Enfin, si a≡r0 [n] avec 0≤r0≤n−1, r0 est son propre reste, donc celui de a.
Compatibilité avec l’addition, la multiplication et les puissances
Soient n≥2 et a,b,c,d∈Z tels que a≡b [n] et c≡d [n]. Alors
a+c≡b+d [n],a−c≡b−d [n],ac≡bd [n],ak≡bk [n] (k∈N).Démonstration : produit et puissances
(a+c)−(b+d)=(a−b)+(c−d) est un multiple de n, de même pour la différence, et ac−bd=a(c−d)+d(a−b) aussi. Pour les puissances, on raisonne par récurrence sur k : notons P(k) la proposition « ak≡bk [n] ».
Initialisation. a0=b0=1, donc P(0) est vraie.
Hérédité. Soit k∈N tel que P(k) soit vraie. En multipliant membre à membre ak≡bk [n] et a≡b [n], ce que permet la règle du produit, on obtient ak+1≡bk+1 [n] : c'est P(k+1).
Conclusion. Par récurrence, ak≡bk [n] pour tout k∈N.
Attention : on remplace la base par un entier congru, jamais l'exposant.
12≡1 [11], mais
212=4096=11×372+4, donc
212≡4 [11], alors que
21=2. On ne simplifie pas non plus :
3×7≡3×2 [15], car
21−6=15, mais
7≡2 [15] ; la simplification d'une congruence est étudiée en 2e année.
Méthode : reste d’une grande puissance
- Remplacer la base par son reste modulo n.
- Calculer les puissances successives jusqu'à un exposant k≥1 tel que ak≡1 [n] ou ak≡−1 [n]. Sinon, on repère directement le cycle des restes (exemple : 2k≡4 [6] pour tout k pair non nul).
- Diviser l'exposant par k : si N=kq+s avec 0≤s<k, alors aN=(ak)q×as≡as [n] si ak≡1 [n], et aN≡(−1)qas [n] si ak≡−1 [n].
Exemple 8 : reste d’une grande puissance dans la division par 11
Cherchons le reste de 1683 par 11. Comme 16≡5 [11], 1683≡583 [11]. Les puissances de 5 donnent 52=25≡3, 53≡3×5≡4, 54≡4×5≡9 et 55≡9×5=45≡1 [11]. Comme 83=5×16+3 :
1683≡(55)16×53≡1×125≡4 [11].Le reste est 4, car 125=11×11+4.
Méthode : démontrer une divisibilité pour tout entier naturel
Pour montrer que m∣An pour tout n∈N, on montre que An≡0 [m] en remplaçant chaque base par une puissance congrue à un entier simple (1 ou −1 souvent).
Exemple 9 : une divisibilité par 17 vraie pour tout n
Soit n∈N. On a 34=81=68+13≡−4 [17], donc 38≡16≡−1 [17], et 24=16≡−1 [17]. Donc
38n+224n+3=9×(38)n≡9(−1)n [17],=8×(24)n≡8(−1)n [17].En additionnant, 38n+2+24n+3≡17(−1)n≡0 [17] : 17 divise 38n+2+24n+3 pour tout n∈N.
L’ensemble Z/nZ et ses opérations
Classes modulo n et ensemble Z/nZ
Soit n≥2. La classe de a∈Z modulo n est l'ensemble défini en compréhension a={b∈Z / b≡a [n]}={a+kn / k∈Z}, et a=b⟺a≡b [n]. D'après la division euclidienne, chaque entier est congru à un seul des restes 0,1,…,n−1 : l'ensemble des classes modulo n est
Z/nZ={0;1;…;n−1},qui a exactement n éléments. Par exemple, dans Z/6Z, −47=1 et 20=2.
Addition et multiplication dans Z/nZ
On pose a+b=a+b et a×b=ab. Le résultat ne dépend pas des représentants choisis : si a=a′ et b=b′, la compatibilité donne a+b≡a′+b′ [n] et ab≡a′b′ [n]. Elles sont commutatives et associatives, × est distributive sur +, et 0, 1 sont les éléments neutres.
Exemple 10 : table de multiplication de Z/6Z et équations
Par exemple, 4×5=20=2. Pour résoudre une équation dans Z/nZ, on teste les n classes sur la table.
| × | 0 | 1 | 2 | 3 | 4 | 5 |
|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
L'équation 4x=2 : sur la ligne de 4, la valeur 2 apparaît dans les colonnes 2 et 5, donc x=2 ou x=5. L'équation 4x=1 n'a aucune solution, car 1 n'apparaît pas sur cette ligne. Retour dans Z : 4x≡2 [6]⟺x≡2 [6] ou x≡5 [6].
Attention : dans
Z/6Z, 2×3=0 alors qu'aucun des deux facteurs n'est nul : une équation produit ne s'y résout pas comme dans
R. Pages liées