Arithmétique · Cours et exercices | 2ème Bac Sciences Mathématiques

01 · Les briques de base

Divisibilité, division euclidienne et PGCD

Diviser, c'est comparer deux entiers ; le PGCD en est la mesure commune, calculée efficacement grâce à l'algorithme d'Euclide.

I

Divisibilité et division euclidienne

Définition

Soient

a,b\in\mathbb Z

avec

b\neq0

. On dit que

b

divise

a

, noté

b\mid a

, s'il existe

k\in\mathbb Z

tel que

a=kb

.

Propriétés

$a\mid b$ et $b\mid a$ $\implies |a|=|b|$ .
$a\mid b$ et $b\mid c$ $\implies a\mid c$ (transitivité).
$a\mid m$ et $a\mid n$ $\implies a\mid(\alpha m+\beta n)$ pour tous $\alpha,\beta\in\mathbb Z$ (combinaison linéaire).

Division euclidienne

Pour

a\in\mathbb Z

et

b\in\mathbb Z^*

, il existe un unique couple

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

tel que :

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

II

PGCD et algorithme d'Euclide

Définition

Le plus grand diviseur commun de deux entiers non nuls

a

et

b

, noté

a\wedge b

, est le plus grand entier qui divise à la fois

a

et

b

. On dit que

a

et

b

sont premiers entre eux si

a\wedge b=1

.

Propriétés du PGCD

$a\wedge a=|a|$ ; $1\wedge a=1$ ; si $b\mid a$ alors $a\wedge b=|b|$ .
$(a\wedge b)\wedge c=a\wedge(b\wedge c)$ ; $a\wedge b=a\wedge(a-b)$ .

Algorithme d'Euclide

Si $a=bq+r$ avec $0\le r<b$ , alors $a\wedge b=b\wedge r$ . En répétant les divisions euclidiennes successives, le dernier reste non nul est le PGCD cherché.

02 · Les deux théorèmes piliers

Théorèmes de Bézout et de Gauss

Deux résultats qui transforment le calcul du PGCD en équations à résoudre dans ℤ, et permettent de « simplifier » des divisibilités.

III

Théorème de Bézout

Théorème (identité de Bézout)

Soient

a,b\in\mathbb Z^*

et

d=a\wedge b

. Il existe

(u,v)\in\mathbb Z^2

tel que

d=au+bv

. En particulier :

a\wedge b=1 \iff \exists(u,v)\in\mathbb Z^2,\ au+bv=1

À retenir

Le couple

(u,v)

n'est pas unique, et la réciproque de l'identité de Bézout (sans l'hypothèse

d=a\wedge b

) est fausse en général.

Trouver u et v : remonter l'algorithme d'Euclide

On effectue les divisions euclidiennes successives, puis on exprime chaque reste en fonction de

a

et

b

en remontant les calculs jusqu'au dernier reste non nul.

IV

Théorème de Gauss et équation ax + by = c

Théorème de Gauss

Soient

a,b,c\in\mathbb Z^*

. Si

c\mid ab

et

c\wedge a=1

, alors

c\mid b

.

Conséquences

Si $a\mid c$ , $b\mid c$ et $a\wedge b=1$ , alors $ab\mid c$ .
$a\wedge b=1\iff a\wedge b^n=1$ pour tout $n\in\mathbb N^*$ .

Équation diophantienne ax + by = c

L'équation $(E):ax+by=c$ ( $a,b,c\in\mathbb Z$ , $(a,b)\neq(0,0)$ ) admet une solution dans $\mathbb Z^2$ si et seulement si $(a\wedge b)\mid c$ . Si $(x_0,y_0)$ est une solution particulière, l'ensemble des solutions est :

S=\left\{\left(x_0+\dfrac{kb}{a\wedge b},\ y_0-\dfrac{ka}{a\wedge b}\right)\ /\ k\in\mathbb Z\right\}

03 · Les briques élémentaires des entiers

Nombres premiers et décomposition en facteurs premiers

Chaque entier se construit, de façon unique, à partir des nombres premiers : la clé pour compter les diviseurs et calculer PGCD, PPCM d'un seul coup d'œil.

V

Nombres premiers

Définition

Un entier

p\ge2

est premier s'il admet exactement deux diviseurs positifs :

1

et

p

.

Propriétés

Il existe une infinité de nombres premiers.
Si $n\ge2$ n'est pas premier, il admet un diviseur premier $p$ tel que $p^2\le n$ : c'est le critère pratique pour tester la primalité d'un entier.
Si $p$ est premier et $p\mid ab$ , alors $p\mid a$ ou $p\mid b$ (conséquence du théorème de Gauss).

VI

Décomposition en facteurs premiers

Théorème fondamental

Tout entier

n\ge2

se décompose de façon unique en produit de facteurs premiers :

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

Applications directes

Le nombre de diviseurs positifs de $n$ est $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$ .
Si $a=\prod p_i^{\alpha_i}$ et $b=\prod p_i^{\beta_i}$ (mêmes facteurs premiers, exposant $0$ si absent), alors :

a\wedge b=\prod p_i^{\min(\alpha_i,\beta_i)}\qquad\text{et}\qquad a\vee b=\prod p_i^{\max(\alpha_i,\beta_i)}

et on a toujours $(a\wedge b)\times(a\vee b)=|ab|$ .

04 · Comparer les restes

Congruences modulo n

Ne retenir que le reste d'une division euclidienne : un outil redoutable pour les démonstrations de divisibilité et le calcul de grandes puissances.

VII

Définition et propriétés

Définition

Soient

a,b\in\mathbb Z

et

n\in\mathbb N^*

. On dit que

a

est congru à

b

modulo

n

, noté

a\equiv b\ [n]

, si

n\mid(b-a)

.

Propriétés fondamentales

La relation $\equiv\ [n]$ est réflexive, symétrique et transitive.
Si $a\equiv b\ [n]$ et $c\equiv d\ [n]$ , alors $a+c\equiv b+d\ [n]$ et $ac\equiv bd\ [n]$ (compatibilité avec $+$ et $\times$ ).
Si $a\equiv b\ [n]$ , alors $a^k\equiv b^k\ [n]$ pour tout $k\in\mathbb N$ .

Petit théorème de Fermat

Si

p

est premier et

a\in\mathbb Z

n'est pas divisible par

p

, alors

a^{p-1}\equiv1\ [p]

, c'est-à-dire

a^p\equiv a\ [p]

.

05 · À toi de jouer

Exercices · Arithmétique

12 exercices corrigés, niveau Sciences Mathématiques : division euclidienne, PGCD, algorithme d'Euclide, Bézout, Gauss, nombres premiers et congruences.

0 / 12 vérifiés

1

Exercice 1 · Reste d'une division euclidienne

1 démonstration

Montrer que pour tout $n\in\mathbb Z$ , le reste de la division euclidienne de $n^2$ par $4$ vaut $0$ ou $1$ .

2

Exercice 2 · Deux entiers toujours premiers entre eux

1 démonstration

Soit $n\in\mathbb N$ , $a=2n+1$ et $b=n+1$ . Montrer que $a$ et $b$ sont premiers entre eux.

3

Exercice 3 · Algorithme d'Euclide et coefficients de Bézout

1 calcul

Déterminer $1071\wedge462$ à l'aide de l'algorithme d'Euclide, puis trouver $(u,v)\in\mathbb Z^2$ tel que $1071u+462v=1071\wedge462$ .

4

Exercice 4 · Décomposition en facteurs premiers, PGCD et PPCM

1 étude

Décomposer $360$ en produit de facteurs premiers et donner le nombre de ses diviseurs positifs. Sachant que $150=2\times3\times5^2$ , calculer $360\wedge150$ et $360\vee150$ .

5

Exercice 5 · Équation diophantienne

1 équation

Résoudre dans $\mathbb Z^2$ l'équation $15x+9y=12$ .

6

Exercice 6 · Congruence linéaire

1 équation

Résoudre dans $\mathbb Z$ la congruence $7x\equiv3\ [12]$ .

7

Exercice 7 · Divisibilité par congruence

1 démonstration

Montrer que pour tout $n\in\mathbb N$ , $3^{2n+1}+2^{n+2}$ est divisible par $7$ .

8

Exercice 8 · Petit théorème de Fermat

1 calcul

Déterminer le reste de la division euclidienne de $7^{100}$ par $5$ .

9

Exercice 9 · Diviseurs communs dépendant d'un paramètre

1 étude

Soit $n\in\mathbb N$ , $a=2n+3$ et $b=4n+1$ . 1) Montrer que tout diviseur commun de $a$ et $b$ divise $5$ . 2) En déduire $a\wedge b$ selon les valeurs de $n$ .

10

Exercice 10 · Test de primalité

1 démonstration

Montrer que $191$ est un nombre premier.

11

Exercice 11 · Équation avec une différence de carrés

1 équation

Résoudre dans $\mathbb N^2$ l'équation $x^2-y^2=45$ avec $x>y>0$ .

12

Exercice 12 · Équation dans ℤ/7ℤ

1 équation

Résoudre dans $\mathbb Z/7\mathbb Z$ l'équation $3\bar x=\bar5$ .