Aller au contenu
OptiTAB

Maths Terminale · Chapitre 23 · Maths Expertes

Arithmétique

  • 9 parties
  • 6 schémas
  • Lecture ≈ 29 min
  • Conforme au programme
Objectifs

Raisonner sur les entiers : divisibilité, division euclidienne et congruences ; calculer un PGCD avec l'algorithme d'Euclide ; démontrer et utiliser les théorèmes de Bézout et de Gauss ; résoudre une congruence ax≡b(modn) et une équation ax+by=c en nombres entiers ; étudier les nombres premiers (décomposition, petit théorème de Fermat) et des problèmes de chiffrement. Programme de Maths expertes.

Prérequis

Calcul sur les entiers relatifs, puissances, raisonnement par récurrence.

IDivisibilité dans Z

DéfinitionDiviseur, multiple

Soient a et b deux entiers relatifs. On dit que b divise a s'il existe un entier relatif k tel que a=kb.

On note b∣a ; on dit aussi que b est un diviseur de a, ou que a est un multiple de b.

Exemple
  • −6∣42 car 42=(−7)×(−6).
  • 0 est un multiple de tout entier (0=0×b), mais 0 ne divise que 0.
  • Les diviseurs de 12 dans Z sont ±1, ±2, ±3, ±4, ±6 et ±12.
PropriétéRègles de calcul

Soient a, b, c des entiers relatifs.

  1. Si a∣b et b∣c, alors a∣c (transitivité).
  2. Si a∣b et a∣c, alors a divise toute combinaison bu+cv avec u,v∈Z ; en particulier a∣b+c et a∣b−c.
  3. Si a∣b et b≠0, alors |a|≤|b| : un entier non nul n'a qu'un nombre fini de diviseurs.
DémonstrationPoint 2

Si b=ka et c=k′a avec k,k′∈Z, alors bu+cv=a(ku+k′v), où ku+k′v est un entier : donc a∣bu+cv.

ExempleÉliminer n par une combinaison

Cherchons les entiers naturels n tels que n+1 divise n+5.

  • Si n+1∣n+5, comme n+1∣n+1, alors n+1 divise la différence (n+5)−(n+1)=4.
  • Réciproquement, si n+1∣4, alors n+1∣4+(n+1)=n+5.

Donc n+1∣n+5⟺n+1∣4. Comme n+1≥1, on a n+1∈{1,2,4}, soit n∈{0,1,3}.

MéthodeDéterminer les diviseurs d'un entier n≥2
  1. Tester les entiers d de 1 à n.
  2. Chaque diviseur d trouvé en donne un second, nd : les diviseurs vont par paires.
  3. Dans Z, ajouter les opposés.
ExempleDiviseurs de 90

90≈9,5 : on teste les entiers de 1 à 9. Les paires 1×90, 2×45, 3×30, 5×18, 6×15 et 9×10 donnent les 12 diviseurs positifs de 90 : 1,2,3,5,6,9,10,15,18,30,45,90.

AttentionLes diviseurs négatifs

Dans Z, un diviseur peut être négatif : pour trouver les entiers n tels que n−4∣21, il faut envisager n−4∈{−21,−7,−3,−1,1,3,7,21}.

IIDivision euclidienne

ThéorèmeDivision euclidienne

Soient a∈Z et b∈N∗. Il existe un unique couple d'entiers (q,r) tel que

a=bq+ret0≤r<b.

q est le quotient et r le reste de la division euclidienne de a par b.

Exemple
  • 742=16×46+6 : quotient 46, reste 6.
  • −17=4×(−5)+3 : quotient −5, reste 3. Sur la droite des entiers, −17 est situé 3 unités après le multiple 4×(−5)=−20.
Droite des entiers : -17 est situé 3 unités après le multiple 4 × (-5) = -20, d'où le reste 3
AttentionLe reste n'est jamais négatif

−17=4×(−4)−1 n'est pas l'écriture euclidienne : le reste doit vérifier 0≤r<4.

PropriétéConséquences
  • b∣a si et seulement si le reste de la division euclidienne de a par b est nul.
  • Les restes possibles dans la division par b sont 0,1,…,b−1 : tout entier s'écrit bq, bq+1, …, ou bq+(b−1). C'est la base des raisonnements par disjonction des cas.
DémonstrationUnicité (pour aller plus loin)

Si a=bq+r=bq′+r′ avec 0≤r<b et 0≤r′<b, alors b(q−q′)=r′−r. Or −b<r′−r<b, et le seul multiple de b strictement compris entre −b et b est 0. Donc r=r′, puis q=q′.

En Python, pour b>0, a // b et a % b donnent le quotient et le reste euclidiens, y compris pour a négatif :

Python
a, b = -17, 4
q, r = a // b, a % b
print(q, r)   # -5 3

IIICongruences dans Z

DéfinitionCongruence modulo n

Soit n un entier naturel, n≥2. Deux entiers a et b sont congrus modulo n lorsque n divise a−b. On note

a≡b(modn)oua≡b [n].
PropriétéCongruence et reste
  • a≡b(modn) si et seulement si a et b ont le même reste dans la division euclidienne par n.
  • Tout entier est congru modulo n à son reste r, avec 0≤r<n.
  • a≡0(modn) signifie que n divise a.
Exemple
  • 17≡2(mod5) car 17−2=15=5×3.
  • 11≡−3(mod7) : 11=7×1+4 et −3=7×(−1)+4 ont le même reste 4.
ThéorèmeCompatibilité avec les opérations

Soient n≥2 et a,b,c,d des entiers tels que a≡b(modn) et c≡d(modn). Alors :

  • a+c≡b+d(modn) et a−c≡b−d(modn) ;
  • ac≡bd(modn) ;
  • ak≡bk(modn) pour tout entier naturel k.
DémonstrationProduit et puissances

L'égalité ac−bd=a(c−d)+d(a−b) montre que ac−bd est une combinaison de c−d et a−b, tous deux multiples de n : donc n∣ac−bd. Pour les puissances, la règle du produit donne, par récurrence sur k : ak+1=ak×a≡bk×b=bk+1(modn).

AttentionOn ne divise pas une congruence

2×1≡2×4(mod6), mais 1≢4(mod6). Simplifier par un facteur n'est permis que sous condition (théorème de Gauss, partie V).

Reste d'une grande puissance

MéthodeRestes de ak modulo n
  1. Remplacer a par un entier plus simple qui lui est congru (son reste, ou un entier négatif comme −1).
  2. Calculer les restes de a1,a2,a3,… jusqu'à obtenir le reste 1 : si ap≡1(modn), les restes se répètent avec la période p.
  3. Diviser l'exposant par p : si k=pm+s, alors ak=(ap)m×as≡as(modn).
ExempleReste de 3100 dans la division par 7

Restes successifs : 31≡3, 32≡2, 33≡6, 34≡4, 35≡5 et 36≡1(mod7). Comme 100=6×16+4 :

3100=(36)16×34≡116×4(mod7)≡4(mod7)

Le reste de la division euclidienne de 3100 par 7 est 4 (en Python : pow(3, 100, 7) renvoie 4).

Cycle des restes des puissances de 3 modulo 7 : 1, 3, 2, 6, 4, 5, puis retour à 1, période 6

Raisonner par disjonction des cas

ExempleLes carrés modulo 4

Tout entier n est congru à 0, 1, 2 ou 3 modulo 4 :

Reste de n modulo 40123
Reste de n2 modulo 40101

Un carré est donc congru à 0 ou à 1 modulo 4, et une somme de deux carrés à 0, 1 ou 2, jamais à 3. Par exemple, 2027≡3(mod4) n'est pas une somme de deux carrés.

Critères de divisibilité

PropriétéDivisibilité par 9 et par 11

Soit N=ak×10k+⋯+a1×10+a0 un entier naturel de chiffres ak,…,a1,a0.

  • N≡a0+a1+⋯+ak(mod9) : N est divisible par 9 si et seulement si la somme de ses chiffres l'est (de même pour 3).
  • N≡a0−a1+a2−⋯+(−1)kak(mod11) : N est divisible par 11 si et seulement si la somme alternée de ses chiffres, à partir des unités, l'est.
Démonstration

10≡1(mod9), donc 10m≡1(mod9) pour tout entier naturel m ; en remplaçant chaque puissance de 10 dans N, on obtient N≡ak+⋯+a1+a0(mod9). De même, 10≡−1(mod11) donne 10m≡(−1)m(mod11).

Exemple
  • 7+3+2+6=18 est divisible par 9, donc 7326 aussi : 7326=9×814.
  • 1−3+3−1=0 est divisible par 11, donc 1331 aussi : 1331=11×121.

IVPGCD et algorithme d'Euclide

DéfinitionPGCD

Soient a et b deux entiers relatifs non tous deux nuls. Leurs diviseurs communs sont en nombre fini ; le plus grand d'entre eux est le plus grand commun diviseur de a et b, noté PGCD(a,b). C'est un entier naturel non nul.

Propriété
  • PGCD(a,b)=PGCD(b,a)=PGCD(|a|,|b|).
  • Si a≠0, PGCD(a,0)=|a| ; si b≠0 et b∣a, PGCD(a,b)=|b|.
PropriétéPropriété clé

Soient a, b, q, r des entiers avec b≠0 et a=bq+r. Les diviseurs communs de a et b sont exactement les diviseurs communs de b et r. En particulier, PGCD(a,b)=PGCD(b,r).

Démonstration

Si d∣a et d∣b, alors d divise la combinaison r=a−bq. Réciproquement, si d∣b et d∣r, alors d∣bq+r=a. Les deux couples ont les mêmes diviseurs communs, donc le même plus grand.

ThéorèmeAlgorithme d'Euclide

Soient a et b deux entiers naturels avec b≠0. On effectue les divisions euclidiennes successives

a=bq1+r1,0≤r1<bb=r1q2+r2,0≤r2<r1r1=r2q3+r3,0≤r3<r2

et ainsi de suite. Les restes forment une suite strictement décroissante d'entiers naturels : un reste nul apparaît après un nombre fini d'étapes. Le dernier reste non nul est PGCD(a,b) (si r1=0, le PGCD est b).

RemarquePourquoi ça marche

D'après la propriété clé, PGCD(a,b)=PGCD(b,r1)=PGCD(r1,r2)=⋯=PGCD(rk,0)=rk, où rk est le dernier reste non nul.

ExempleCalcul de PGCD(252,198)
Division euclidienneReste
252=198×1+5454
198=54×3+3636
54=36×1+1818
36=18×2+00

Le dernier reste non nul est 18 : PGCD(252,198)=18.

Rectangle 252 × 198 découpé en carrés de côtés 198, 54, 36 et 18 selon les divisions de l'algorithme d'Euclide ; PGCD(252, 198) = 18

Lecture géométrique : on découpe le rectangle de côtés 252 et 198 en carrés aussi grands que possible, à chaque étape. Le côté des derniers carrés, 18, est le PGCD : c'est le plus grand côté de carré qui pave exactement le rectangle.

PropriétéDiviseurs communs

Les diviseurs communs de a et b sont exactement les diviseurs de PGCD(a,b) : on l'obtient en suivant l'algorithme d'Euclide jusqu'au couple (rk,0).

Exemple

Les diviseurs communs positifs de 252 et 198 sont les diviseurs de 18 : 1,2,3,6,9,18.

Pour a et b entiers naturels, b≠0 (pgcd(252, 198) renvoie 18) :

Python
def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

VThéorèmes de Bézout et de Gauss

DéfinitionEntiers premiers entre eux

Deux entiers a et b, non tous deux nuls, sont premiers entre eux lorsque PGCD(a,b)=1 : leurs seuls diviseurs communs sont 1 et −1.

Exemple
  • 15 et 28 sont premiers entre eux, sans être des nombres premiers ; 12 et 18 ne le sont pas (PGCD(12,18)=6).
  • Deux entiers consécutifs n et n+1 sont toujours premiers entre eux : un diviseur commun divise (n+1)−n=1.
ThéorèmeIdentité de Bézout

Soient a et b deux entiers non tous deux nuls et d=PGCD(a,b). Il existe des entiers relatifs u et v tels que

au+bv=d.
DémonstrationÉcriture du PGCD sous la forme au+bv (au programme)

Soit E l'ensemble des entiers strictement positifs de la forme au+bv, avec u,v∈Z. E n'est pas vide : il contient a×a+b×b=a2+b2>0. Toute partie non vide de N admet un plus petit élément : notons m=au0+bv0 le plus petit élément de E.

  1. m divise a. Écrivons la division euclidienne a=mq+r, avec 0≤r<m. Alors r=a−(au0+bv0)q=a(1−qu0)+b(−qv0) est de la forme au+bv. Si r était strictement positif, il appartiendrait à E tout en étant strictement inférieur à m : impossible. Donc r=0 et m∣a. De même, m∣b.
  2. m=d. m est un diviseur commun positif de a et b, donc m≤d. Inversement, d divise a et b, donc la combinaison au0+bv0=m ; comme m>0, on a d≤m.

Ainsi d=m=au0+bv0.

ThéorèmeThéorème de Bézout

Deux entiers a et b sont premiers entre eux si et seulement s'il existe des entiers u et v tels que au+bv=1.

Démonstration

Si PGCD(a,b)=1, l'identité de Bézout fournit u et v. Réciproquement, si au+bv=1, tout diviseur commun positif de a et b divise au+bv=1 : il vaut 1.

MéthodeTrouver un couple de Bézout (algorithme d'Euclide étendu)
  1. Écrire l'algorithme d'Euclide.
  2. Partir de l'avant-dernière division et isoler le dernier reste non nul.
  3. Remonter les divisions en remplaçant chaque reste par son expression, jusqu'à n'avoir plus que a et b.
ExempleUn couple de Bézout pour 252 et 198

D'après les divisions du IV : 18=54−36, 36=198−54×3 et 54=252−198. Donc

18=54−(198−54×3)=54×4−198=(252−198)×4−198=252×4+198×(−5)

Le couple (4,−5) convient : 1008−990=18.

Version itérative de l'algorithme (pour a et b entiers naturels, b≠0) : à chaque étape, r0=au0+bv0 et r1=au1+bv1 ; bezout(252, 198) renvoie (18, 4, -5).

Python
def bezout(a, b):
    r0, u0, v0 = a, 1, 0
    r1, u1, v1 = b, 0, 1
    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q*r1
        u0, u1 = u1, u0 - q*u1
        v0, v1 = v1, v0 - q*v1
    return r0, u0, v0
ThéorèmeThéorème de Gauss

Soient a, b, c des entiers. Si a divise bc et si a et b sont premiers entre eux, alors a divise c.

Démonstration(au programme)

Comme PGCD(a,b)=1, le théorème de Bézout donne des entiers u et v tels que au+bv=1. En multipliant par c :

c=acu+bcv.

a divise acu ; a divise bc, donc bcv. Ainsi a divise la somme acu+bcv=c.

PropriétéCorollaire

Si a et b sont premiers entre eux et divisent tous les deux n, alors ab divise n.

Démonstration

n=ak avec k∈Z. Comme b∣ak et PGCD(b,a)=1, le théorème de Gauss donne b∣k : k=bk′, d'où n=abk′.

ExempleProduit de trois entiers consécutifs

Pour tout entier n, N=n(n+1)(n+2) est divisible par 6. En effet, parmi deux entiers consécutifs l'un est pair, donc 2∣N ; les restes de n, n+1 et n+2 modulo 3 sont 0, 1 et 2 dans un certain ordre, donc l'un des trois est multiple de 3 et 3∣N. Comme 2 et 3 sont premiers entre eux, 6∣N.

AttentionL'hypothèse « premiers entre eux » est indispensable

6 divise 4×3=12, mais 6 ne divise ni 4 ni 3 : ici PGCD(6,4)=2≠1.

VICongruences linéaires et équations diophantiennes

PropriétéInverse modulo n

Soient n≥2 et a un entier. Il existe un entier u tel que au≡1(modn) si et seulement si a et n sont premiers entre eux. Un tel u est un inverse de a modulo n.

Démonstration

au≡1(modn) équivaut à l'existence d'un entier v tel que au+nv=1 : c'est exactement le théorème de Bézout appliqué à a et n.

ExempleInverse de 3 modulo 7

7=3×2+1 donne 1=7−3×2, soit 3×(−2)≡1(mod7). Comme −2≡5(mod7), 5 est un inverse de 3 modulo 7 : vérification, 3×5=15=2×7+1.

MéthodeRésoudre ax≡b(modn)
  1. Calculer d=PGCD(a,n).
  2. Si d ne divise pas b : aucune solution (car ax−b=nk serait divisible par d).
  3. Si d=1 : multiplier les deux membres par un inverse u de a modulo n ; ax≡b(modn)⟺x≡ub(modn).
  4. Si d>1 et d∣b : diviser a, b et n par d (car n∣ax−b⟺nd∣adx−bd), puis appliquer le point 3. On obtient d solutions modulo n.
ExempleTrois cas
  • 3x≡2(mod7) : PGCD(3,7)=1 ; en multipliant par 5, x≡10≡3(mod7). Les solutions sont les entiers x=3+7k, k∈Z.
  • 6x≡4(mod10) : PGCD(6,10)=2 divise 4 ; on se ramène à 3x≡2(mod5), puis, 2 étant un inverse de 3 modulo 5, à x≡4(mod5). Modulo 10 : x≡4 ou x≡9(mod10).
  • 6x≡5(mod9) : PGCD(6,9)=3 ne divise pas 5 : aucune solution.
PropriétéÉquation ax+by=c

Soient a et b deux entiers non nuls et d=PGCD(a,b). L'équation ax+by=c admet des solutions entières si et seulement si d divise c.

Démonstration

Si ax+by=c, d divise a et b, donc c. Réciproquement, si c=dk, l'identité de Bézout au+bv=d multipliée par k donne la solution (uk,vk).

MéthodeRésoudre ax+by=c dans Z2
  1. Vérifier que d=PGCD(a,b) divise c, puis diviser l'équation par d : on se ramène au cas PGCD(a,b)=1.
  2. Trouver une solution particulière (x0,y0) (couple de Bézout, ou essai).
  3. Soustraire : a(x−x0)=−b(y−y0). Le théorème de Gauss donne b∣x−x0, d'où x=x0+bk puis y=y0−ak, avec k∈Z.
  4. Vérifier (réciproque) que ces couples sont bien solutions.
ExempleRésoudre 3x+5y=7
  • PGCD(3,5)=1 et 3×(−1)+5×2=7 : (−1,2) est une solution particulière.
  • Si 3x+5y=7, alors 3(x+1)=−5(y−2). 5 divise 3(x+1) et est premier avec 3, donc 5∣x+1 (Gauss) : x=−1+5k. En reportant, 15k=−5(y−2), soit y=2−3k.
  • Réciproquement, 3(−1+5k)+5(2−3k)=−3+15k+10−15k=7.

Les solutions sont les couples (−1+5k, 2−3k) avec k∈Z.

Attention

Ne pas oublier la réciproque, ni de diviser a, b et c par le PGCD avant d'appliquer Gauss : dans 12x+18y=30, on travaille sur 2x+3y=5.

VIINombres premiers

DéfinitionNombre premier

Un nombre premier est un entier naturel p≥2 dont les seuls diviseurs positifs sont 1 et p. Un entier n≥2 non premier est dit composé. L'entier 1 n'est pas premier.

Propriété
  1. Tout entier n≥2 admet au moins un diviseur premier : son plus petit diviseur d≥2.
  2. Si n≥2 est composé, il admet un diviseur premier p tel que p≤n.
  3. Si p est premier et ne divise pas a, alors a et p sont premiers entre eux.
Démonstration
  1. Si le plus petit diviseur d≥2 de n était composé, il aurait un diviseur d′ avec 1<d′<d, qui diviserait aussi n : contradiction.
  2. Si n=ab avec 2≤a≤b, alors a2≤ab=n, donc a≤n, et un diviseur premier de a convient.
  3. Les diviseurs positifs de p sont 1 et p ; p ne divise pas a, donc le seul diviseur commun positif est 1.
MéthodeÉtudier la primalité d'un entier n

Chercher un diviseur parmi les nombres premiers p≤n. S'il n'y en a aucun, n est premier.

Exemple

211≈14,5. Aucun des nombres premiers 2, 3, 5, 7, 11, 13 ne divise 211 (restes 1, 1, 1, 1, 2, 3) : 211 est premier.

ThéorèmeL'ensemble des nombres premiers est infini

Il existe une infinité de nombres premiers.

Démonstration(au programme)

Raisonnons par l'absurde : supposons qu'il n'existe qu'un nombre fini de nombres premiers p1,p2,…,pk. Posons

N=p1×p2×⋯×pk+1.

N≥2 admet un diviseur premier p, qui est l'un des pi. Alors p divise N et le produit p1×⋯×pk, donc leur différence 1 : impossible. Il existe donc une infinité de nombres premiers.

Remarque

N n'est pas forcément premier : 2×3×5×7×11×13+1=30031=59×509. Mais ses diviseurs premiers ne sont pas dans la liste de départ.

Crible d'Ératosthène

Pour obtenir les nombres premiers jusqu'à n : on écrit les entiers de 2 à n ; le premier entier non barré est premier, on barre tous ses multiples à partir de son carré ; on recommence tant que le carré du nombre retenu est inférieur ou égal à n. Jusqu'à 100, il suffit de barrer les multiples de 2, 3, 5 et 7 (car 112>100) : il reste les 25 nombres premiers inférieurs à 100.

Crible d'Ératosthène de 1 à 100 : les 25 nombres premiers sont mis en évidence en bleu
Python
def crible(n):
    est_p = [True] * (n + 1)
    est_p[0] = est_p[1] = False
    p = 2
    while p * p <= n:
        if est_p[p]:
            k = p * p
            while k <= n:
                est_p[k] = False
                k += p
        p += 1
    return [k for k in range(n+1)
            if est_p[k]]

Décomposition en produit de facteurs premiers

PropriétéUn premier qui divise un produit

Si un nombre premier p divise un produit ab, alors p divise a ou p divise b.

Démonstration

Si p ne divise pas a, alors a et p sont premiers entre eux ; comme p∣ab, le théorème de Gauss donne p∣b.

ThéorèmeDécomposition en facteurs premiers

Tout entier n≥2 s'écrit comme produit de nombres premiers :

n=p1α1×p2α2×⋯×pkαk,

où p1<p2<⋯<pk sont premiers et les exposants αi des entiers naturels non nuls. Cette écriture est unique.

DémonstrationIdée

Existence, par récurrence forte : si n est premier, c'est fini ; sinon n=ab avec 2≤a,b<n, et on décompose a et b. Unicité : si deux décompositions de n existaient, un premier de la première divise le produit de la seconde, donc l'un de ses facteurs (propriété précédente) ; on simplifie par ce premier et on recommence.

Exemple

On divise successivement par les plus petits nombres premiers possibles : 360=2×180=22×90=23×45=23×32×5.

Arbre de décomposition de 360 en facteurs premiers : 360 = 2 au cube × 3 au carré × 5
PropriétéDiviseurs d'un entier décomposé

Les diviseurs positifs de n=p1α1×⋯×pkαk sont les entiers p1β1×⋯×pkβk avec 0≤βi≤αi. Leur nombre est (α1+1)(α2+1)⋯(αk+1).

Exemple

360=23×32×5 a (3+1)(2+1)(1+1)=24 diviseurs positifs. Avec 84=22×3×7, on lit PGCD(360,84)=22×3=12 (plus petits exposants communs).

RemarquePour aller plus loin : le PPCM

Le plus petit multiple commun strictement positif de a et b s'obtient avec les plus grands exposants : PPCM(360,84)=23×32×5×7=2520. Pour a,b>0, on a PGCD(a,b)×PPCM(a,b)=ab : ici 12×2520=360×84=30240.

Pour n≥2, facteurs(360) renvoie [2, 2, 2, 3, 3, 5] :

Python
def facteurs(n):
    res, d = [], 2
    while d * d <= n:
        while n % d == 0:
            res.append(d)
            n //= d
        d += 1
    if n > 1:
        res.append(n)
    return res

VIIIPetit théorème de Fermat

ThéorèmePetit théorème de Fermat

Soit p un nombre premier.

  • Si a est un entier non divisible par p, alors ap−1≡1(modp).
  • Pour tout entier a, ap≡a(modp).
DémonstrationPour aller plus loin

Soit a non divisible par p. Les entiers a,2a,…,(p−1)a ne sont pas divisibles par p (propriété du VII), et ils ont des restes deux à deux distincts modulo p : si ia≡ja(modp), alors p∣(i−j)a, donc p∣i−j (Gauss), avec |i−j|<p, d'où i=j. Leurs restes sont donc 1,2,…,p−1 dans un certain ordre. En multipliant :

(p−1)!×ap−1≡(p−1)!(modp).

p divise (p−1)!(ap−1−1) et est premier avec (p−1)!, donc p∣ap−1−1. Enfin, ap≡a s'obtient en multipliant par a (et est évident si p∣a).

ExempleReste de 2100 dans la division par 13

13 est premier et ne divise pas 2 : 212≡1(mod13). Comme 100=12×8+4, 2100=(212)8×24≡16≡3(mod13).

AttentionLa réciproque est fausse

2340≡1(mod341) alors que 341=11×31 n'est pas premier. En revanche, si an−1≢1(modn) pour un entier a premier avec n, alors n est sûrement composé : c'est le principe des tests de primalité.

IXApplication : chiffrement

ExempleChiffrement affine

On numérote les lettres de A=0 à Z=25 et on chiffre la lettre x par le reste y de 7x+3 modulo 26. Par exemple, E (x=4) donne 7×4+3=31≡5 : E devient F.

Pour déchiffrer, on résout 7x≡y−3(mod26). Comme 7×15=105=4×26+1, 15 est un inverse de 7 modulo 26, d'où x≡15(y−3)(mod26). Pour y=5 : 15×2=30≡4, on retrouve E.

Schéma du chiffrement affine y ≡ 7x + 3 (mod 26) : la lettre E de rang 4 devient F de rang 5, et le déchiffrement x ≡ 15(y − 3) ramène F à E
Remarque

Le déchiffrement n'est possible que si le coefficient (7 ici) est premier avec 26. Le système RSA repose de même sur des calculs de puissances modulo n=pq et sur le petit théorème de Fermat.

À retenir
  • b∣a⟺a=kb ; division euclidienne a=bq+r avec 0≤r<b.
  • a≡b(modn)⟺n∣a−b : compatible avec +, × et les puissances, mais on ne divise pas.
  • Le dernier reste non nul de l'algorithme d'Euclide est le PGCD ; en remontant les divisions, on obtient au+bv=PGCD(a,b).
  • Bézout : PGCD(a,b)=1⟺au+bv=1. Gauss : a∣bc et PGCD(a,b)=1⇒a∣c.
  • Infinité des nombres premiers, décomposition unique, Fermat : ap−1≡1(modp) si p∤a.

Fiche de synthèse dans l'onglet Fiches !

Cours lu ? Continue avec :

Plateforme OptiTAB

S’entraîner jusqu’à maîtriser le programme de Terminale

Les 19 exercices corrigés de ce chapitre, le suivi de tes progrès et des révisions guidées.

Découvrir l’abonnement

Cours particuliers

Un prof de maths en Terminale, en ligne

Des séances individuelles avec un professeur, à distance, pour comprendre, combler ses lacunes et préparer les contrôles et le bac.

Réserver un cours particulier