Deux entiers relatifs a et b sont premiers entre eux si a∧b=1. Le théorème de Bézout dit que c'est le cas si et seulement s'il existe u,v∈Z tels que au+bv=1. Le théorème de Gauss en déduit : si a∣bc et a∧b=1, alors a∣c. Le petit théorème de Fermat donne, pour p premier ne divisant pas a, ap−1≡1 [p]. Exemple : 9×4−7×5=1, donc 9 et 7 sont premiers entre eux ; si 9 divise 7c, alors 9 divise c.
Chapitre du semestre 2 de la 2e année du baccalauréat sciences mathématiques (option française), seule filière qui l'étudie. À la fin du chapitre, on sait calculer des coefficients de Bézout, résoudre ax+by=c et une congruence linéaire, utiliser Fermat pour une grande puissance et écrire un entier dans une base donnée.
Rappels de 1 bac SM : divisibilité, PGCD et congruences
Le chapitre s'appuie sur l'arithmétique dans Z de 1re année, résumée dans son tableau de cours : division euclidienne, nombres premiers (leur ensemble est infini) et existence de la décomposition, PGCD comme dernier reste non nul de l'algorithme d'Euclide. On utilise aussi (ka)∧(kb)=k(a∧b) pour k∈N∗, (a∧b)(a∨b)=∣ab∣, les congruences modulo n et leur compatibilité avec +, × et les puissances, et l'ensemble Z/nZ. Tout ce qui suit est nouveau.
Nombres premiers entre eux et théorème de Bézout
Entiers premiers entre eux
Soient a et b deux entiers relatifs non tous les deux nuls. Ils sont premiers entre eux si a∧b=1, c'est-à-dire si leurs seuls diviseurs communs sont 1 et −1. Par exemple 49=72 et 30=2×3×5 n'ont aucun facteur premier commun : 49∧30=1. Deux nombres premiers distincts sont toujours premiers entre eux.
Caractérisation du PGCD
Soient a,b∈Z∗ et d∈N∗. Alors a∧b=d si et seulement s'il existe α,β∈Z tels que a=dα, b=dβ et α∧β=1.
Démonstration : caractérisation du PGCD
Si a∧b=d, d divise a et b : a=dα et b=dβ. La propriété (ka)∧(kb)=k(a∧b) donne d=(dα)∧(dβ)=d(α∧β), donc α∧β=1. Réciproquement, si a=dα, b=dβ et α∧β=1, alors a∧b=d(α∧β)=d.
Identité et théorème de Bézout
- Identité de Bézout : si a et b sont deux entiers non tous les deux nuls, il existe u,v∈Z tels que au+bv=a∧b.
- Théorème de Bézout : a∧b=1 si et seulement s'il existe u,v∈Z tels que au+bv=1.
Démonstration : identité et théorème de Bézout
L'ensemble E des entiers strictement positifs de la forme au+bv contient a2+b2, donc il a un plus petit élément m=au0+bv0. Divisons a par m : a=mq+r avec 0≤r<m. Alors r=a(1−qu0)+b(−qv0) est de la même forme ; s'il était strictement positif, il serait dans E et plus petit que m. Donc r=0 et m∣a ; de même m∣b, d'où m≤a∧b. Inversement, a∧b divise a et b, donc il divise au0+bv0=m, et a∧b≤m. Ainsi m=a∧b.
Pour le théorème : si a∧b=1, l'identité donne u et v. Réciproquement, si au+bv=1, tout diviseur commun de a et b divise 1, donc a∧b=1.
Méthode : coefficients de Bézout par l’algorithme d’Euclide
On écrit les divisions de l'algorithme d'Euclide, puis on remonte (c'est l'algorithme d'Euclide étendu) : on exprime le dernier reste non nul à partir de l'avant-dernière division, et l'on remplace chaque reste par son expression tirée de la division précédente, jusqu'à ne garder que a et b.
Exemple 1 : coefficients de Bézout de 161 et 72
1617217=72×2+17=17×4+4=4×4+1Le dernier reste non nul est 1 : 161∧72=1. On remonte :
1=17−4×4=17−4(72−4×17)=17×17−4×72=17(161−2×72)−4×72=161×17−72×38.Contrôle : 161×17=2737 et 72×38=2736. Le couple (u;v)=(17;−38) convient.
Attention : une égalité
au+bv=d avec
d≥2 ne prouve pas que
d=a∧b ; elle prouve seulement que
a∧b divise
d. Par exemple
6×3−7×2=4, alors que
6∧7=1. Seul le cas
d=1 conclut.
Théorème de Gauss et décomposition en facteurs premiers
Théorème de Gauss
Soient a, b, c des entiers relatifs, avec a=0. Si a divise bc et si a∧b=1, alors a divise c.
Démonstration : théorème de Gauss
Comme a∧b=1, Bézout donne u,v tels que au+bv=1. En multipliant par c : c=a(cu)+(bc)v. Or a divise a(cu) et bc, donc il divise la combinaison c.
Exemple 2 : une équation homogène
Résolvons 21x=16y dans Z2. Si (x;y) est solution, 16 divise 21x et 16∧21=1 (16=24, 21=3×7) : par Gauss, 16 divise x, soit x=16k avec k∈Z. Alors 21×16k=16y donne y=21k. Réciproquement, 21×16k=16×21k. Les solutions sont les couples (16k;21k), k∈Z.
Attention : sans l'hypothèse
a∧b=1, la conclusion est fausse : 6 divise
4×9=36, mais 6 ne divise ni 4 ni 9.
Conséquences : produit de diviseurs et lemme d’Euclide
- Si a∣c, b∣c et a∧b=1, alors ab∣c.
- Lemme d'Euclide : si un nombre premier p divise ab, alors p∣a ou p∣b. En effet, si p∤a, alors p∧a=1 (les diviseurs positifs de p sont 1 et p), et Gauss donne p∣b. En 1re année, ce lemme se déduisait de l'unicité de la décomposition, alors admise ; ici, il découle de Bézout et de Gauss, sans utiliser cette unicité, ce qui permet ensuite de la démontrer.
- Si a∧b=1 et a∧c=1, alors a∧bc=1 : en multipliant au+bv=1 par au′+cv′=1, on obtient a(uau′+ucv′+bvu′)+bc(vv′)=1. Par récurrence, a∧b=1⇒am∧bk=1 pour m,k∈N∗.
Démonstration : produit de deux diviseurs premiers entre eux
Écrivons c=ak avec k∈Z. Alors b divise ak et b∧a=1 : par Gauss, b∣k, soit k=bk′. Donc c=abk′ et ab∣c.
Exemple 3 : un produit toujours divisible par 6
Soit n∈Z et A=n(n+1)(2n+1). Parmi n et n+1, l'un est pair : 2∣A. Selon le reste de n par 3 : si n=3q, 3∣n ; si n=3q+1, 2n+1=3(2q+1) ; si n=3q+2, n+1=3(q+1). Donc 3∣A. Comme 2∧3=1, on conclut 6∣A.
Théorème fondamental de l’arithmétique
Tout entier n≥2 s'écrit comme un produit de nombres premiers, et cette écriture est unique à l'ordre des facteurs près : c'est le théorème fondamental de l'arithmétique. L'existence a été vue en 1re année ; l'unicité, admise alors, se démontre maintenant avec le lemme d'Euclide.
Démonstration : unicité dans le théorème fondamental de l’arithmétique
Raisonnons par l'absurde : soit n le plus petit entier ayant deux décompositions différentes n=p1p2⋯pr=q1q2⋯qs. Le premier p1 divise q1(q2⋯qs) ; en appliquant le lemme d'Euclide autant de fois que nécessaire, il divise l'un des qj, qui est premier, donc p1=qj. Si p1n=1, les deux produits restants valent 1, donc sont vides (un produit non vide de nombres premiers vaut au moins 2), et les deux décompositions étaient égales. Sinon 2≤p1n<n, et retirer le facteur commun p1=qj donne deux décompositions différentes de p1n : cela contredit le choix de n.
Équations diophantiennes du premier degré à deux inconnues
Condition d’existence et ensemble des solutions
Soient a,b∈Z∗, c∈Z, d=a∧b, a=dα et b=dβ. On considère (E) : ax+by=c, d'inconnue (x;y)∈Z2.
- (E) a des solutions si et seulement si d divise c.
- Si (x0;y0) est une solution, les solutions sont les couples (x0+βk;y0−αk), k∈Z.
Démonstration : condition d’existence et solutions
Si (E) a une solution, d divise ax+by=c. Réciproquement, si c=dm, l'identité de Bézout au+bv=d donne la solution (um;vm). Soit ensuite (x0;y0) une solution. Pour (x;y) solution, par différence, a(x−x0)=−b(y−y0), puis, en divisant par d, α(x−x0)=−β(y−y0). Donc β divise α(x−x0) ; comme α∧β=1, Gauss donne x−x0=βk, puis αβk=−β(y−y0) et y=y0−αk (β=0). Réciproquement, a(x0+βk)+b(y0−αk)=c+dαβk−dβαk=c.
Méthode : résoudre une équation diophantienne en trois étapes
- Calculer d=a∧b : si d∤c, il n'y a aucune solution ; sinon, diviser l'équation par d.
- Trouver une solution particulière (évidente, ou par les coefficients de Bézout multipliés par dc).
- Soustraire, appliquer Gauss avec les coefficients simplifiés, vérifier la réciproque.
Exemple 4 : une équation à simplifier, puis une équation sans solution
Soit 322x+144y=10. On a 322∧144=2 et 2 divise 10 : on divise par 2, 161x+72y=5. L'exemple 1 donne 161×17+72×(−38)=1, donc (85;−190) est solution ; on prend plus simplement (85−72;−190+161)=(13;−29) : 2093−2088=5. Si (x;y) est solution, 161(x−13)=−72(y+29) ; 72 divise 161(x−13) et 72∧161=1, donc x=13+72k, puis y=−29−161k. Les solutions sont les couples (13+72k;−29−161k), k∈Z.
En revanche, 322x+144y=7 n'a aucune solution : le membre de gauche est toujours pair.
Attention : dans la solution générale, on utilise
βk et
−αk, coefficients divisés par
d. Garder
144k et
−322k ferait perdre une solution sur deux.
Méthode : système de deux congruences
Pour x≡r [m] et x≡s [m′], on écrit x=r+mk=s+m′k′ : le couple (k;k′) vérifie mk−m′k′=s−r. Si m∧m′=1, une solution x1 étant trouvée, x est solution si et seulement si m et m′ divisent x−x1, c'est-à-dire x≡x1 [mm′].
Exemple 5 : un système de deux congruences
Résolvons x≡2 [7] et x≡6 [9]. On cherche x=2+7k avec 2+7k≡6 [9], soit 7k≡4 [9]. Comme 7×4=28≡1 [9], on multiplie par 4 : k≡16≡7 [9]. Pour k=7, x1=51 : 51=7×7+2=9×5+6. Comme 7∧9=1, les solutions sont les entiers x≡51 [63].
Simplification des congruences et ensemble Z/pZ
Simplification d’une congruence
Soient n≥2, a,b∈Z, c∈Z∗ et δ=c∧n. Alors ac≡bc [n] si et seulement si a≡b [δn]. En particulier, si c∧n=1, on peut simplifier par c sans changer le module. Si δ=n, c'est-à-dire si n∣c, les deux membres ac et bc sont congrus à 0 et la congruence ac≡bc [n] est vraie pour tous a et b.
Démonstration : simplification d’une congruence
Écrivons n=δn′ et c=δc′, avec c′∧n′=1 par la caractérisation du PGCD. Si n∣c(a−b), alors δn′k=δc′(a−b), donc n′∣c′(a−b), et Gauss donne n′∣a−b. Réciproquement, si a−b=n′j, alors c(a−b)=c′jδn′=c′jn.
Attention : on divise aussi le module.
10×3≡10×7 [8], car
70−30=40, mais
3≡7 [8] ; ici
10∧8=2 et l'on obtient seulement
3≡7 [4]. Résoudre une congruence linéaire
Soient n≥2, a∈Z∗, b∈Z et δ=a∧n. L'équation ax≡b [n] équivaut à l'existence de y∈Z tel que ax+ny=b : elle a des solutions si et seulement si δ∣b. On simplifie alors par δ, puis on multiplie par un entier a′ tel que δaa′≡1 [δn] : il existe par Bézout, car δa∧δn=1 (caractérisation du PGCD), et l'on revient en arrière en multipliant par δa, donc chaque étape est une équivalence.
Exemple 6 : une congruence linéaire modulo 24
Soit 14x≡10 [24]. Ici 14∧24=2, qui divise 10 : on simplifie par 2, 7x≡5 [12]. Comme 7×7=49≡1 [12], on multiplie par 7 : x≡35≡11 [12]. Contrôle : 14×11=154=6×24+10. Modulo 24, les solutions sont x≡11 et x≡23.
Classes inversibles de Z/nZ et ensemble Z/pZ
- Soit n≥2. La classe a admet un inverse dans Z/nZ, c'est-à-dire une classe a′ telle que a×a′=1, si et seulement si a∧n=1.
- Si p est premier, toute classe non nulle de Z/pZ est inversible ; par suite, x×y=0 entraîne x=0 ou y=0.
Démonstration : classes inversibles
a×a′=1 signifie aa′≡1 [n], c'est-à-dire aa′+nk=1 pour un k∈Z. Par le théorème de Bézout, un tel couple (a′;k) existe si et seulement si a∧n=1. Si p est premier et a=0, alors p∤a, donc a∧p=1. Enfin, si xy=0 avec x=0, on multiplie par l'inverse de x : y=0.
Exemple 7 : inverse de la classe de 7 dans Z/19Z
19 est premier, donc 7 est inversible. Euclide donne 19=7×2+5, 7=5×1+2, 5=2×2+1, puis 1=5−2×2=3×5−2×7=3×19−8×7. Donc 7×(−8)≡1 [19] et l'inverse de 7 est −8=11 (77=4×19+1). L'équation 7x+2=6 équivaut à 7x=4, soit x=11×4=44=6.
Petit théorème de Fermat
Énoncé du petit théorème de Fermat
Soit p un nombre premier.
- Pour tout entier a non divisible par p, ap−1≡1 [p].
- Pour tout entier a, ap≡a [p].
Démonstration : petit théorème de Fermat
Soit a non divisible par p. Les classes 1a, 2a, …, p−1a sont non nulles (produit de deux classes non nulles de Z/pZ) et deux à deux distinctes : si ia=ja, on multiplie par l'inverse de a et i=j. Ce sont donc les p−1 classes non nulles, dans un autre ordre, et leurs produits sont égaux :
(p−1)!×ap−1≡(p−1)! [p].Aucun des facteurs 1,…,p−1 n'est divisible par p, donc, par le lemme d'Euclide, (p−1)!∧p=1 : on simplifie, ap−1≡1 [p]. En multipliant par a, ap≡a [p] ; si p∣a, les deux membres sont congrus à 0.
Exemple 8 : reste d’une grande puissance par Fermat
Cherchons le reste de 52026 par 13. 13 est premier et ne divise pas 5, donc 512≡1 [13]. Comme 2026=12×168+10 :
52026=(512)168×510≡510=(52)5 [13].Or 52=25≡−1 [13], donc 52026≡(−1)5≡12 [13] : le reste est 12.
Attention : la réciproque est fausse.
42=16≡1 [15], donc
414=(42)7≡1 [15], alors que 15 n'est pas premier. Et Fermat ne s'applique pas si
p∣a : 2612≡0 [13]. Systèmes de numération et critères de divisibilité
Écriture d’un entier en base b
Soit b≥2 un entier. Tout entier N≥1 s'écrit de manière unique N=akbk+ak−1bk−1+⋯+a1b+a0, avec des chiffres ai∈{0;1;…;b−1} et ak=0. On note N=akak−1⋯a0(b). En base 16, les chiffres 10 à 15 s'écrivent A, B, C, D, E, F.
Démonstration : existence et unicité de l’écriture en base b
Existence : on divise N par b, N=bq0+a0, puis q0=bq1+a1, et ainsi de suite. Les quotients sont des entiers naturels strictement décroissants tant qu'ils ne sont pas nuls, donc l'un d'eux est nul ; en remplaçant chaque quotient, on obtient l'écriture. Unicité, par récurrence forte sur N : dans toute écriture, N=b(akbk−1+⋯+a1)+a0 avec 0≤a0<b, donc, par unicité de la division euclidienne, a0 est le reste et akbk−1+⋯+a1 le quotient q de N par b. Si q=0, l'écriture se réduit à a0 ; sinon ak⋯a1(b) est une écriture de q<N, unique par hypothèse de récurrence.
Exemple 9 : écrire 1517 en base 5 et en base 16
151730360122=5×303+2=5×60+3=5×12+0=5×2+2=5×0+2On lit les restes de bas en haut : 1517=22032(5). Contrôle : 2×625+2×125+3×5+2=1517. En base 16, 1517=16×94+13 et 94=16×5+14, donc 1517=5ED(16).
Méthode : addition et multiplication en base b
On pose l'opération comme en base 10, colonne par colonne depuis la droite : dès qu'un résultat r atteint b, on écrit le reste de r par b et l'on retient le quotient. Pour comparer deux entiers écrits en base b, celui qui a le plus de chiffres est le plus grand ; à nombre égal de chiffres, on compare de gauche à droite.
Exemple 10 : opérations en base 6
2453(6)+1354(6) : 3+4=7=6+1, on écrit 1 et l'on retient 1 ; 5+5+1=11=6+5, on écrit 5, retenue 1 ; 4+3+1=8=6+2, on écrit 2, retenue 1 ; 2+1+1=4. Résultat 4251(6). Contrôle en base 10 : 609+358=967=4×216+2×36+5×6+1. De même, 45(6)×3(6) : 5×3=15=2×6+3, on écrit 3, retenue 2 ; 4×3+2=14=2×6+2. Résultat 223(6), soit 29×3=87.
Critères de divisibilité par les congruences
Soit N=ak⋯a1a0(10). Les critères de divisibilité du tronc commun se démontrent par les congruences : comme 10≡1 [9], 10≡−1 [11] et 100≡0 [4], la compatibilité avec les puissances donne :
NNN≡ak+⋯+a1+a0 [9],≡a0−a1+a2−…+(−1)kak [11],≡a1a0(10) [4].Comme m∣N⟺N≡0 [m], N est divisible par 9 si et seulement si la somme de ses chiffres l'est (de même pour 3, car 10≡1 [3]). Il est divisible par 11 si et seulement si sa somme alternée l'est, et par 4 si et seulement si le nombre formé par ses deux derniers chiffres l'est. De même, 100≡0 [25] et 10≡0 [5].
Exemple 11 : divisibilité de 73 854 par 9 et par 11
Somme des chiffres : 7+3+8+5+4=27, multiple de 9. Somme alternée depuis les unités : 4−5+8−3+7=11, multiple de 11. Donc 9 et 11 divisent 73 854 ; comme 9∧11=1, 99 le divise aussi : 73854=99×746.
Pages liées