Les entiers naturels et notions d'arithmétique

L'ensemble ${\mathbb{N}}^{\ast }$ désigne l'ensemble des entiers naturels non nuls :

Pour tous entiers naturels $a$ et $b$ :

• la somme $a+b$ est un entier naturel ;
• le produit $a\times b$ est un entier naturel ;
• en revanche, la différence $a-b$ n'est pas toujours un entier naturel (par exemple $3-5=-2\notin \mathbb{N}$).

Soient $a\in \mathbb{N}$ et $b\in {\mathbb{N}}^{\ast }$. Il existe un unique couple $(q,r)$ d'entiers naturels tel que

L'entier $q$ est appelé le quotient et l'entier $r$ le reste de la division euclidienne de $a$ par $b$.

Division de $47$ par $6$ : on cherche le plus grand multiple de $6$ inférieur ou égal à $47$. Comme $6\times 7=42$ et $6\times 8=48>47$, on obtient $q=7$ et $r=47-42=5$. Donc $47=6\times 7+5$.

Soient $a,b\in \mathbb{N}$. On dit que $b$ divise $a$, noté $b|a$, lorsqu'il existe $k\in \mathbb{N}$ tel que $a=bk$. On dit alors que $a$ est un multiple de $b$.

$7|42$ car $42=7\times 6$. En revanche $5$ ne divise pas $23$ car la division euclidienne de $23$ par $5$ donne un reste non nul ($23=5\times 4+3$).

Pour tous entiers naturels $a,b,c$ :

1. $1|a$ et $a|a$ (réflexivité).
2. Si $a|b$ et $b|c$, alors $a|c$ (transitivité).
3. Si $a|b$ et $a|c$, alors pour tous $u,v\in \mathbb{N}$, $a|(bu+cv)$.
4. Si $a|b$ et $b\ne 0$, alors $a\le b$.

Un entier $p\in \mathbb{N}$ est dit premier lorsque $p\ge 2$ et que ses seuls diviseurs dans $\mathbb{N}$ sont $1$ et $p$ lui-même.

Tout entier $n\ge 2$ s'écrit, de manière unique à l'ordre des facteurs près, comme produit de nombres premiers :

où les $p_i$ sont des nombres premiers deux à deux distincts et les ${\alpha }_i\in {\mathbb{N}}^{\ast }$.

$360=2^3\times 3^2\times 5$. En effet $360=8\times 45=8\times 9\times 5$, et $8=2^3$, $9=3^2$.

Si un entier $n\ge 2$ n'a aucun diviseur premier $p\le \sqrt{n}$, alors $n$ est premier.

Pour vérifier que $97$ est premier, il suffit de tester les diviseurs premiers $\le \sqrt{97}\approx 9,85$, soit $2,3,5,7$. Aucun ne divise $97$, donc $97$ est premier.

Soient $a,b\in \mathbb{N}$ non tous deux nuls. Le plus grand commun diviseur de $a$ et $b$, noté $\mathrm{pgcd}(a,b)$ (ou $a\wedge b$), est le plus grand entier naturel qui divise à la fois $a$ et $b$.

Soient $a,b\in {\mathbb{N}}^{\ast }$. Le plus petit commun multiple de $a$ et $b$, noté $\mathrm{ppcm}(a,b)$ (ou $a\vee b$), est le plus petit entier naturel non nul multiple de $a$ et de $b$.

Calculons $\mathrm{pgcd}(360,84)$ et $\mathrm{ppcm}(360,84)$.

• $360=2^3\times 3^2\times 5^1$
• $84=2^2\times 3^1\times 7^1$ Donc $\mathrm{pgcd}(360,84)=2^2\times 3^1=12$ et $\mathrm{ppcm}(360,84)=2^3\times 3^2\times 5\times 7=2520$.

Soient $a\in \mathbb{N}$ et $b\in {\mathbb{N}}^{\ast }$. Si $r$ est le reste de la division euclidienne de $a$ par $b$, alors

Calcul de $\mathrm{pgcd}(252,105)$ par l'algorithme d'Euclide :

• $252=105\times 2+42$
• $105=42\times 2+21$
• $42=21\times 2+0$ Le dernier reste non nul est $21$, donc $\mathrm{pgcd}(252,105)=21$.

Pour tous entiers $a,b\in {\mathbb{N}}^{\ast }$ :

Avec $a=360$ et $b=84$ : $12\times 2520=30240=360\times 84$. ✓

Deux entiers $a,b\in {\mathbb{N}}^{\ast }$ sont dits premiers entre eux lorsque $\mathrm{pgcd}(a,b)=1$.

$15$ et $28$ sont premiers entre eux : $15=3\times 5$, $28=2^2\times 7$, ils n'ont aucun facteur premier en commun.

Soit $d=\mathrm{pgcd}(a,b)$. Si l'on pose $a=d{a}^{\prime }$ et $b=d{b}^{\prime }$, alors $a^{\prime }$ et $b^{\prime }$ sont premiers entre eux.

Effectuer la division euclidienne de $a$ par $b$ dans les cas suivants : (a) $a=73$, $b=8$ ; (b) $a=2025$, $b=47$ ; (c) $a=1000$, $b=17$.

Lister tous les diviseurs naturels de $60$. Combien y en a-t-il ? Retrouver ce nombre à partir de la décomposition $60=2^2\times 3\times 5$.

Montrer que la somme de trois entiers naturels consécutifs est divisible par $3$.

Décomposer en facteurs premiers : $504$, $1001$, $2024$. En déduire $\mathrm{pgcd}(504,2024)$.

En utilisant l'algorithme d'Euclide, calculer $\mathrm{pgcd}(1071,462)$, puis $\mathrm{ppcm}(1071,462)$ via la formule $\mathrm{pgcd}\times \mathrm{ppcm}=ab$.