1ʳᵉ Bac · Sciences Maths · Chapitre 14

Arithmétique dans ℕ

1 · Résumé du cours

1.1 Divisibilité dans $\mathbb{Z}$

Diviseur, multiple Soient

a,b\in\mathbb{Z}

. On dit que

a

divise

b

, noté

a\mid b

, lorsqu'il existe

k\in\mathbb{Z}

tel que

b=a\,k

. On dit alors que

a

est un diviseur de

b

, et

b

un multiple de

a

.
Exemples :

3\mid12

car

12=3\times4

;

7\nmid20

. Pour tout

a

1\mid a

a\mid a

, et

a\mid0

(car

0=a\times0

Règles de calcul Pour tous entiers

a,b,c,u,v

$a\mid a$ (réflexivité) ;
si $a\mid b$ et $b\mid c$ , alors $a\mid c$ (transitivité) ;
si $a\mid b$ et $a\mid c$ , alors $a\mid(bu+cv)$ (combinaison linéaire — la règle la plus utile) ;
si $a\mid b$ et $b\mid a$ , alors $a=b$ ou $a=-b$ ;
si $a\mid b$ et $b\neq0$ , alors $|a|\le|b|$ .

La règle qui débloque presque tout Pour montrer qu'un nombre

d

divise une expression, on l'écrit comme combinaison linéaire de choses que

d

divise déjà. Ex. : si

d\mid n

d\mid(n+7)

, alors

d

divise la différence

(n+7)-n=7

— donc

d\in\{1,7\}

d\in\mathbb{N}^*

1.2 La division euclidienne

Théorème Soient

a\in\mathbb{Z}

b\in\mathbb{N}^*

. Il existe un unique couple

(q,r)\in\mathbb{Z}\times\mathbb{N}

tel que

a=b\,q+r\quad\text{avec}\quad 0\le r<b.

q

est le quotient,

r

le reste.
Exemples :

47=6\times7+5

(

q=7,r=5

). Pour

a=-47

-47=6\times(-8)+1

, donc

q=-8,r=1

— le reste est toujours positif.

Propriété

b\mid a

si et seulement si le reste de la division euclidienne de

a

par

b

est nul.

Méthode — utiliser les restes possibles Pour démontrer une propriété de divisibilité « pour tout entier

n

», on discute selon le reste de

n

dans la division par

b

: seulement

b

cas (

r=0,1,\dots,b-1

). C'est le raisonnement par disjonction des cas.
Exemple :

n(n+1)

est pair. Si

n=2k

n(n+1)=2k(n+1)

; si

n=2k+1

n+1=2(k+1)

n(n+1)=2n(k+1)

. Dans les deux cas

2\mid n(n+1)

1.3 PGCD et algorithme d'Euclide

PGCD Soient

a,b

deux entiers naturels non tous deux nuls. L'ensemble de leurs diviseurs communs admet un plus grand élément, le plus grand commun diviseur

\mathrm{pgcd}(a,b)

(ou

a\wedge b

Lemme d'Euclide Si

a=bq+r

(division euclidienne), alors

\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r)

.
Preuve : tout diviseur commun de

a,b

divise

r=a-bq

; réciproquement tout diviseur commun de

b,r

divise

a=bq+r

. Mêmes diviseurs communs, donc même plus grand. ∎

Méthode — algorithme d'Euclide On remplace

(a,b)

par

(b,r)

et on recommence, jusqu'à un reste nul. Le dernier reste non nul est le PGCD.
Exemple

\mathrm{pgcd}(1071,462)

\begin{array}{rcl}1071 &=& 462\times2+147\\ 462 &=& 147\times3+21\\ 147 &=& 21\times7+0\end{array}

Dernier reste non nul :

21

, donc

\mathrm{pgcd}(1071,462)=21

Entiers premiers entre eux

a

b

sont premiers entre eux lorsque

\mathrm{pgcd}(a,b)=1

. Si

d=\mathrm{pgcd}(a,b)

, il existe

a',b'

premiers entre eux tels que

a=d\,a'

b=d\,b'

: c'est la fraction irréductible

\frac ab=\frac{a'}{b'}

1.4 PPCM

PPCM Le plus petit commun multiple strictement positif de

a

b

(non nuls) est noté

\mathrm{ppcm}(a,b)

(ou

a\vee b

Relation fondamentale Pour tous entiers naturels non nuls

a,b

\mathrm{pgcd}(a,b)\times\mathrm{ppcm}(a,b)=a\times b

.
Exemple :

\mathrm{pgcd}(12,18)=6

, donc

\mathrm{ppcm}(12,18)=\frac{12\times18}{6}=36

1.5 Les nombres premiers

Nombre premier Un entier

p\ge2

est premier lorsqu'il admet exactement deux diviseurs positifs :

1

p

. Un entier

n\ge2

non premier est composé.

1

n'est pas premier

1

n'a qu'un seul diviseur positif, pas deux. L'exclure rend unique la décomposition en facteurs premiers (sinon on ajouterait autant de facteurs

1

que l'on veut).

Les premiers inférieurs à

100

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,

53,59,61,67,71,73,79,83,89,97.

Il y en a

25

. Le seul premier pair est

2

Test de primalité Si un entier

n\ge2

n'est divisible par aucun nombre premier

p\le\sqrt n

, alors

n

est premier.
Exemple :

n=211

\sqrt{211}\approx14{,}5

; on teste

2,3,5,7,11,13

: aucun ne divise

211

, donc

211

est premier.

Euclide — infinité de nombres premiers L'ensemble des nombres premiers est infini.
Preuve (absurde) : supposons-les en nombre fini

p_1,\dots,p_k

; posons

N=p_1\cdots p_k+1\ge2

N

admet un diviseur premier

p

, l'un des

p_i

; alors

p\mid N

p\mid p_1\cdots p_k

, donc

p\mid1

— impossible. Contradiction. ∎

1.6 Décomposition en facteurs premiers

Théorème fondamental de l'arithmétique Tout entier

n\ge2

s'écrit de manière unique (à l'ordre près) :

n=p_1^{\alpha_1}\,p_2^{\alpha_2}\cdots p_k^{\alpha_k},

où les

p_i

sont des premiers distincts et

\alpha_i\in\mathbb{N}^*

.
Exemples :

360=2^3\times3^2\times5

84=2^2\times3\times7

Lire le PGCD et le PPCM sur la décomposition Exposant le plus petit pour le PGCD, le plus grand pour le PPCM :

\mathrm{pgcd}=\prod p_i^{\min(\alpha_i,\beta_i)},\qquad \mathrm{ppcm}=\prod p_i^{\max(\alpha_i,\beta_i)}.

Exemple :

\mathrm{pgcd}(360,84)=2^2\times3=12

\mathrm{ppcm}(360,84)=2^3\times3^2\times5\times7=2520

Nombre de diviseurs Si

n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}

, le nombre de diviseurs positifs est

(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)

.
Exemple :

360=2^3 3^2 5^1

(3+1)(2+1)(1+1)=24

diviseurs.

1.7 Congruences modulo $n$

Congruence Soit

n\in\mathbb{N}^*

. Deux entiers

a,b

sont congrus modulo $n$ , noté

a\equiv b\ [n]

, lorsque

n\mid(a-b)

; autrement dit

a

b

ont le même reste dans la division par

n

.
Exemples :

17\equiv2\ [5]

car

17-2=15

;

-3\equiv4\ [7]

car

-3-4=-7

Compatibilité avec les opérations Si

a\equiv b\ [n]

c\equiv d\ [n]

, alors

a+c\equiv b+d\ [n],\qquad a\,c\equiv b\,d\ [n],\qquad a^m\equiv b^m\ [n]\ (m\in\mathbb{N}).

Le super-pouvoir des congruences On peut remplacer un nombre par son reste avant de calculer. C'est ce qui permet de traiter des puissances énormes.
Exemple — reste de $7^{100}$ modulo $5$ :

7\equiv2\ [5]

, donc

7^{100}\equiv2^{100}\ [5]

. Or

2^4=16\equiv1\ [5]

100=4\times25

, donc

2^{100}=(2^4)^{25}\equiv1\ [5]

. Le reste est

1

Critères de divisibilité Comme

10\equiv1\ [9]

10\equiv1\ [3]

, un entier est congru à la somme de ses chiffres modulo

9

(et modulo

3

) : il est divisible par

3

(resp.

9

) ssi la somme de ses chiffres l'est.

2 · Exercices résolus

Euclide

Exercice 1

Déterminer $\mathrm{pgcd}(1128,468)$ par l'algorithme d'Euclide, en déduire $\mathrm{ppcm}(1128,468)$ et rendre $\frac{1128}{468}$ irréductible.

Voir la correction

Algorithme d'Euclide : $\begin{array}{rcl}1128 &=& 468\times2+192\\ 468 &=& 192\times2+84\\ 192 &=& 84\times2+24\\ 84 &=& 24\times3+12\\ 24 &=& 12\times2+0\end{array}$ Dernier reste non nul : $12$ , donc $\mathrm{pgcd}(1128,468)=12$ .

$\mathrm{ppcm}=\frac{1128\times468}{12}=1128\times39=43\,992$ .

$1128=12\times94$ et $468=12\times39$ , donc $\frac{1128}{468}=\frac{94}{39}$ , irréductible ( $\mathrm{pgcd}(94,39)=1$ ). ∎

Disjonction

Exercice 2

Montrer que pour tout $n\in\mathbb{N}$ , $n(n+1)(n+2)$ est divisible par $6$ .

Voir la correction

Par $2$ : parmi $n$ et $n+1$ , l'un est pair, donc $2\mid n(n+1)$ , donc $2\mid n(n+1)(n+2)$ .

Par $3$ : selon le reste de $n$ modulo $3$ : si $n\equiv0$ , $3\mid n$ ; si $n\equiv1$ , $n+2\equiv0$ ; si $n\equiv2$ , $n+1\equiv0$ . Dans tous les cas $3\mid n(n+1)(n+2)$ .

Comme $2$ et $3$ sont premiers entre eux et divisent le produit, $6=2\times3$ le divise aussi. ∎

PGCD variable

Exercice 3

Soit $n\in\mathbb{N}$ . Déterminer les valeurs possibles de $d=\mathrm{pgcd}(n+3,\ n+7)$ .

Voir la correction

$d$ divise $n+3$ et $n+7$ , donc leur différence $(n+7)-(n+3)=4$ . Donc $d$ est un diviseur positif de $4$ : $d\in\{1,2,4\}$ .

Ces valeurs sont atteintes : $n=0$ → $\mathrm{pgcd}(3,7)=1$ ; $n=1$ → $\mathrm{pgcd}(4,8)=4$ ; $n=3$ → $\mathrm{pgcd}(6,10)=2$ . Donc $d\in\{1,2,4\}$ . ∎

L'essentiel du chapitre

$a\mid b\iff\exists k\in\mathbb{Z},\ b=ak$ . Règle-reine : si $d$ divise $a$ et $b$ , il divise toute combinaison $au+bv$ .
Division euclidienne : $a=bq+r$ , $0\le r<b$ , couple $(q,r)$ unique ; reste $\ge0$ .
Algorithme d'Euclide : $\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r)$ ; dernier reste non nul = PGCD.
$\mathrm{pgcd}(a,b)\times\mathrm{ppcm}(a,b)=a\times b$ .
Premier : exactement deux diviseurs ; tester par les premiers $\le\sqrt n$ ; infinité (Euclide).
Décomposition unique : $\min$ des exposants → PGCD, $\max$ → PPCM ; $\prod(\alpha_i+1)$ diviseurs.
Congruences : $a\equiv b\ [n]\iff n\mid(a-b)$ , compatibles avec $+,\times$ et les puissances.

Fiche de révisionL’essentiel du chapitre en une page — formules, méthodes et astucesVoir la fiche QCM interactifTeste-toi sur ce chapitre — 22 questions auto-corrigéesCommencer le QCM

Arithmétique dans ℕ

1 · Résumé du cours

1.1 Divisibilité dans Z\mathbb{Z}Z

1.2 La division euclidienne

1.3 PGCD et algorithme d'Euclide

1.4 PPCM

1.5 Les nombres premiers

1.6 Décomposition en facteurs premiers

1.7 Congruences modulo nnn

2 · Exercices résolus

Exercice 1

Exercice 2

Exercice 3

1.1 Divisibilité dans $\mathbb{Z}$

1.7 Congruences modulo $n$