Maths expertes

Arithmetique modulaire et nombres premiers

Les congruences permettent de calculer "modulo n", comme sur une horloge. Elles sont tres utiles pour simplifier les calculs et etudier les derniers chiffres d un nombre.

Version HTML statique du cours. Si JavaScript est actif, MathSups affiche l’expérience interactive avec QCM, exercices guidés et assistant IA.

Congruences

Les congruences permettent de calculer "modulo n", comme sur une horloge. Elles sont tres utiles pour simplifier les calculs et etudier les derniers chiffres d un nombre.

Congruence modulo n

Soit $n \ge 2$. On dit que deux entiers $a$ et $b$ sont congruents modulo n si leur difference est divisible par $n$.

On ecrit :

$$a \equiv b \ [n]$$

Par exemple, $17 \equiv 2 \ [5]$ car $17-2=15$ est divisible par 5.

Operations compatibles

Si $a \equiv b \ [n]$ et $c \equiv d \ [n]$, alors :

  • $a+c \equiv b+d \ [n]$
  • $ac \equiv bd \ [n]$
  • $a^k \equiv b^k \ [n]$ pour tout entier naturel $k$

On peut donc calculer modulo n a chaque etape.

On peut aussi soustraire membre a membre : si $$a \equiv b \ [n]$$ et $$c \equiv d \ [n],$$ alors $$a-c \equiv b-d \ [n].$$

Les puissances sont elles aussi compatibles : $$a \equiv b \ [n] \Rightarrow a^k \equiv b^k \ [n].$$ C est ce qui permet de reduire les calculs a chaque etape.

Exemple de calcul modulo 7

On veut calculer $5^{4}$ modulo 7.

On peut reduire a chaque etape :

$$5^2 = 25 \equiv 4 \ [7]$$

$$5^4 = (5^2)^2 \equiv 4^2 = 16 \equiv 2 \ [7]$$

Donc $5^4 \equiv 2 \ [7]$.

Lire une congruence comme un reste

Ecrire $$a \equiv b \ [n]$$ signifie que $a$ et $b$ donnent le meme reste dans la division par $n$.

Par exemple, $$23 \equiv 3 \ [5]$$ signifie simplement que 23 laisse le reste 3 quand on le divise par 5.

Cette lecture tres concrete permet de controler rapidement les derniers chiffres, les cycles de puissances et les tests de divisibilite.

Systeme de congruences simples

Quand deux modules sont premiers entre eux, on peut chercher un entier verifiant simultanement deux congruences, par exemple :

$$x\equiv a\ [m], \qquad x\equiv b\ [n].$$

La methode pratique consiste a parametrer une premiere congruence, puis a reinjecter dans la seconde. On obtient ainsi une solution unique modulo $$mn.$$ C est la version calculatoire du principe chinois des restes.

Inverse modulo n et equations ax = b

Quand un entier est premier avec n, il admet un inverse modulo n. Cela permet de resoudre des equations lineaires modulo n.

Inverse modulo n

Un entier $a$ admet un inverse modulo $n$ s'il existe un entier $u$ tel que :

$$au \equiv 1 \ [n].$$

Cela arrive exactement lorsque $\mathrm{PGCD}(a,n)=1$.

Resolution de $ax \equiv b \ [n]$

L equation $ax \equiv b \ [n]$ admet des solutions si et seulement si $\mathrm{PGCD}(a,n)$ divise $b$.

Si $\mathrm{PGCD}(a,n)=1$, on multiplie par l inverse de $a$ modulo n pour obtenir une solution unique modulo n.

Dans le cas general, si $$d=\mathrm{PGCD}(a,n),$$ alors l equation $$ax \equiv b \ [n]$$ admet des solutions si et seulement si $$d \mid b.$$ Quand cette condition est satisfaite, on commence par diviser l equation par $d$ avant de chercher un inverse.

Le nombre de classes de solutions depend alors du PGCD initial.

Utiliser Bezout pour trouver un inverse

On cherche des entiers $u$ et $v$ tels que :

$$au + nv = 1.$$

Alors $u$ est un inverse de $a$ modulo $n$.

Cette methode vient directement du theoreme de Bezout.

Exemple : resoudre $7x \equiv 3 \ [10]$

On cherche l inverse de 7 modulo 10.

On remarque que $7 \times 3 = 21 \equiv 1 \ [10]$, donc $3$ est l inverse de 7 modulo 10.

On multiplie alors par 3 :

$$x \equiv 9 \ [10].$$

Les solutions sont donc tous les entiers congrus a 9 modulo 10.

Nombres premiers

Les nombres premiers sont les blocs elementaires de l arithmetique. Ils interviennent dans la decomposition unique des entiers et dans de nombreux problemes de calcul modulaire.

Nombre premier

Un entier naturel $p \ge 2$ est premier si ses seuls diviseurs positifs sont 1 et lui-meme.

Exemples : 2, 3, 5, 7, 11, 13, ...

Infinitude des nombres premiers

Il existe une infinite de nombres premiers.

Idee classique : si l on suppose qu il n y en a qu un nombre fini, on considere leur produit augmente de 1. Ce nouveau nombre n est divisible par aucun des premiers listes, ce qui contredit l hypothese.

Decomposition en facteurs premiers

Tout entier naturel strictement superieur a 1 s ecrit de maniere unique comme produit de nombres premiers, a l ordre pres des facteurs.

Cette ecriture permet de lire rapidement les diviseurs, les PGCD et certaines congruences.

Exemple de decomposition

On a :

$$840 = 2^3 \times 3 \times 5 \times 7.$$

On en deduit facilement que 840 est divisible par 2, 3, 5 et 7, et que son PGCD avec un autre entier se calcule plus vite en utilisant ces facteurs.

Crible d Eratosthene

Pour lister les nombres premiers jusqu a un entier $$N,$$ on ecrit les entiers de $$2$$ a $$N$$, puis on barre successivement les multiples de $$2$$, puis de $$3$$, puis de chaque nouveau nombre non barre.

Les entiers qui restent non barres sont les nombres premiers inferieurs ou egaux a $$N$$.

C est une methode simple et tres utile pour explorer rapidement une liste de nombres premiers.

Petit theoreme de Fermat et applications

Le petit theoreme de Fermat est un outil tres utile pour faire des calculs modulo un nombre premier et pour verifier certains tests de divisibilite ou de codage simple.

Petit theoreme de Fermat

Si $p$ est premier et si $a$ n est pas divisible par $p$, alors :

$$a^{p-1} \equiv 1 \ [p].$$

On en deduit aussi :

$$a^p \equiv a \ [p].$$

Calculer une puissance modulo un premier

On reduit l exposant en utilisant Fermat puis on simplifie les puissances intermediaires modulo $p$.

Exemple de reflexe : pour calculer $3^{100} \ [7]$, on utilise $3^6 \equiv 1 \ [7]$ puisque 7 est premier et $3$ n est pas multiple de 7.

Tests de divisibilite et chiffrement simple

Les congruences servent a construire des tests de divisibilite et des codes simples.

Par exemple, dans un codage affine modulo 26, on associe a une lettre un nombre, puis on applique une transformation de la forme :

$$y \equiv ax + b \ [26].$$

Pour decoder, il faut inverser $a$ modulo 26.

Exemple de Fermat

Calculons le reste de $3^{100}$ dans la division par 7.

Comme 7 est premier et $3 \not\equiv 0 \ [7]$, on a :

$$3^6 \equiv 1 \ [7].$$

Or $100 = 96 + 4 = 16 \times 6 + 4$, donc :

$$3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 3^4 = 81 \equiv 4 \ [7].$$

Quand Fermat s applique

Le petit theoreme de Fermat demande que le modulo soit un nombre premier $p$ et que $a$ ne soit pas divisible par $p$.

On peut alors reduire un grand exposant modulo $p-1$ :

$$a^{k+(p-1)} \equiv a^k \ [p].$$

Si le modulo n est pas premier, il faut revenir a une reduction directe ou a un autre argument.

QCM du chapitre

  1. Question 1. On a $23 \equiv ? \ [5]$

    • A. 0
    • B. 1
    • C. 2
    • D. 3

    Réponse. D. 3

    Explication. Le reste de 23 dans la division par 5 est 3, donc $23 \equiv 3 \ [5]$.

  2. Question 2. Si $a \equiv b \ [n]$, alors :

    • A. a-b est divisible par n
    • B. a+b est nul
    • C. a est premier
    • D. b divise a

    Réponse. A. a-b est divisible par n

    Explication. C est la definition meme de la congruence modulo n.

  3. Question 3. Un entier a admet un inverse modulo n si et seulement si :

    • A. a est pair
    • B. $\mathrm{PGCD}(a,n)=1$
    • C. a > n
    • D. n est pair

    Réponse. B. $\mathrm{PGCD}(a,n)=1$

    Explication. L existence de l inverse modulo n est equivalente au fait que a et n soient premiers entre eux.

  4. Question 4. L equation $4x \equiv 2 \ [6]$ admet-elle des solutions ?

    • A. Oui
    • B. Non
    • C. Seulement si x = 0
    • D. Impossible a dire

    Réponse. A. Oui

    Explication. On a $\mathrm{PGCD}(4,6)=2$ et 2 divise 2, donc il y a des solutions.

  5. Question 5. Quel entier est premier ?

    • A. 21
    • B. 27
    • C. 29
    • D. 33

    Réponse. C. 29

    Explication. 29 n a pour diviseurs positifs que 1 et 29.

  6. Question 6. Si p est premier et $a \not\equiv 0 \ [p]$, alors :

    • A. $a^{p-1} \equiv 1 \ [p]$
    • B. $a^p \equiv 0 \ [p]$
    • C. $a^{p-1} \equiv 0 \ [p]$
    • D. $a \equiv 1 \ [p]$

    Réponse. A. $a^{p-1} \equiv 1 \ [p]$

    Explication. C est l enonce du petit theoreme de Fermat.

Exercices guidés

Exercice 1. Resoudre une congruence lineaire

Resoudre $9x \equiv 6 \ [15]$.

  1. Étape 1. Verifier la condition d existence.

    On calcule $\mathrm{PGCD}(9,15)=3$.

    Comme $3 \mid 6$, l equation admet des solutions.

  2. Étape 2. Simplifier l equation.

    On divise par 3 :

    $$3x \equiv 2 \ [5].$$

    L inverse de 3 modulo 5 est 2, car $3\times2=6 \equiv 1 \ [5]$.

  3. Étape 3. Conclure.

    On multiplie par 2 :

    $$x \equiv 4 \ [5].$$

    Les solutions sont donc tous les entiers congrus a 4 modulo 5.

Exercice 2. Utiliser Fermat pour un calcul rapide

Calculer le reste de $2^{50}$ dans la division par 13.

  1. Étape 1. Appliquer le petit theoreme de Fermat.

    Comme 13 est premier et $2$ n est pas divisible par 13, on a :

    $$2^{12} \equiv 1 \ [13].$$

  2. Étape 2. Reduire l exposant.

    On ecrit $50 = 48 + 2 = 4 \times 12 + 2$.

    Alors :

    $$2^{50} = (2^{12})^4 \times 2^2 \equiv 1^4 \times 4 \equiv 4 \ [13].$$

Exercice 3. Chercher un chiffre des unites avec les congruences

Determiner le chiffre des unites de $$7^{53}.$$
7^{53}\ [10]

  1. Étape 1. Travailler modulo 10.

    On calcule $$7^1\equiv7,$$ $$7^2\equiv9,$$ $$7^3\equiv3,$$ $$7^4\equiv1\ [10].$$
    7^4\equiv1\ [10]

  2. Étape 2. Utiliser la periodicite.

    Comme $$53=4\times13+1,$$ on a $$7^{53}=(7^4)^{13}\times7\equiv1^{13}\times7\equiv7\ [10].$$
    7^{53}\equiv7\ [10]

  3. Étape 3. Conclure.

    Le chiffre des unites de $$7^{53}$$ est donc $$7.$$

Exercice 4. Trouver un inverse modulo 26

Resoudre la congruence $$11x\equiv7\ [26].$$
11x\equiv7\ [26]

  1. Étape 1. Verifier que 11 est inversible modulo 26.

    Comme $$\mathrm{PGCD}(11,26)=1,$$ le nombre 11 admet un inverse modulo 26.

  2. Étape 2. Trouver cet inverse.

    Une relation de Bezout donne $$1=3\times26-7\times11,$$ donc $$-7$$, c est-a-dire $$19,$$ est un inverse de 11 modulo 26.
    11^{-1}\equiv19\ [26]

  3. Étape 3. Multiplier la congruence par cet inverse.

    On obtient $$x\equiv19\times7=133\equiv3\ [26].$$ Donc les solutions sont $$x=3+26k$$ avec $$k\in\mathbb Z.$$
    x\equiv3\ [26]

Exercice 5. Calculer une grande puissance modulo un premier

Calculer le reste de $$3^{100}$$ dans la division par $$17.$$
3^{100}\ [17]

  1. Étape 1. Appliquer le petit theoreme de Fermat.

    Comme 17 est premier et $$17\nmid3,$$ on a $$3^{16}\equiv1\ [17].$$

  2. Étape 2. Reduire l exposant.

    On ecrit $$100=6\times16+4,$$ donc $$3^{100}\equiv(3^{16})^6\times3^4\equiv3^4\ [17].$$

  3. Étape 3. Finir le calcul.

    On calcule $$3^4=81\equiv13\ [17].$$ Le reste cherche est donc $$13.$$
    3^{100}\equiv13\ [17]