Rappel · 1

Dans la division euclidienne d'un entier naturel $a$ par un entier naturel non nul $b$ , quelle condition fondamentale doit vérifier le reste $r$ ?

Remarque

Le reste $r$ est un entier naturel obligatoirement encadré par $0 \le r < b$ : il est toujours strictement inférieur au diviseur $b$ .

Point de départ · 2

On donne l'égalité exacte : $282 = 14 \times 19 + 16$ Cette égalité représente-t-elle la division euclidienne de $282$ par $14$ ou par $19$ ?

Remarque

Si le diviseur était $14$ , le reste serait $16$ , ce qui est impossible car $16 \ge 14$ . Comme $16 < 19$ , il s'agit de la division euclidienne par $19$ .

Définition · 3

Théorème de la division euclidienne

Soient $a$ et $b$ deux entiers naturels avec $b \neq 0$ . Il existe un unique couple d'entiers naturels $(q, r)$ vérifiant :

$a = bq + r$

0 \le r < b

$a$ est le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste.

Exemple travaillé · 4

Déterminer le quotient entier $q$ et le reste $r$ de la division euclidienne de $82\;368\;941$ par $253\;687$ , sachant que la division décimale donne environ $324{,}6872$ .

1

Le quotient entier $q$ est la partie entière du quotient décimal : $q = 324$ .

2

On exprime le reste exact à l'aide de l'égalité euclidienne : $r = a - bq$ .

3

r = 82\;368\;941 - 253\;687 \times 324 = 82\;368\;941 - 82\;194\;588 = 174\;353

4

On contrôle l'encadrement : $0 \le 174\;353 < 253\;687$ . L'égalité s'écrit :

5

82\;368\;941 = 253\;687 \times 324 + 174\;353

Piège classique · 5

Soit $n$ un entier naturel dont le reste dans la division par $6$ vaut $5$ ( $n = 6k + 5$ ). Quel est le reste de la division euclidienne de $3n$ par $6$ ?

Attention

Développer $3n = 18k + 15$ et déclarer directement que le reste est $15$ .

À la place : Le reste doit être strictement inférieur à $6$ . On décompose $15 = 6 \times 2 + 3$ , d'où $3n = 6(3k + 2) + 3$ . Le reste est donc $3$ .

Vérification · 6

Pour tout entier $n \in \mathbb{N}$ , on pose $A = 8n + 27$ . Quel est le reste de la division euclidienne de $A$ par $8$ ?

Remarque

Comme $27 \ge 8$ , on effectue la division de $27$ par $8$ : $27 = 8 \times 3 + 3$ . On obtient $A = 8(n + 3) + 3$ . Puisque $0 \le 3 < 8$ , le reste est $3$ .

Point de départ · 7

Soit $d$ un diviseur commun à $a = 3n - 5$ et $b = 2n - 7$ . Quelle combinaison linéaire permet d'éliminer complètement l'inconnue $n$ pour contraindre $d$ ?

Remarque

On effectue un produit croisé des coefficients de $n$ : $2a - 3b = 2(3n - 5) - 3(2n - 7) = 6n - 10 - 6n + 21 = 11$ . Tout diviseur commun $d$ doit donc obligatoirement diviser $11$ .

Définition · 8

Stabilité par combinaisons linéaires

Soient $a$ et $b$ deux entiers naturels et $c$ un entier naturel non nul.

$c \mid a \text{ et } c \mid b \implies c \mid (\alpha a + \beta b)$

\forall \alpha, \beta \in \mathbb{Z} \text{ tels que } \alpha a + \beta b \in \mathbb{N}

En particulier, tout diviseur commun à $a$ et $b$ divise leur somme $a + b$ , leur différence $a - b$ (si $a \ge b$ ) et toute combinaison linéaire entière.

Exemple travaillé · 9

Déterminer tous les entiers naturels $n > 1$ tels que $n - 1$ divise $n + 17$ .

1

On exprime le numérateur $n + 17$ en faisant apparaître le diviseur $n - 1$ :

2

n + 17 = (n - 1) + 18

3

Puisque $n - 1$ divise $n - 1$ , il divise $n + 17$ si et seulement si $n - 1$ divise $18$ .

4

Les diviseurs de $18$ dans $\mathbb{N}^*$ sont $1, 2, 3, 6, 9$ et $18$ . On en déduit les valeurs de $n = (n - 1) + 1$ :

5

n \in \{2\, ;\, 3\, ;\, 4\, ;\, 7\, ;\, 10\, ;\, 19\}

Exemple travaillé · 10

Montrer que pour tout entier naturel $n$ , les entiers $c = 6n + 5$ et $d = 7n + 6$ sont premiers entre eux.

1

Soit $\delta$ un diviseur commun positif à $c$ et $d$ . Alors $\delta$ divise toute combinaison linéaire entière de $c$ et $d$ .

2

On choisit les coefficients croisés pour éliminer le terme en $n$ :

3

7c - 6d = 7(6n + 5) - 6(7n + 6) = 42n + 35 - 42n - 36 = -1

4

Puisque $\delta$ divise $-1$ et que $\delta \in \mathbb{N}^*$ , on a nécessairement $\delta = 1$ . Les entiers $c$ et $d$ sont donc premiers entre eux.

Piège classique · 11

On cherche les diviseurs communs à $a = 3n - 5$ et $b = 2n - 7$ pour $n \in \mathbb{N}$ . Quelle méthode conduit à une conclusion rigoureuse ?

Attention

Engager une démonstration par récurrence sur $n$ ou tester $n=0, 1, 2$ en croyant que la divisibilité dépend de chaque entier $n$ .

À la place : Il faut éliminer la variable $n$ par combinaison linéaire : $2a - 3b = 11$ . Tout diviseur commun divise $11$ , donc les seuls diviseurs communs possibles sont $1$ et $11$ .

Vérification · 12

En éliminant la variable $n$ par une combinaison linéaire adaptée, déterminer la valeur du PGCD $(5n + 3) \wedge (2n + 1)$ pour tout $n \in \mathbb{N}$ .

Remarque

On forme $2(5n + 3) - 5(2n + 1) = 10n + 6 - 10n - 5 = 1$ . Tout diviseur commun divise $1$ , donc le PGCD vaut nécessairement $1$ pour tout $n$ .

Point de départ · 13

On considère les entiers $a = 24$ et $b = 36$ . Leur plus grand commun diviseur est $d = 12$ . On écrit $a = 12 \times 2$ et $b = 12 \times 3$ . Que vaut le PGCD des quotients $2$ et $3$ ?

Remarque

On a $2 \wedge 3 = 1$ : après factorisation par le PGCD, les deux quotients restants sont obligatoirement premiers entre eux.

Définition · 14

Forme réduite par factorisation du PGCD

Soient $a$ et $b$ deux entiers naturels non nuls et $d = a \wedge b$ leur PGCD.

$a = da' \quad \text{et} \quad b = db'$

a' \wedge b' = 1

Les entiers naturels $a'$ et $b'$ sont appelés les quotients réduits de $a$ et $b$ .

Exemple travaillé · 15

Résoudre dans $\mathbb{N}^2$ le système : $\begin{cases} a + b = 144 \\ a \wedge b = 18 \end{cases}$

1

Puisque $a \wedge b = 18$ , on pose $a = 18a'$ et $b = 18b'$ avec $a', b' \in \mathbb{N}$ et $a' \wedge b' = 1$ .

2

L'égalité $a + b = 144$ devient $18a' + 18b' = 144$ , soit en simplifiant par $18$ :

3

a' + b' = 8

4

On liste les couples d'entiers naturels de somme $8$ vérifiant la condition $a' \wedge b' = 1$ .

5

Les couples admissibles sont $(1, 7)$ , $(3, 5)$ , $(5, 3)$ et $(7, 1)$ . Les couples $(0, 8)$ , $(2, 6)$ et $(4, 4)$ sont éliminés car ils ne sont pas premiers entre eux.

6

On multiplie chaque quotient par $18$ pour obtenir les couples $(a, b)$ solutions :

7

S = \{(18\, ;\, 126)\, ;\, (54\, ;\, 90)\, ;\, (90\, ;\, 54)\, ;\, (126\, ;\, 18)\}

Exemple travaillé · 16

Résoudre dans $(\mathbb{N}^*)^2$ le système : $\begin{cases} ab = 1728 \\ a \wedge b = 12 \end{cases}$

1

On pose $a = 12a'$ et $b = 12b'$ avec $a', b' \in \mathbb{N}^*$ et $a' \wedge b' = 1$ .

2

On injecte dans le produit : $(12a')(12b') = 1728$ , ce qui s'écrit $144a'b' = 1728$ .

3

En divisant par $12^2 = 144$ , on obtient l'équation réduite :

4

a'b' = 12

5

On cherche les diviseurs associés de $12$ qui sont premiers entre eux ( $a' \wedge b' = 1$ ).

6

Les couples retenus sont $(1, 12)$ , $(3, 4)$ , $(4, 3)$ et $(12, 1)$ . Le couple $(2, 6)$ est rejeté car $2 \wedge 6 = 2 \neq 1$ .

7

On multiplie par $12$ pour obtenir les solutions finales $(a, b)$ :

8

S = \{(12\, ;\, 144)\, ;\, (36\, ;\, 48)\, ;\, (48\, ;\, 36)\, ;\, (144\, ;\, 12)\}

Piège classique · 17

Pour résoudre le système $\begin{cases} a + b = 144 \\ a \wedge b = 18 \end{cases}$ , on a trouvé $a' + b' = 8$ . Le couple $(a', b') = (2, 6)$ donne-t-il une solution $(a, b) = (36, 108)$ admissible ?

Attention

Valider $(36, 108)$ sous prétexte que $36 + 108 = 144$ .

À la place : Comme $2$ et $6$ ont pour PGCD $2$ , le PGCD de $36$ et $108$ est $18 \times 2 = 36$ et non $18$ . Le couple $(2, 6)$ viole la condition $a' \wedge b' = 1$ .

Vérification · 18

Dans la résolution du système $\begin{cases} x + y = 224 \\ x \wedge y = 16 \end{cases}$ avec $x, y \in \mathbb{N}^*$ , on pose $x = 16x'$ et $y = 16y'$ , ce qui donne $x' + y' = 14$ . Combien de couples $(x', y')$ sont admissibles pour former les solutions ?

Remarque

Les couples d'entiers naturels non nuls vérifiant $x' + y' = 14$ et $x' \wedge y' = 1$ sont $(1, 13)$ , $(3, 11)$ , $(5, 9)$ , $(9, 5)$ , $(11, 3)$ et $(13, 1)$ . Les couples $(2, 12)$ , $(4, 10)$ , $(6, 8)$ et $(7, 7)$ sont éliminés. Il y a donc exactement $6$ couples admissibles.

Point de départ · 19

On sait que $6$ divise $36$ , et on peut écrire $36 = 4 \times 9$ . L'entier $6$ divise-t-il $4$ ? Divise-t-il $9$ ?

Remarque

$6$ ne divise ni $4$ ni $9$ , bien qu'il divise leur produit $36$ . Pour qu'un entier divisant un produit $bc$ divise nécessairement l'un des deux facteurs, une condition supplémentaire de coprimalité est indispensable.

Définition · 20

Lemme de Gauss

Soient $a, b$ et $c$ trois entiers naturels non nuls.

$a \mid bc \quad \text{et} \quad a \wedge b = 1 \implies a \mid c$

a \wedge b = 1

Si un entier divise un produit de deux facteurs et est premier avec l'un d'eux, alors il divise nécessairement l'autre facteur.

Exemple travaillé · 21

Déterminer tous les couples d'entiers naturels $(a, b)$ vérifiant : $3(a - 2) = 2(b - 3)$ .

1

L'égalité implique que $3$ divise le produit $2(b - 3)$ .

2

Comme $3$ et $2$ sont premiers entre eux ( $3 \wedge 2 = 1$ ), d'après le lemme de Gauss, $3$ divise $b - 3$ .

3

Il existe donc un entier naturel $k$ tel que $b - 3 = 3k$ , soit $b = 3k + 3$ .

4

3(a - 2) = 2(3k) \iff a - 2 = 2k \iff a = 2k + 2

5

Pour que $a$ et $b$ soient des entiers naturels, il faut et il suffit que $k \in \mathbb{N}$ . L'ensemble des solutions est :

6

S = \{(2k + 2\, ;\, 3k + 3) \mid k \in \mathbb{N}\}

Exemple travaillé · 22

Soient $a$ et $b$ deux entiers naturels non nuls. Montrer que si $4$ divise $ab$ et si $a$ est impair, alors $4$ divise $b$ .

1

Puisque $a$ est impair, aucun facteur $2$ n'apparaît dans sa décomposition en facteurs premiers.

2

Les seuls diviseurs de $4 = 2^2$ supérieurs à $1$ étant $2$ et $4$ , aucun d'eux ne divise $a$ . On a donc :

3

a \wedge 4 = 1

4

On a $4$ qui divise le produit $ab$ et $4 \wedge a = 1$ . D'après le lemme de Gauss, $4$ divise nécessairement $b$ .

Piège classique · 23

Pour résoudre dans $\mathbb{N}^2$ l'équation $22(a - 1) = 26(b - 3)$ , peut-on appliquer directement le lemme de Gauss pour affirmer que $22$ divise $b - 3$ ?

Attention

Appliquer le lemme de Gauss sans vérifier que les coefficients sont premiers entre eux ( $22 \wedge 26 = 2 \neq 1$ ).

À la place : Il faut d'abord simplifier par le PGCD des coefficients : en divisant par $2$ , l'équation devient $11(a - 1) = 13(b - 3)$ . Comme $11 \wedge 13 = 1$ , Gauss s'applique alors valablement et donne $11 \mid (b - 3)$ .

Vérification · 24

Soient $a$ et $b$ deux entiers naturels vérifiant $5a = 33b$ . Quelle est l'expression générale de $a$ en fonction d'un paramètre $k \in \mathbb{N}$ ?

Remarque

Comme $5 \wedge 33 = 1$ et que $5$ divise $33b$ , d'après le lemme de Gauss, $5$ divise $b$ , d'où $b = 5k$ . En substituant : $5a = 33(5k) \iff a = 33k$ avec $k \in \mathbb{N}$ .

Point de départ · 25

Si un entier $n \ge 2$ est composé, il s'écrit $n = a \times b$ avec $a > 1$ et $b > 1$ . Est-il possible que les deux facteurs $a$ et $b$ soient tous les deux strictement supérieurs à $\sqrt{n}$ ?

Remarque

Non, car si $a > \sqrt{n}$ et $b > \sqrt{n}$ , alors $a \times b > \sqrt{n} \times \sqrt{n} = n$ , ce qui est contradictoire. Au moins l'un des deux facteurs est donc obligatoirement inférieur ou égal à $\sqrt{n}$ .

Définition · 26

Test de primalité par la racine carrée

Soit $n$ un entier naturel supérieur ou égal à $2$ .

$n \text{ est premier} \iff \forall p \in \mathbb{P} \text{ tel que } p \le \sqrt{n}, \; p \nmid n$

p^2 \le n

Pour déterminer si $n$ est premier, on teste successivement sa divisibilité par les nombres premiers rangés dans l'ordre croissant ( $2, 3, 5, 7, 11, \dots$ ). L'algorithme s'arrête dès qu'une division tombe juste ( $n$ est composé) ou dès qu'on atteint un nombre premier $p$ vérifiant $p^2 > n$ ( $n$ est premier).

Exemple travaillé · 27

Déterminer si l'entier $971$ est un nombre premier en appliquant le critère de la racine carrée.

1

On encadre la racine carrée : $31^2 = 961 \le 971$ et $37^2 = 1369 > 971$ , donc $\sqrt{971} \approx 31{,}16$ .

2

Les nombres premiers inférieurs ou égaux à $\sqrt{971}$ sont : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ et $31$ .

3

$971$ est impair (non divisible par $2$ ), la somme de ses chiffres est $17$ (non divisible par $3$ ), et son chiffre des unités est $1$ (non divisible par $5$ ).

4

On effectue les divisions par les premiers suivants : $971 = 7 \times 138 + 5$ , $971 = 11 \times 88 + 3$ , $971 = 13 \times 74 + 9$ , $971 = 17 \times 57 + 2$ , $971 = 19 \times 51 + 2$ , $971 = 23 \times 42 + 5$ , $971 = 29 \times 33 + 14$ , $971 = 31 \times 31 + 10$ .

5

Le nombre premier suivant est $37$ avec $37^2 > 971$ . Aucun premier $\le \sqrt{971}$ ne divise $971$ , donc $971$ est un nombre premier.

Exemple travaillé · 28

Déterminer si l'entier $1781$ est un nombre premier.

1

On encadre la racine carrée : $41^2 = 1681 \le 1781$ et $43^2 = 1849 > 1781$ , donc $\sqrt{1781} \approx 42{,}2$ .

2

On teste d'abord les critères immédiats : $1781$ n'est ni pair, ni divisible par $3$ (somme $17$ ), ni divisible par $5$ .

3

On poursuit les divisions euclidiennes : $1781 = 7 \times 254 + 3$ et $1781 = 11 \times 161 + 10$ .

4

On teste ensuite le nombre premier $13$ :

5

1781 = 13 \times 137 + 0

6

Le reste est nul : $1781$ admet le diviseur strict $13$ (avec $1 < 13 < 1781$ ). L'entier $1781$ est donc composé.

Piège classique · 29

Soit $n \in \mathbb{N}$ . L'entier $A = n^2 + 4n + 3$ peut-il être un nombre premier ?

Attention

Factoriser $A = (n+1)(n+3)$ et affirmer que $A$ n'est jamais premier car c'est un produit de deux facteurs.

À la place : Dans $\mathbb{N}$ , un produit $u \times v$ est premier lorsque le plus petit facteur vaut $1$ et l'autre est premier. Ici, $n + 1 = 1 \iff n = 0$ . Pour $n = 0$ , $A = 1 \times 3 = 3$ , qui est bien premier.

Vérification · 30

Déterminer l'unique valeur de l'entier naturel $n$ pour laquelle l'entier $P(n) = n^2 + 3n + 2$ est un nombre premier.

Remarque

On factorise $P(n) = (n + 1)(n + 2)$ . Comme $n + 1 < n + 2$ , le produit ne peut être premier que si son plus petit facteur vaut $1$ , c'est-à-dire $n + 1 = 1 \iff n = 0$ . On vérifie que $P(0) = 1 \times 2 = 2$ , qui est bien un nombre premier.

Rappel · 31

Rappelle la relation fondamentale liant le PGCD et le PPCM de deux entiers naturels non nuls $a$ et $b$ .

Remarque

Pour tous $a, b \in \mathbb{N}^*$ , le produit de leur PGCD par leur PPCM est égal au produit des deux entiers : $(a \wedge b) \times (a \vee b) = ab$ .

Définition · 32

Résolution des systèmes conjoints PGCD et PPCM

Pour résoudre un système comportant le PGCD et le PPCM de deux inconnues $a$ et $b$ , on exploite la forme réduite et la relation fondamentale :

$a = da' \quad \text{et} \quad b = db' \quad \text{avec} \quad a' \wedge b' = 1$

Le PPCM s'exprime alors simplement sous la forme $a \vee b = da'b'$ .

Exemple travaillé · 33

Résoudre dans $(\mathbb{N}^*)^2$ le système : $\begin{cases} a \vee b = 120 \\ a \wedge b = 10 \end{cases}$

1

On pose $a = 10a'$ et $b = 10b'$ avec $a', b' \in \mathbb{N}^*$ et $a' \wedge b' = 1$ .

2

On sait que $a \vee b = da'b'$ . L'équation du PPCM devient :

3

10a'b' = 120 \iff a'b' = 12

4

On cherche les diviseurs de $12$ sous forme de couples $(a', b')$ premiers entre eux :

5

Les couples $(a', b')$ retenus sont $(1, 12)$ , $(3, 4)$ , $(4, 3)$ et $(12, 1)$ . Le couple $(2, 6)$ est exclu car $2 \wedge 6 = 2 \neq 1$ .

6

En multipliant par $d = 10$ , on obtient l'ensemble des solutions $(a, b)$ :

7

S = \{(10\, ;\, 120)\, ;\, (30\, ;\, 40)\, ;\, (40\, ;\, 30)\, ;\, (120\, ;\, 10)\}

Exemple travaillé · 34

Résoudre dans $(\mathbb{N}^*)^2$ le système : $\begin{cases} a \vee b - a \wedge b = 187 \\ a \text{ divise } b \end{cases}$

1

Puisque $a$ divise $b$ , on a $a \wedge b = a$ et $a \vee b = b$ .

2

Le système se simplifie immédiatement en une équation de différence :

3

b - a = 187

4

Comme $a$ divise $b$ , il existe un entier $k \ge 2$ tel que $b = ka$ . L'équation devient $ka - a = 187$ , soit :

5

a(k - 1) = 187

6

On décompose $187 = 11 \times 17$ . Ses diviseurs sont $1, 11, 17$ et $187$ . On teste chaque valeur de $a$ :

7

• $a = 1 \implies k-1 = 187 \implies b = 188$ \
• $a = 11 \implies k-1 = 17 \implies b = 198$ \
• $a = 17 \implies k-1 = 11 \implies b = 204$ \
• $a = 187 \implies k-1 = 1 \implies b = 374$

8

S = \{(1\, ;\, 188)\, ;\, (11\, ;\, 198)\, ;\, (17\, ;\, 204)\, ;\, (187\, ;\, 374)\}

Piège classique · 35

Dans la résolution du système $\begin{cases} a \vee b = 120 \\ a \wedge b = 10 \end{cases}$ , on obtient $a'b' = 12$ . Le couple $(a', b') = (2, 6)$ est-il acceptable pour former une solution ?

Attention

Conserver le couple $(2, 6)$ sous prétexte que $2 \times 6 = 12$ .

À la place : Le couple $(2, 6)$ est rejeté car $2 \wedge 6 = 2 \neq 1$ . Les quotients réduits doivent impérativement être premiers entre eux pour respecter la définition du PGCD.

Vérification · 36

Soit un système où $a \wedge b = 18$ et $a \vee b = 360$ . Quel est le produit $ab$ ?

Remarque

D'après la relation fondamentale $(a \wedge b) \times (a \vee b) = ab$ , on a $ab = 18 \times 360 = 6480$ .

Arithmétique — cours

Le cours

Théorème de la division euclidienne

Stabilité par combinaisons linéaires

Forme réduite par factorisation du PGCD

Lemme de Gauss

Test de primalité par la racine carrée

Résolution des systèmes conjoints PGCD et PPCM

Chapitres liés

Continuer sur Lumio