Arithmétique

Cours complet · mathématiques expertes (terminale), chapitre 3 · terminale, option mathématiques expertes

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

L'arithmétique est l'étude des nombres entiers. Domaine parmi les plus anciens des mathématiques (Euclide, vers 300 av. J.-C.), elle connaît depuis un demi-siècle des applications spectaculaires : cryptographie (RSA), codes correcteurs, clés de contrôle. Ce chapitre présente la divisibilité, les congruences, le PGCD et les théorèmes de Bézout et de Gauss, puis les nombres premiers.

3.1 Divisibilité et Division Euclidienne

3.1.1 Divisibilité dans $Z$

Définition 3.1Divisibilité

Soient $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ (ou que $a$ est un multiple de $b$ ), et on note $b ∣ a$ , s'il existe un entier $k \in Z$ tel que :

$a = k b$

Proposition 3.2Propriétés de la divisibilité

Soient $a$ , $b$ , $c$ des entiers relatifs.

Si $c ∣ b$ et $b ∣ a$ , alors $c ∣ a$ (transitivité).
Si $c ∣ a$ et $c ∣ b$ , alors $c$ divise toute combinaison linéaire $a u + b v$ ( $u, v \in Z$ ) — en particulier $a + b$ et $a - b$ .
Si $b ∣ a$ et $a \neq = 0$ , alors $∣ b ∣ \leq ∣ a ∣$ : un entier non nul n'a qu'un nombre fini de diviseurs.

3.1.2 Division euclidienne

◆Théorème 3.3Division euclidienne

Soient $a \in Z$ et $b \in N^{*}$ . Il existe un unique couple $(q, r)$ d'entiers tels que :

$a = b q + r avec 0 \leq r < b$

L'entier $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$ .

Exemple 3.4

$47 = 9 \times 5 + 2$ (quotient $9$ , reste $2$ ) ; pour un négatif : $- 47 = 5 \times (- 10) + 3$ (le reste doit rester dans $[0, 5 [$ : $q = - 10$ , $r = 3$ ).

3.2 Congruences

Définition 3.5Congruence modulo

n

Soit $n \in N^{*}$ . Deux entiers $a$ et $b$ sont congrus modulo $n$ , ce que l'on note

$a \equiv b (mod n)$

si $n$ divise $a - b$ — de façon équivalente, si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .

Proposition 3.6Compatibilité avec les opérations

Soit $n \in N^{*}$ . Si $a \equiv b (mod n)$ et $c \equiv d (mod n)$ , alors :

$a + c \equiv b + d (mod n), a - c \equiv b - d (mod n), a c \equiv b d (mod n)$

et pour tout entier $k \geq 1$ : $a^{k} \equiv b^{k} (mod n)$ .

Démonstration (— compatibilité avec le produit)

Par hypothèse, $a - b = λn$ et $c - d = μ n$ avec $λ, μ \in Z$ . Alors :

$a c - b d = a c - b c + b c - b d = c (a - b) + b (c - d) = (c λ + b μ) n$

donc $n ∣ a c - b d$ . La compatibilité avec les puissances s'en déduit par récurrence.

Exemple 3.7Le reste d'une grande puissance

Quel est le reste de $7^{100}$ modulo $10$ (c'est-à-dire son chiffre des unités) ? On calcule les premières puissances modulo 10 : $7^{1} \equiv 7$ , $7^{2} = 49 \equiv 9$ , $7^{3} \equiv 63 \equiv 3$ , $7^{4} \equiv 21 \equiv 1 (mod 10)$ . Comme $7^{4} \equiv 1$ , on écrit $100 = 4 \times 25$ :

$7^{100} = (7^{4})^{25} \equiv 1^{25} \equiv 1 (mod 10)$

Le chiffre des unités de $7^{100}$ est $1$ .

3.3 PGCD, Théorèmes de Bézout et de Gauss

3.3.1 PGCD et algorithme d'Euclide

Définition 3.8PGCD

Soient $a$ et $b$ deux entiers non tous deux nuls. Le PGCD de $a$ et $b$ , noté $pgcd (a, b)$ , est le plus grand entier positif qui divise à la fois $a$ et $b$ . Deux entiers sont dits premiers entre eux si $pgcd (a, b) = 1$ .

Proposition 3.9Lemme d'Euclide

Si $a = b q + r$ (division euclidienne), alors :

$pgcd (a, b) = pgcd (b, r)$

En effet, tout diviseur commun de $a$ et $b$ divise $r = a - b q$ , et tout diviseur commun de $b$ et $r$ divise $a = b q + r$ : les couples $(a, b)$ et $(b, r)$ ont les mêmes diviseurs communs.

Méthode : Algorithme d'Euclide

Pour calculer $pgcd (a, b)$ ( $a > b > 0$ ) : on remplace $(a, b)$ par $(b, r)$ où $r$ est le reste de la division de $a$ par $b$ , et on recommence jusqu'à obtenir un reste nul. Le PGCD est le dernier reste non nul.

Exemple 3.10PGCD par l'algorithme d'Euclide

Calculons $pgcd (252, 198)$ :

$252 = 198 \times 1 + 54, 198 = 54 \times 3 + 36, 54 = 36 \times 1 + 18, 36 = 18 \times 2 + 0$

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

3.3.2 Théorème de Bézout

◆Théorème 3.11Identité de Bézout

Soient $a$ et $b$ deux entiers non tous deux nuls et $d = pgcd (a, b)$ . Alors il existe des entiers $x$ et $y$ tels que :

$a x + b y = d$

Démonstration ((exigible) — écriture du PGCD sous la forme

a x + b y

)

Considérons l'ensemble $E$ des entiers strictement positifs de la forme $a u + b v$ ( $u, v \in Z$ ). Cet ensemble est non vide (il contient $∣ a ∣$ ou $∣ b ∣$ ), donc admet un plus petit élément $d_{0} = a x + b y$ .

$d_{0}$ divise $a$ : la division euclidienne de $a$ par $d_{0}$ s'écrit $a = d_{0} q + r$ avec $0 \leq r < d_{0}$ . Alors :

$r = a - d_{0} q = a - (a x + b y) q = a (1 - x q) + b (- y q)$

est de la forme $a u + b v$ . Si $r > 0$ , alors $r \in E$ et $r < d_{0}$ , ce qui contredit la minimalité de $d_{0}$ . Donc $r = 0$ et $d_{0} ∣ a$ . De même, $d_{0} ∣ b$ .

$d_{0}$ est le plus grand diviseur commun : tout diviseur commun $c$ de $a$ et $b$ divise la combinaison linéaire $a x + b y = d_{0}$ , donc $c \leq d_{0}$ .

Ainsi $d_{0} = pgcd (a, b)$ , qui s'écrit bien sous la forme $a x + b y$ .

◆Théorème 3.12Théorème de Bézout

Deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $x$ et $y$ tels que :

$a x + b y = 1$

Démonstration

Si $pgcd (a, b) = 1$ , l'identité de Bézout fournit $x$ et $y$ . Réciproquement, si $a x + b y = 1$ , tout diviseur commun de $a$ et $b$ divise $1$ , donc $pgcd (a, b) = 1$ .

Méthode : Trouver un couple de Bézout (algorithme d'Euclide étendu)

On « remonte » l'algorithme d'Euclide. Pour $pgcd (252, 198) = 18$ :

$18 = 54 - 36 = 54 - (198 - 54 \times 3) = 4 \times 54 - 198 = 4 \times (252 - 198) - 198 = 4 \times 252 - 5 \times 198$

D'où le couple $(x, y) = (4, - 5)$ : $252 \times 4 + 198 \times (- 5) = 18$ .

3.3.3 Théorème de Gauss

◆Théorème 3.13Théorème de Gauss

Soient $a$ , $b$ , $c$ des entiers. Si $a$ divise le produit $b c$ et si $a$ est premier avec $b$ , alors $a$ divise $c$ :

$(a ∣ b c et pgcd (a, b) = 1) ⟹ a ∣ c$

Démonstration ((exigible))

Comme $pgcd (a, b) = 1$ , le théorème de Bézout donne des entiers $x$ et $y$ tels que $a x + b y = 1$ . Multiplions par $c$ :

$a c x + b cy = c$

Or $a$ divise $a c x$ (évident) et $a$ divise $b cy$ (car $a ∣ b c$ par hypothèse). Donc $a$ divise la somme, c'est-à-dire $a ∣ c$ .

Proposition 3.14Inverse modulo

n

et équation

a x \equiv b (mod n)

Si $pgcd (a, n) = 1$ , alors $a$ admet un inverse modulo $n$ : il existe $u \in Z$ tel que $a u \equiv 1 (mod n)$ (le coefficient $u$ d'une relation de Bézout $a u + n v = 1$ convient). L'équation $a x \equiv b (mod n)$ a alors pour solutions $x \equiv u b (mod n)$ .

3.4 Nombres Premiers

Définition 3.15Nombre premier

Un entier naturel $p \geq 2$ est premier si ses seuls diviseurs positifs sont $1$ et $p$ . Les premiers nombres premiers : $2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$

Proposition 3.16Critère d'arrêt

Tout entier $n \geq 2$ admet un diviseur premier. Si $n$ n'est pas premier, il admet un diviseur premier $p \leq n$ — pour tester la primalité de $n$ , il suffit donc d'essayer les diviseurs premiers jusqu'à $n$ .

◆Théorème 3.17Infinité des nombres premiers

L'ensemble des nombres premiers est infini.

Démonstration ((exigible) — Euclide)

Raisonnons par l'absurde : supposons qu'il n'existe qu'un nombre fini de nombres premiers, notés $p_{1}, p_{2}, \dots, p_{k}$ . Considérons :

$N = p_{1} p_{2} \dots p_{k} + 1$

L'entier $N \geq 2$ admet un diviseur premier $p$ , qui est l'un des $p_{i}$ . Mais alors $p$ divise à la fois $N$ et le produit $p_{1} \dots p_{k}$ , donc leur différence : $p ∣ 1$ — ce qui est impossible pour un nombre premier ( $p \geq 2$ ). Contradiction : il existe une infinité de nombres premiers.

◆Théorème 3.18Décomposition en facteurs premiers

Tout entier $n \geq 2$ s'écrit de façon unique (à l'ordre des facteurs près) comme produit de nombres premiers :

$n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{r}^{α_{r}}$

où $p_{1} < p_{2} < \dots < p_{r}$ sont premiers et $α_{i} \geq 1$ .

Exemple 3.19

$252 = 2^{2} \times 3^{2} \times 7$ et $198 = 2 \times 3^{2} \times 11$ . On retrouve $pgcd (252, 198) = 2 \times 3^{2} = 18$ (produit des facteurs communs avec le plus petit exposant).

◆Théorème 3.20Petit théorème de Fermat

Soit $p$ un nombre premier et $a$ un entier non divisible par $p$ . Alors :

$a^{p - 1} \equiv 1 (mod p)$

Version générale : pour tout entier $a$ , $a^{p} \equiv a (mod p)$ .

Exemple 3.21

$2^{10} \equiv 1 (mod 11)$ (avec $p = 11$ , $a = 2$ ). On en déduit par exemple $2^{2026} = 2^{10 \times 202 + 6} \equiv 2^{6} = 64 \equiv 9 (mod 11)$ .

3.5 Méthodes Clés

Méthode : Résoudre une équation diophantienne $a x + b y = c$

Calculer $d = pgcd (a, b)$ . L'équation a des solutions entières si et seulement si $d ∣ c$ .
Trouver une solution particulière $(x_{0}, y_{0})$ (Bézout, remontée d'Euclide, ou essai).
Forme générale : soustraire $a x_{0} + b y_{0} = c$ de $a x + b y = c$ donne $a (x - x_{0}) = - b (y - y_{0})$ ; après division par $d$ et application du théorème de Gauss :

$x = x_{0} + \frac{b}{d} k, y = y_{0} - \frac{a}{d} k (k \in Z)$

3.6 Algorithmique et Programmation


def pgcd(a, b):
    # Algorithme d'Euclide : le PGCD est le dernier reste non nul
    while b != 0:
        a, b = b, a % b
    return a

def bezout(a, b):
    # Euclide etendu : renvoie (d, x, y) avec a*x + b*y = d = pgcd(a, b)
    if b == 0:
        return (a, 1, 0)
    d, u, v = bezout(b, a % b)
    return (d, v, u - (a // b) * v)

# pgcd(252, 198) renvoie 18 ; bezout(252, 198) renvoie (18, 4, -5)

Algorithme d'Euclide et couple de Bézout


def crible(n):
    # Renvoie la liste des nombres premiers <= n
    est_premier = [True] * (n + 1)
    est_premier[0] = est_premier[1] = False
    for p in range(2, n + 1):
        if est_premier[p]:
            for multiple in range(p * p, n + 1, p):
                est_premier[multiple] = False
    return [p for p in range(n + 1) if est_premier[p]]

def decomposition(n):
    # Renvoie la liste des facteurs premiers de n (avec repetition)
    facteurs = []
    p = 2
    while p * p <= n:
        while n % p == 0:
            facteurs.append(p)
            n = n // p
        p = p + 1
    if n > 1:
        facteurs.append(n)
    return facteurs

# crible(30) : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# decomposition(252) : [2, 2, 3, 3, 7]

Crible d'Ératosthène et décomposition en facteurs premiers

Continuer sur Adloun : animation, QCM, fiches, exercices