Maths expertes
Arithmetique
En Premiere, vous avez deja manipule les multiples, les diviseurs et les nombres premiers. En math expertes, on reprend ces idees pour aller plus loin : prouver des divisibilites, calculer des PGCD et resoudre des equations avec des entiers.
Version HTML statique du cours. Si JavaScript est actif, MathSups affiche l’expérience interactive avec QCM, exercices guidés et assistant IA.
Rappels de Premiere et vocabulaire
En Premiere, vous avez deja manipule les multiples, les diviseurs et les nombres premiers. En math expertes, on reprend ces idees pour aller plus loin : prouver des divisibilites, calculer des PGCD et resoudre des equations avec des entiers.
Divisibilite
Soient deux entiers relatifs $a$ et $b$. On dit que $a$ divise $b$, note $a \mid b$, s'il existe un entier $k$ tel que $b = ak$.
Autrement dit, $b$ est un multiple de $a$.
Exemple : $3 \mid 12$ car $12 = 3 \times 4$. En revanche $5 \nmid 12$.
On utilise souvent les consequences suivantes : si $a \mid b$ et $a \mid c$, alors $a \mid (ub+vc)$ pour tous entiers $u$ et $v$. En particulier, si $a \mid b$, alors $a \mid (-b)$.
Le bon reflexe est donc de transformer une divisibilite en combinaison lineaire quand on veut reutiliser plusieurs informations en meme temps.
Quelques criteres utiles
On utilise souvent des criteres rapides :
- $2 \mid n$ si le chiffre des unites de $n$ est pair.
- $5 \mid n$ si le chiffre des unites est $0$ ou $5$.
- $3 \mid n$ si la somme des chiffres est divisible par $3$.
- $9 \mid n$ si la somme des chiffres est divisible par $9$.
Ces criteres servent surtout a tester vite une divisibilite avant un calcul plus long.
Divisibilite et combinaisons lineaires
Si $c \mid a$ et $c \mid b$, alors pour tous entiers $m$ et $n$ :
$$c \mid (ma + nb).$$
Demonstration : Puisque $c \mid a$, il existe $k_1$ tel que $a = ck_1$. Puisque $c \mid b$, il existe $k_2$ tel que $b = ck_2$. Alors $ma + nb = c(mk_1 + nk_2)$, donc $c$ divise $ma + nb$.
Exemple : $3 \mid 12$ et $3 \mid 9$, donc $3 \mid (2 \times 12 - 5 \times 9) = -21$.
Exemple de verification
Le nombre $483$ est-il divisible par $3$ ?
On calcule la somme des chiffres : $4+8+3 = 15$.
Or $15$ est divisible par $3$, donc $483$ est divisible par $3$.
En effet, $483 = 3 \times 161$.
Division euclidienne et PGCD
La division euclidienne permet de decomposer un entier en quotient et reste. Elle est la base de l'algorithme d'Euclide, qui calcule efficacement un PGCD.
Division euclidienne
Pour tout entier $a$ et tout entier naturel non nul $b$, il existe un unique couple $(q,r)$ tel que :
$$a = bq + r \quad \text{avec} \quad 0 \le r < b.$$
$q$ est le quotient et $r$ le reste.
Exemple : $37 = 5 \times 7 + 2$. Le quotient est $7$ et le reste est $2$.
PGCD
Le PGCD de deux entiers non nuls $a$ et $b$ est le plus grand entier positif qui divise a la fois $a$ et $b$.
On le note $\mathrm{PGCD}(a,b)$ ou $a \wedge b$.
Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$.
PPCM
Le PPCM (Plus Petit Commun Multiple) de deux entiers naturels non nuls $a$ et $b$ est le plus petit entier strictement positif qui est a la fois multiple de $a$ et de $b$.
On le note $\mathrm{PPCM}(a,b)$.
Exemple : $\mathrm{PPCM}(4,6)=12$.
Lien PGCD-PPCM
Pour tous entiers naturels non nuls $a$ et $b$ :
$$\mathrm{PGCD}(a,b) \times \mathrm{PPCM}(a,b) = a \times b.$$
Cette relation permet de calculer le PPCM apres avoir trouve le PGCD par l algorithme d Euclide.
Exemple : $\mathrm{PGCD}(4,6)=2$, donc $\mathrm{PPCM}(4,6)=\frac{4 \times 6}{2}=12$.
Algorithme d Euclide
Pour calculer le PGCD de deux entiers, on effectue des divisions euclidiennes successives :
$$a = bq_1 + r_1$$
$$b = r_1 q_2 + r_2$$
$$r_1 = r_2 q_3 + r_3$$
On continue jusqu'a obtenir un reste nul. Le dernier reste non nul est le PGCD.
Idee : on remplace sans perdre d'information le couple $(a,b)$ par des restes de plus en plus petits.
Le point cle a retenir est l invariant suivant : si $a=bq+r$, alors $$\mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,r).$$ C est cette propriete qui autorise les divisions successives jusqu au reste nul.
Exemple complet
Calculons $\mathrm{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$, donc $\mathrm{PGCD}(252,198)=18$.
Lire le PGCD dans la division euclidienne
Si $$a=bq+r,$$ alors tout diviseur commun de $a$ et $b$ divise aussi $r=a-bq$, et tout diviseur commun de $b$ et $r$ divise aussi $a=bq+r$.
On en deduit la formule fondamentale :
$$\mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,r).$$
C est la justification theorique de l algorithme d Euclide.
Bezout et Gauss
Les theoremes de Bezout et de Gauss sont centraux. Ils permettent de relier PGCD, combinaisons lineaires et divisibilite.
Theoreme de Bezout
Deux entiers $a$ et $b$ non tous les deux nuls sont premiers entre eux si et seulement s'il existe deux entiers $x$ et $y$ tels que :
$$ax + by = 1.$$
Plus generalement, il existe toujours des entiers $x$ et $y$ tels que :
$$ax + by = \mathrm{PGCD}(a,b).$$
Theoreme de Gauss
Si $a \mid bc$ et si $\mathrm{PGCD}(a,b)=1$, alors $a \mid c$.
C'est un outil tres utile pour demontrer des divisibilites et factoriser des equations.
Trouver une relation de Bezout
On part de l'algorithme d'Euclide, puis on remonte les egalites pour exprimer le PGCD comme combinaison lineaire de $a$ et $b$.
Idee : le dernier reste non nul est ecrit comme une combinaison de l'etape precedente, puis on remplace recursivement jusqu'aux nombres de depart.
Exemple de Bezout
Pour $252$ et $198$, on a trouve $\mathrm{PGCD}(252,198)=18$.
En remontant les egalites de l'algorithme d'Euclide, on obtient par exemple :
$$18 = 4 \times 252 - 5 \times 198.$$
Donc $18$ est bien une combinaison lineaire de $252$ et $198$.
Equations diophantiennes simples
Une equation diophantienne est une equation dont on cherche des solutions entieres. En Terminale, on traite surtout les equations lineaires a deux inconnues.
Equation diophantienne lineaire
Une equation de la forme $ax + by = c$ avec $x$ et $y$ entiers est une equation diophantienne lineaire.
Elle admet des solutions si et seulement si $\mathrm{PGCD}(a,b)$ divise $c$.
Principe de resolution
Si $d = \mathrm{PGCD}(a,b)$ et si $d \mid c$, on ecrit d'abord une solution particuliere de $ax+by=d$, puis on multiplie par $c/d$.
Ensuite, on decrit toutes les solutions a partir d'une solution particuliere.
Toutes les solutions
Si $(x_0,y_0)$ est une solution particuliere de $ax + by = c$, alors toutes les solutions sont donnees par :
$$x = x_0 + \frac{b}{d}t \quad \text{et} \quad y = y_0 - \frac{a}{d}t$$
ou $d = \mathrm{PGCD}(a,b)$ et $t \in \mathbb{Z}$.
Exemple de resolution
Resolvons $18x + 30y = 6$.
On a $\mathrm{PGCD}(18,30)=6$, donc l'equation admet des solutions.
En divisant par $6$, on obtient $3x + 5y = 1$.
Une solution particuliere est $x=2$, $y=-1$ car $3\times2 + 5\times(-1)=1$.
Donc toutes les solutions sont :
$$x = 2 + 5t \quad \text{et} \quad y = -1 - 3t, \quad t \in \mathbb{Z}.$$
Verifier d abord l existence
Pour l equation $$ax+by=c,$$ il est inutile de chercher une solution si $$d=\mathrm{PGCD}(a,b)$$ ne divise pas $c$.
Exemple : $$6x+9y=5$$ n admet aucune solution entiere car $$\mathrm{PGCD}(6,9)=3$$ et $$3 \nmid 5.$$
Le premier reflexe est donc toujours : calculer le PGCD, puis tester la divisibilite du second membre.
QCM du chapitre
-
Question 1. Si $7 \mid 63$, alors :
- A. 63 est un multiple de 7
- B. 7 est un multiple de 63
- C. 63 est premier
- D. 7 divise 8
Réponse. A. 63 est un multiple de 7
Explication. L ecriture $7 \mid 63$ signifie que 63 est un multiple de 7.
-
Question 2. La division euclidienne de 29 par 4 donne :
- A. $29 = 4 \times 7 + 1$
- B. $29 = 4 \times 6 + 5$
- C. $29 = 4 \times 8 - 3$
- D. $29 = 4 \times 5 + 9$
Réponse. A. $29 = 4 \times 7 + 1$
Explication. Le quotient est 7 et le reste est 1, avec un reste toujours inferieur a 4.
-
Question 3. Si $\mathrm{PGCD}(a,b)=1$, alors :
- A. a et b sont egaux
- B. a et b sont premiers entre eux
- C. a et b sont premiers
- D. a divise b
Réponse. B. a et b sont premiers entre eux
Explication. Le PGCD vaut 1 exactement lorsque les deux entiers sont premiers entre eux.
-
Question 4. Le theoreme de Bezout affirme que pour $a$ et $b$ premiers entre eux, on peut ecrire :
- A. $ax + by = 0$
- B. $ax + by = 1$
- C. $ax = by$
- D. $a+b=1$
Réponse. B. $ax + by = 1$
Explication. C est la forme fondamentale du theoreme de Bezout.
-
Question 5. Si $\mathrm{PGCD}(a,b)=d$, l equation $ax + by = c$ admet des solutions entieres seulement si :
- A. d divise c
- B. a divise b
- C. c divise d
- D. a = b
Réponse. A. d divise c
Explication. La condition necessaire et suffisante est que le PGCD divise le second membre.
-
Question 6. Le theoreme de Gauss dit que si $a \mid bc$ et $\mathrm{PGCD}(a,b)=1$, alors :
- A. a divise c
- B. b divise a
- C. c divise b
- D. a = b
Réponse. A. a divise c
Explication. Lorsque a et b sont premiers entre eux, la divisibilite de bc par a force a diviser c.
Exercices guidés
Exercice 1. Calculer un PGCD et une relation de Bezout
-
Étape 1. Faire l algorithme d Euclide.
On enchaine les divisions :
$$120 = 84 \times 1 + 36$$
$$84 = 36 \times 2 + 12$$
$$36 = 12 \times 3 + 0$$
Donc $\mathrm{PGCD}(120,84)=12$.
-
Étape 2. Remonter les egalites pour exprimer 12.
On a $12 = 84 - 36 \times 2$ puis $36 = 120 - 84$.
Donc :
$$12 = 84 - 2(120 - 84) = 3 \times 84 - 2 \times 120.$$
Exercice 2. Resoudre une equation diophantienne
-
Étape 1. Verifier la condition d existence.
On calcule $\mathrm{PGCD}(15,21)=3$.
Comme $3 \mid 6$, l equation admet des solutions entieres.
-
Étape 2. Simplifier l equation.
On divise par 3 :
$$5x + 7y = 2.$$
Une solution particuliere est $x=6$, $y=-4$ car $5\times6 + 7\times(-4)=30-28=2$.
-
Étape 3. Ecrire toutes les solutions.
Les solutions sont :
$$x = 6 + 7t \quad \text{et} \quad y = -4 - 5t, \quad t \in \mathbb{Z}.$$
Exercice 3. Calculer un PGCD puis remonter Bezout
\mathrm{PGCD}(64,35),\quad 64u+35v=1
-
Étape 1. Appliquer l algorithme d Euclide.
On calcule : $$64=35\times1+29,$$ $$35=29\times1+6,$$ $$29=6\times4+5,$$ $$6=5\times1+1.$$ Le dernier reste non nul est $$1$$.\mathrm{PGCD}(64,35)=1 -
Étape 2. Remonter les egalites.
On a $$1=6-5=6-(29-4\times6)=5\times6-29.$$ Puis $$6=35-29,$$ donc $$1=5\times35-6\times29.$$ Enfin $$29=64-35,$$ donc $$1=-6\times64+11\times35.$$ -
Étape 3. Conclure.
On peut prendre $$u=-6$$ et $$v=11.$$u=-6,\quad v=11
Exercice 4. Utiliser Gauss dans une preuve de divisibilite
6\mid n,\ 35\mid n\Rightarrow 210\mid n
-
Étape 1. Verifier que 6 et 35 sont premiers entre eux.
On a $$6=2\times3$$ et $$35=5\times7,$$ donc $$\mathrm{PGCD}(6,35)=1.$$ -
Étape 2. Traduire une des deux divisibilites.
Comme $$35\mid n,$$ il existe un entier $$k$$ tel que $$n=35k.$$ Comme $$6\mid n,$$ on a alors $$6\mid35k.$$ -
Étape 3. Appliquer Gauss et conclure.
Puisque $$\mathrm{PGCD}(6,35)=1$$ et $$6\mid35k,$$ le theoreme de Gauss donne $$6\mid k.$$ Donc $$k=6t$$ puis $$n=35\times6t=210t.$$ Ainsi $$210\mid n.$$
Exercice 5. Resoudre une equation diophantienne dans $\mathbb N$
18x+30y=78
-
Étape 1. Verifier la condition d existence.
On a $$\mathrm{PGCD}(18,30)=6$$ et $$6\mid78,$$ donc il existe des solutions entieres. -
Étape 2. Simplifier et trouver une solution particuliere.
En divisant par 6, on obtient $$3x+5y=13.$$ Une solution particuliere est $$(6,-1)$$.3x+5y=13
-
Étape 3. Ecrire toutes les solutions entieres.
Toutes les solutions sont $$x=6+5t,\quad y=-1-3t,\quad t\in\mathbb Z.$$ -
Étape 4. Imposer $$x\ge0$$ et $$y\ge0$$.
Les conditions donnent $$t\ge-1$$ et $$t\le-1,$$ donc $$t=-1.$$ La seule solution dans $$\mathbb N$$ est $$x=1,\ y=2.$$(x,y)=(1,2)