Mathématiques au lycée/Arithmétique

Un livre de Wikibooks.

< Mathématiques au lycée

Aller à : Navigation, rechercher

Contenu transféré sur Wikiversité

Le contenu que vous recherchez a été déplacé vers la Wikiversité. Il devrait être disponible sous le nom Arithmétique.

[modifier] Divisibilité et congruences dans Z

[modifier] Multiples d'un entier relatif

Définition

L'entier relatif $a\,$ est un multiple de l'entier relatif $b\,$ si et seulement si $\exists q \in \mathbb{Z}^*, a = bq$ .

Remarques :

Tout entier relatif est multiple de $1\,$ et de $-1\,$
$0\,$ n'admet qu'un multiple : lui-même
$0\,$ est multiple de tout entier

[modifier] Divisibilité dans Z

Définition

$a\,$ et $b\,$ désignent 2 entiers relatifs.
Dire que $b\,$ divise $a\,$ signifie qu'il existe un entier relatif $c\,$ tel que $a = bc\,$ .

Vocabulaire : « b divise a » $\Leftrightarrow$ « b est un diviseur de a » $\Leftrightarrow$ « a est un multiple de b ».

Notation : « b divise a » $\Leftrightarrow$ $b|a\,$

Exemples :

17 divise -153 car $-153 = 17\times(-9)$
$\forall n \in \mathbb{Z}, (n+1)|(n^2-1)$

Démonstration

$(n-1) \in \mathbb{Z}$ et $n^2-1 = (n-1)(n+1)\,$

Propriétés : $(a,b,c) \in \mathbb{Z}^{*3}$

$\begin{align} a|a \\ 1|a \\ -1|a \\ -a|a \end{align}$
$a|b\,$ et $b|a \Leftrightarrow a = b$ ou $a = -b\,$

Démonstration

$a|b \Leftrightarrow \exists q_1 \in \mathbb{Z}^*, b = q_1a$
$b|a \Leftrightarrow \exists q_2 \in \mathbb{Z}^*, a = q_2b$
d'où $b = q_1(q_2b) \Leftrightarrow b(1-q_1q_2) = 0 \Rightarrow 1-q_1q_2 = 0 \Rightarrow q_1q_2 = 1$
d'où $q_1\,$ et $q_2\,$ sont des diviseurs de 1 $\Rightarrow q_1 \in \left \{ -1;1 \right \}, q_2 \in \left \{ -1;1 \right \}$

transitivité $\forall (a,b,c) \in \mathbb{Z}^{*3}$

Si $a|b\,$ et $b|c\,$ , alors $a|c\,$ .

Démonstration

$a|b \Leftrightarrow b = aq_1$ avec $q_1 \in \mathbb{Z}^*$
$b|c \Leftrightarrow c = bq_2$ avec $q_2 \in \mathbb{Z}^*$
$\Rightarrow c = aq_1q_2 \Rightarrow a|c$

combinaison linéaire $\forall (a,b) \in \mathbb{Z}^2$ et $\forall q \in \mathbb{Z}^*$

Si $q|a\,$ et $q|b\,$ alors

$q|(a+b)\,$
$q|(a-b)\,$
plus généralement, $\forall (m,n) \in \mathbb{Z}^2, q|(ma+nb)$

[modifier] Division euclidienne

Définition

Pour tout dividende « a » entier relatif et diviseur « b » entier relatif non nul, il existe un unique quotient « q » et un unique reste « r » tels que le dividende soit égal à la multiplication du diviseur par le quotient plus le reste avec le reste positif et strictement inférieur à la valeur absolue du diviseur.

En langage mathématiques, cette définition est $\forall (a,b) \in (\mathbb{Z} \times {\mathbb{Z}}^*), \exists !(q,r) \in (\mathbb{Z} \times\mathbb{N})$ tels que $\begin{cases} a = b \times q + r \\ 0 \le r < |b| \end{cases}$

Démonstration de l'unicité du couple (q,r)

Soient $(q,r),~(q',r')$ dans $\mathbb{Z}^2$ tels que : $\begin{cases} a = b \times q + r \\ 0 \le r < b \end{cases}$ et $~\begin{cases} a = b \times q' + r' \\ 0 \le r' < b \end{cases}$
Alors $b \times (q - q') = r' - r$
et $~-b < r' - r < b$ ,
d'où $~-1 < q - q' < 1$ ,
et donc $~q' = q$ , $~r' = r$

 est la division euclidienne de 101 par 4 ou la division euclidienne de 101 par 25.
 ne traduit pas la division euclidienne de 34 par 10. En effet, on a pas l'inégalité .

Exemple : Division euclidienne

[modifier] Congruences

La relation de congruence ne ressemble pas aux relations habituelles, en effet les relations que nous utilisons depuis que nous faisons des mathématiques (=, <, > ...) comparent deux nombres alors que la relation de congruence compare les restes des deux nombres étudiés.

Définition

Deux entiers relatifs sont congrus modulo n (avec n un entier naturel) si et seulement s'ils ont même reste dans la division euclidienne par n.

En langage mathématique, $\text{Pour }n \in \mathbb{N},\text{ pour }(a,b) \in \mathbb{Z}^2, \exists (q_1, q_2, r) \in \mathbb{N}^3, a \equiv b [n] \Leftrightarrow \begin{cases} b = n \times q_1 + r \\ a = n \times q_2 + r \\ 0 \le r < n \end{cases}$

Les notations changent d'un professeur à l'autre mais elles désignent toutes la même chose:

$a \equiv b [n]$
$a \equiv b (n)$
$a \equiv b (\text{mod n})$
$a \equiv b (\text{modulo n})$

Il existe une seconde définition qui est parfois utilisée.

Définition

Deux entiers relatifs sont congrus modulo n (avec n un entier naturel) si et seulement si n divise la différence de ces deux nombres.

En langage mathématique, $\text{Pour }n \in \mathbb{N},\text{ pour }(a,b) \in \mathbb{Z}^2, a \equiv b [n] \Leftrightarrow n |(a-b)$

De la même manière, comme il a été précisé dans le paragraphe Divisibilité dans Z, on peut tout autant dire:

n divise a-b
a-b est multiple de n

Démonstration de la seconde définition

$\forall (r,n) \in (\mathbb{N\times N^*}), \forall (q_1,q_2) \in \mathbb{Z}^2$

On sait que $a \equiv b [n] \Leftrightarrow \begin{cases} b = n \times q_1 + r \\ a = n \times q_2 + r \\ 0 \le r < n \end{cases}$ .

On a $a - b = n (q_1 - q_2) + r - r = n (q_1 - q_2)\,$ et $q_1 - q_2\,$ est un entier car les quotients sont des entiers, donc a - b est un multiple de n.

On peut vérifier que r soit bien le même reste pour les deux divisions euclidiennes.

$a - b = k \times n$ (avec $k \in \mathbb{Z}$ ) et $a = n \times q_1 + r$ (avec $0 \le r < n$ ).

On remplace a, $b = a - k \times n = n \times q_1 + r - k \times n = n \times (q_1 - k) + r = n \times q_2 + r$ (avec $0 \le r < n$ ).

r est bien le reste de b dans la division euclidienne par n.

Quel est le reste de  dans la division par 7 ?
On a  et 
Donc .

Exemple : Exemple de congruence

[modifier] Propriétés des congruences

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

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

(1) $a+c \equiv b+d[n]$
$a-c \equiv b-d[n]$
(2) $ac \equiv bd[n]$
(3) $\forall p \in \mathbb{N}, a^p \equiv b^p[n]$

Démonstration

Démos des (1) (2) (3) à faire.

Quel est le reste de la division de  par 7 ?


Or  et 
En multipliant membre à membre : 
Le reste de la division de  par 7 est donc 2.

Exemple : Exemple de congruence

[modifier] PGCD

[modifier] Diviseurs communs à 2 entiers naturels

2 entiers naturels non nuls ont toujours un nombre fini de diviseurs et donc de diviseurs communs (dont -1 et 1). Il existe donc un diviseur commun à ces 2 nombres plus grand que les autres.

Définition

$\forall (a,b) \in \mathbb{N}^{*2}$ , le PGCD de a et b est noté $pgcd(a,b)\,$

Conséquence : $b|a \Leftrightarrow pgcd(a,b) = b$

[modifier] Lemme d'Euclide

Définition

$(a,b) \in \mathbb{N}^{*2}$
Si des entiers naturels q et r, avec $r \ne 0\,$ , sont tels que $a = bq+r\,$ , alors :
$pgcd(a,b) = pgcd(b,r)\,$

Démonstration

d désigne un diviseur commun à a et b. De $r = a-bq\,$ , on en déduit que d divise r. Ainsi tout diviseur commun à a et b est un diviseur commun à b et r.
Réciproquement, d' désigne un diviseur commun à b et r. De $a = bq+r\,$ , on déduit que d' divise a. Ainsi tout diviseur commun à b et r est un diviseur commun à a et b.
En conclusion, a et b ont les mêmes diviseurs communs que b et r donc $pgcd(a,b) = pgcd(b,r)\,$

[modifier] Algorithme d'Euclide

[modifier] Propriétés du PGCD

[modifier] Extension du PGCD aux entiers relatifs

[modifier] Nombres premiers entre eux

Définition

Nous dirons que deux nombres sont premiers entre eux si et seulement si leur pgcd vaut $1$ .

En d'autres termes, deux nombres $x$ et $y$ sont premiers entre eux si et seulement si pgcd $(x, y) = 1$ .

[modifier] Nombres premiers

[modifier] Définition

Définition

Un nombre naturel n est premier s'il possède exactement 2 diviseurs, 1 et lui-même.

Les premiers nombres premiers sont : $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ . Nous remarquons que le nombre $1$ n'est pas dans cette liste et pourtant les diviseurs du nombre $1$ sont $1$ et lui-même, mais nous ne considérons pas ce nombre comme un nombre premier.

[modifier] Propriété des entiers naturels

Proposition

Tout entier naturel $n$ admet au moins un diviseur premier.

Démonstration C'est assez évident. Nous distinguerons deux cas :

Supposons que $n$ est premier. Alors par définition des nombres premiers, $n$ admet uniquement $1$ et lui-même, c'est-à-dire $n$ , comme diviseur. Or $n$ est premier donc $n$ admet bien un diviseur premier ;
Supposons maintenant que $n$ n'est pas premier, alors $n$ admet d'autres diviseurs compris strictement entre $1$ et $n$ . Supposons qu'un de ces diviseurs est $m$ , alors si $m$ et premier, $n$ admet bien un diviseur premier $m$ . Sinon, si $m$ n'est pas premier, il est divisible par au moins un autre nombre $p$ tel que $1 < p < m < n$ . Si $p$ est un nombre premier, alors $p | m$ et comme $m | n$ alors $p | n$ et $n$ admet un diviseur premier. Sinon, si $p$ n'est pas premier on recommence le raisonnement jusqu'à trouver un nombre premier. Comme cette suite de nombres est décroissante et bornée par $1$ , nous trouverons bien un nombre premier qui divisera $n$ .

[modifier] Critère de primalité

Si un entier naturel n n'est pas divisible par aucun nombre premier dont le carré lui est inférieur ou égal, alors n est premier.

Application : tant que $q < \sqrt{n}\,$ , on tente la division de n par q.

127 premier ? 
les nombres premiers inférieurs ou égaux à 11 sont : 





 127 est premier

Exemple : Exemple d'utilisation du critère de primalité

[modifier] Ensemble des nombres premiers

Théorème : Il existe une infinité de nombres premiers.

Démonstration par l'absurde :
On suppose qu'il existe un nombre fini de nombres premiers. Soient $p_1,p_2,p_3,...,p_n\,$ ces nombres premiers.
Soit $N = p_1\times p_2\times...\times p_n +1$ , N n'est pas premier car $\forall j \in \left \{ 1,2,...,n \right \}, N > P_j$ .
Il est donc divisible par l'un des nombres premiers au moins.
Soit j tel que $p_j|N\,$
$\begin{align} \\ N = p_j\times q (q\in\mathbb{N}) \\ p_j\times q = p_1\times p_2\times ...\times p_j\times ...\times p_n+1 \\ p_j\left (q-p_1\times p_2\times ...\times p_{j-1}\times p_{j+1}\times ...\times p_n \right) = 1 \\ \Rightarrow p_j|1 \end{align}$
or $p_j\,$ est premier : contradiction