Arithmétique

 

ILa divisibilité

ALes diviseurs

Soient $\displaystyle{a}$ et $\displaystyle{b}$ deux entiers relatifs, avec $\displaystyle{b}$ non nul.
L'entier $\displaystyle{a}$ est divisible par $\displaystyle{b}$ si et seulement s'il existe un entier relatif $\displaystyle{k}$ tel que :
$$a = kb$$

Les propositions suivantes sont équivalentes :

  • $\displaystyle{a}$ est divisible par $\displaystyle{b}$ ;
  • $\displaystyle{b}$ est un diviseur de $\displaystyle{a}$ ;
  • $\displaystyle{b}$ divise $\displaystyle{a}$.
  • Si $\displaystyle{b}$ divise $\displaystyle{a}$, alors $\displaystyle{- b}$ divise $\displaystyle{a}$.
  • Si $\displaystyle{d}$ divise les entiers $\displaystyle{a}$ et $\displaystyle{b}$, il divise alors toute cominaison linéaire de $\displaystyle{a}$ et de $\displaystyle{b}$ : $\displaystyle{ka + k'b}$, avec $\displaystyle{k}$ et $\displaystyle{k'}$ entiers relatifs.
$\displaystyle{4}$ divise $\displaystyle{16}$ et $\displaystyle{24}$, donc $\displaystyle{4}$ divise $\displaystyle{71 \times 16 - 13 \times 24}$.

BLes multiples

L'entier $\displaystyle{a}$ est un multiple de $\displaystyle{b}$ si et seulement si $\displaystyle{b}$ est un diviseur de $\displaystyle{a}$.
$\displaystyle{81}$ est un multiple de $\displaystyle{9}$, et $\displaystyle{9}$ est un diviseur de $\displaystyle{81}$.
  • Si $\displaystyle{a}$ est un multiple de $\displaystyle{b}$, alors $\displaystyle{- a}$ est un multiple de $\displaystyle{b}$.
  • La somme et / ou la différence de multiples de $\displaystyle{b}$ est un multiple de $\displaystyle{b}$.
  • Si $\displaystyle{a}$ est un multiple de $\displaystyle{b}$, alors $\displaystyle{ka}$ est un multiple de $\displaystyle{b}$ ($\displaystyle{k}$ entier relatif).

CLa division euclidienne

Soient $\displaystyle{a}$ et $\displaystyle{b}$ deux entiers relatifs, avec $\displaystyle{b}$ non nul.
Il existe un unique couple d'entiers relatifs $\displaystyle{(q ; r)}$ tel que :

$\displaystyle{a = bq + r}$ et $\displaystyle{0 \leqslant r \lt b}$

 

  • L'entier $\displaystyle{q}$ est le quotient de la division euclidienne de $\displaystyle{a}$ par $\displaystyle{b}$.
  • L'entier $\displaystyle{r}$ est le reste de la division euclidienne de $\displaystyle{a}$ par $\displaystyle{b}$.
La division euclidienne de $\displaystyle{103}$ par $\displaystyle{12}$ est : $\displaystyle{103 = 12 \times 8 + 7}$

Dans cet exemple, $\displaystyle{q = 8}$ et $\displaystyle{r = 7}$.

DLe PGCD

Le plus grand diviseur commun de $\displaystyle{a}$ et de $\displaystyle{b}$, noté PGCD($\displaystyle{a ; b}$), est le plus grand entier naturel qui divise à la fois $\displaystyle{a}$ et $\displaystyle{b}$.

On veut déterminer le PGCD($\displaystyle{ 12;30 }$).

On recherche les diviseurs communs à $\displaystyle{12}$ et $\displaystyle{30}$ :

  • Les diviseurs de $\displaystyle{12}$ sont : $\displaystyle{\color{Red}{1}}$, $\displaystyle{\color{Red}{2}}$, $\displaystyle{\color{Red}{3}}$, $\displaystyle{4}$, $\displaystyle{\color{Red}{6}}$, $\displaystyle{12}$
  • Les diviseurs de $\displaystyle{30}$ sont : $\displaystyle{\color{Red}{1}}$, $\displaystyle{\color{Red}{2}}$, $\displaystyle{\color{Red}{3}}$, $\displaystyle{5}$, $\displaystyle{\color{Red}{6}}$, $\displaystyle{10}$, $\displaystyle{15}$, $\displaystyle{30}$

Les diviseurs communs à $\displaystyle{12}$ et $\displaystyle{30}$ sont donc les nombres : $\displaystyle{1}$, $\displaystyle{2}$, $\displaystyle{3}$ et $\displaystyle{6}$.

Parmi ceux-ci le plus grand étant $\displaystyle{6}$, on en déduit que PGCD($\displaystyle{ 12;30 }$) $\displaystyle{= 6}$.

Pour déterminer le PGCD de deux nombres, on peut procéder par divisions euclidiennes successives, d'après l'algorithme d'Euclide.
Soit $\displaystyle{d}$ = PGCD($\displaystyle{a ; b}$).
Il existe alors deux entiers $\displaystyle{a'}$ et $\displaystyle{b'}$ tels que :
$\displaystyle{a = da'}$ et $\displaystyle{b = db'}$
Soit $\displaystyle{d}$ = PGCD($\displaystyle{a ; b}$).
L'ensemble des diviseurs communs à $\displaystyle{a}$ et $\displaystyle{b}$ est l'ensemble des diviseurs de $\displaystyle{d}$.

IILes nombres premiers

ALa définition

Un entier naturel est premier si et seulement s'il admet exactement deux diviseurs positifs : $\displaystyle{1}$ et lui-même.
L'entier $\displaystyle{1}$ n'admet qu'un seul diviseur positif ($\displaystyle{1}$), il n'est donc pas premier.
Il existe une infinité de nombres premiers.
Tout entier supérieur ou égal à $\displaystyle{2}$ admet au moins un diviseur premier.
Si $\displaystyle{a}$ n'est pas premier, il admet alors au moins un diviseur premier $\displaystyle{p}$ tel que :
$$2 \leqslant p \leqslant \sqrt{a} $$

BLa décomposition

Soient $\displaystyle{a}$ un entier naturel supérieur ou égal à $\displaystyle{2}$, $\displaystyle{(p_{1}, p_{2},..., p_{r})}$ des nombres premiers deux à deux distincts, $\displaystyle{(\alpha_{1}, \alpha_{2},..., \alpha_{r})}$ des entiers naturels non nuls.
On peut décomposer $\displaystyle{a}$ comme un unique produit de facteurs premiers :
$$a = p_{1}^{\alpha_{1}} \times p_{2}^{\alpha_{2}} \times... \times p_{r}^{\alpha_{r}}$$
On décompose le nombre $\displaystyle{60}$ sous la forme d'un produit de facteurs premiers :

$\displaystyle{60 = 6 \times 10}$

$\displaystyle{60 = 2 \times 3 \times 2 \times 5}$

$\displaystyle{60 = 2^2 \times 3 \times 5}$

Les entiers $\displaystyle{2}$, $\displaystyle{3}$ et $\displaystyle{5}$ sont bien premiers.

CLes nombres premiers entre eux

Deux entiers sont premiers entre eux si et seulement si leur seul diviseur positif commun est $\displaystyle{1}$.
Les nombres $\displaystyle{15}$ et $\displaystyle{28}$ n'ayant pas d'autre diviseur commun que $\displaystyle{1}$, ils sont premiers entre eux.
D'après le théorème de Bezout, les entiers $\displaystyle{a}$ et $\displaystyle{b}$ sont premiers entre eux si et seulement s'il existe des entiers $\displaystyle{u}$ et $\displaystyle{v}$ tels que :
$$ua + vb = 1$$
Soient $\displaystyle{a}$, $\displaystyle{b}$ et $\displaystyle{c}$ trois entiers.
D'après le théorème de Gauss, si $\displaystyle{c}$ divise $\displaystyle{ab}$ et $\displaystyle{c}$ premier avec $\displaystyle{a}$, alors $\displaystyle{c}$ divise $\displaystyle{b}$.

IIILes congruences

ALa caractérisation

Soient $\displaystyle{a}$ et $\displaystyle{b}$ deux entiers et $\displaystyle{n}$ un entier naturel supérieur ou égal à $\displaystyle{2}$.
On dit que $\displaystyle{a}$ est congru à $\displaystyle{b}$ modulo $\displaystyle{n}$, noté $\displaystyle{a \equiv b [n]}$, si et seulement si :
$\displaystyle{a - b}$ est multiple de $\displaystyle{n}$
On peut écrire que $\displaystyle{51 \equiv 27 [6]}$ car $\displaystyle{51-27 = 24}$ et $\displaystyle{24}$ est multiple de $\displaystyle{6}$.
On peut également écrire $\displaystyle{51 \equiv 27 [4]}$, $\displaystyle{51 \equiv 27 [2]}$, $\displaystyle{51 \equiv 27 [24]}$...
$\displaystyle{a \equiv b [n] \Leftrightarrow a}$ et $\displaystyle{b}$ ont le même reste dans la division euclidienne par $\displaystyle{n}$.
L'entier $\displaystyle{a}$ est divisible par $\displaystyle{b}$ (supérieur ou égal à $\displaystyle{2}$) si et seulement si $\displaystyle{a \equiv 0 [b]}$.

BLes opérations

Soient $\displaystyle{n}$ un entier naturel supérieur ou égal à $\displaystyle{2}$, $\displaystyle{a}$, $\displaystyle{a'}$, $\displaystyle{b}$ et $\displaystyle{b'}$ des entiers relatifs tels que $\displaystyle{a \equiv a' [n]}$ et $\displaystyle{b \equiv b' [n]}$, alors :

  • $\displaystyle{a + b \equiv a' + b' [n]}$
  • $\displaystyle{a - b \equiv a' - b' [n]}$
  • $\displaystyle{ab \equiv a'b' [n]}$
  • $\displaystyle{a^{k} \equiv a'^{k} [n]}$ ($\displaystyle{k}$ entier naturel non nul)
  • Vues: 1993

Rechercher