Ascension Maths

I. Divisibilité et division euclidienne

DéfinitionDivisibilité

Un entier relatif $b$ divise un entier relatif $a$ lorsqu'il existe un entier $k$ tel que $a = kb$ . On note alors $b \mid a$ .

L'ensemble des diviseurs communs à deux entiers est stable par combinaison : si $d$ divise $a$ et $b$ , alors $d$ divise $au+bv$ pour tous entiers $u$ et $v$ . Cette remarque est le moteur de presque toutes les démonstrations du chapitre.

ThéorèmeDivision euclidienne

Pour tout entier relatif $a$ et tout entier naturel non nul $b$ , il existe un unique couple d'entiers $(q\,;r)$ tel que

a = bq+r \qquad \text{avec} \qquad 0 \leqslant r < b

Les entiers $q$ et $r$ s'appellent le quotient et le reste de la division euclidienne de $a$ par $b$ .

Attention

Le reste est toujours positif ou nul, y compris pour un dividende négatif. La division de $-17$ par $5$ donne $-17 = 5 \times (-4)+3$ , avec un reste égal à $3$ , et non $-2$ .

II. Congruences

Beaucoup de questions ne portent pas sur la valeur exacte d'un entier, mais sur son reste : un jour de la semaine, un chiffre des unités, une clé de contrôle. Les congruences sont l'outil adapté à ce type de raisonnement.

DéfinitionCongruence

Soit $n$ un entier naturel non nul. Deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ lorsque $n$ divise $a-b$ . On écrit

a \equiv b \;[n]

Cela revient à dire que $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .

PropriétéCompatibilité avec les opérations

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

a+c \equiv b+d\;[n] \qquad ac \equiv bd\;[n] \qquad a^k \equiv b^k\;[n]

pour tout entier naturel $k$ . Les congruences se manipulent donc presque comme des égalités, à une exception près : on ne simplifie pas librement par un facteur commun.

ExempleChiffre des unités

Cherchons le chiffre des unités de $7^{2026}$ , c'est-à-dire son reste modulo $10$ .

Les puissances de $7$ modulo $10$ donnent $7$ , $9$ , $3$ , $1$ , puis se répètent avec une période de $4$ . Comme $2026 = 4 \times 506+2$ :

7^{2026} \equiv 7^2 \equiv 9 \;[10]

Le chiffre des unités est donc $9$ .

MéthodeRésoudre

ax \equiv b\;[n]

Lorsque $a$ et $n$ sont premiers entre eux, l'entier $a$ possède un inverse modulo $n$ , c'est-à-dire un entier $u$ tel que $au \equiv 1\;[n]$ . Cet inverse s'obtient par l'algorithme d'Euclide.

Multiplier les deux membres de la congruence par $u$ donne alors la solution.

III. PGCD, Bézout et Gauss

DéfinitionPGCD et algorithme d'Euclide

Le PGCD de deux entiers naturels non tous nuls est le plus grand de leurs diviseurs communs.

L'algorithme d'Euclide repose sur l'égalité $\text{PGCD}(a\,;b)=\text{PGCD}(b\,;r)$ , où $r$ est le reste de la division de $a$ par $b$ . On remplace donc le couple par un couple plus petit, jusqu'à obtenir un reste nul : le dernier reste non nul est le PGCD.

Exemple

Calculons $\text{PGCD}(252\,;105)$ .

252 = 2 \times 105+42 \qquad 105 = 2 \times 42+21 \qquad 42 = 2 \times 21+0

Le dernier reste non nul vaut $21$ , donc $\text{PGCD}(252\,;105)=21$ .

DéfinitionEntiers premiers entre eux

Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$ , c'est-à-dire lorsque leurs seuls diviseurs communs sont $1$ et $-1$ .

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

Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $u$ et $v$ tels que

au+bv=1

Plus généralement, le PGCD de $a$ et $b$ s'écrit toujours sous la forme $au+bv$ .

Démonstration : Le PGCD s'écrit

au+bv

Considérons l'ensemble $E$ des entiers strictement positifs de la forme $au+bv$ , avec $u$ et $v$ entiers relatifs. Cet ensemble n'est pas vide, car il contient $|a|$ ou $|b|$ . Il possède donc un plus petit élément, noté $d = au_0+bv_0$ .

Montrons que $d$ divise $a$ . La division euclidienne de $a$ par $d$ donne $a = dq+r$ avec $0 \leqslant r<d$ , donc

r = a-dq = a-(au_0+bv_0)q = a\,(1-u_0q)+b\,(-v_0q)

Le reste $r$ est donc de la forme $au+bv$ . S'il était strictement positif, il appartiendrait à $E$ tout en étant plus petit que $d$ , ce qui contredirait le choix de $d$ . Donc $r=0$ , et $d$ divise $a$ . Le même raisonnement montre que $d$ divise $b$ .

Enfin, tout diviseur commun à $a$ et $b$ divise $au_0+bv_0$ , c'est-à-dire $d$ . L'entier $d$ est donc bien le PGCD de $a$ et $b$ .

ThéorèmeThéorème de Gauss

Si un entier $a$ divise le produit $bc$ et si $a$ est premier avec $b$ , alors $a$ divise $c$ .

Démonstration : Théorème de Gauss

Comme $a$ et $b$ sont premiers entre eux, le théorème de Bézout fournit deux entiers $u$ et $v$ tels que

au+bv=1

Multiplions cette égalité par $c$ :

acu+bcv=c

L'entier $a$ divise le premier terme, puisqu'il y figure en facteur. Il divise aussi le second, puisqu'il divise $bc$ par hypothèse. Il divise donc leur somme, c'est-à-dire $c$ .

MéthodeÉquation diophantienne

ax+by=c

Calculer $d = \text{PGCD}(a\,;b)$ . L'équation admet des solutions si et seulement si $d$ divise $c$ .
Trouver une solution particulière, par l'algorithme d'Euclide remonté ou par essais.
Écrire la solution générale en soustrayant les deux égalités, puis en appliquant le théorème de Gauss.

IV. Nombres premiers

DéfinitionNombre premier

Un entier naturel $p$ supérieur ou égal à $2$ est premier lorsque ses seuls diviseurs positifs sont $1$ et lui-même.

ThéorèmeDécomposition en facteurs premiers

Tout entier naturel supérieur ou égal à $2$ s'écrit comme produit de nombres premiers, et cette écriture est unique à l'ordre près des facteurs.

Démonstration : L'ensemble des nombres premiers est infini

Raisonnons par l'absurde en supposant qu'il n'existe qu'un nombre fini de nombres premiers, notés $p_1, p_2, \ldots, p_k$ .

Considérons l'entier

N = p_1p_2\cdots p_k+1

Cet entier est supérieur ou égal à $2$ , donc il admet un diviseur premier $p$ , qui figure nécessairement dans la liste.

Ce nombre $p$ divise le produit $p_1p_2\cdots p_k$ , et il divise $N$ . Il divise donc leur différence, qui vaut $1$ . Or aucun nombre premier ne divise $1$ .

La supposition mène à une contradiction : l'ensemble des nombres premiers est infini.

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

Soit $p$ un nombre premier et $a$ un entier.

a^p \equiv a \;[p]

Si de plus $a$ n'est pas divisible par $p$ :

a^{p-1} \equiv 1 \;[p]

Exemple

Calculons le reste de $3^{100}$ modulo $7$ . Comme $7$ est premier et ne divise pas $3$ , le petit théorème de Fermat donne $3^{6} \equiv 1\;[7]$ .

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

3^{100} \equiv \left(3^6\right)^{16} \times 3^4 \equiv 3^4 \equiv 81 \equiv 4 \;[7]

ExempleCrible d'Ératosthène

def crible(n):
    est_premier = [True] * (n + 1)
    est_premier[0] = False
    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]]

Arithmétique

Avant de commencer

À la fin du chapitre, tu sais

I. Divisibilité et division euclidienne

II. Congruences

III. PGCD, Bézout et Gauss

IV. Nombres premiers