Arithmétique dans N
Table des matières
L’ensemble \(\mathbb{N}\) des entiers naturels
Définition
L’ensemble des entiers naturels, noté \(\mathbb{N}\), est l’ensemble des nombres entiers positifs ou nuls :
\[\mathbb{N}=\{0,\,1,\,2,\,3,\,\cdots\}.\]
-
\(0\) est le plus petit élément de \(\mathbb{N}\) ; \(\mathbb{N}\) n’admet pas de plus grand élément.
-
\(\mathbb{N}^{*}=\{1,\,2,\,3,\,\cdots\}=\mathbb{N}\setminus\{0\}\) : ensemble des entiers naturels non nuls.
-
\(\mathbb{N}^{*}\subset \mathbb{N}\).
Exemple
\[0\in\mathbb{N},\qquad 3189\in\mathbb{N}^{*},\qquad -3\notin\mathbb{N},\qquad 1{,}89\notin\mathbb{N}.\]
Pair et impair
Définition
Soit \(a\in\mathbb{N}\).
-
\(a\) est pair si et seulement s’il existe \(k\in\mathbb{N}\) tel que \(a=2k\).
-
\(a\) est impair si et seulement s’il existe \(k\in\mathbb{N}\) tel que \(a=2k+1\).
Remarque
Tout entier naturel est soit pair, soit impair (et jamais les deux à la fois).
-
La somme de deux entiers de même parité est paire.
-
La somme de deux entiers de parités différentes est impaire.
-
Le produit de deux entiers consécutifs est pair.
Exemple
\[\underbrace{124+18}_{\text{pair}+\text{pair}}=142\ (\text{pair}),\quad \underbrace{5+17}_{\text{impair}+\text{impair}}=22\ (\text{pair}),\quad \underbrace{5+18}_{\text{impair}+\text{pair}}=23\ (\text{impair}).\]
Multiples et diviseurs d’un entier naturel
Définitions
Définition
Soient \(a\) et \(b\) deux entiers naturels avec \(b\neq 0\).
-
On dit que \(a\) est un multiple de \(b\) (ou que \(b\) est un diviseur de \(a\), ou encore que \(a\) est divisible par \(b\)) s’il existe \(k\in\mathbb{N}\) tel que :
\[a=k\times b.\]
Exemple
-
\(24=8\times 3\), donc \(24\) est un multiple de \(8\), et \(8\) est un diviseur de \(24\).
-
\(D_{8}=\{1,2,4,8\}\) : ensemble des diviseurs de \(8\).
Propriétés
Soient \(a\), \(b\), \(c\) des entiers naturels.
-
Si \(b\) et \(c\) sont des multiples de \(a\) et \(b\geq c\), alors \(b+c\) et \(b-c\) sont des multiples de \(a\).
-
Si \(b\) est un multiple de \(a\), alors \(b\times c\) est un multiple de \(a\).
-
Si \(a\) est un diviseur de \(b\) et de \(c\), alors \(a\) est un diviseur de \(b+c\), \(b\times c\) et (si \(b\geq c\)) de \(b-c\).
Exemple
\(21\) et \(6\) sont des multiples de \(3\), donc \(21+6=27\) et \(21-6=15\) le sont aussi.
Exercice n°1
Montrer que pour tout entier naturel \(n\), \(n(n+1)\) est un multiple de \(2\).
Critères de divisibilité
Un entier naturel est divisible par :
-
\(2\) si son chiffre des unités est pair ( \(0,\,2,\,4,\,6\) ou \(8\) ).
-
\(3\) si la somme de ses chiffres est divisible par \(3\).
-
\(4\) si le nombre formé par ses deux derniers chiffres est divisible par \(4\).
-
\(5\) si son chiffre des unités est \(0\) ou \(5\).
-
\(9\) si la somme de ses chiffres est divisible par \(9\).
-
\(10\) si son chiffre des unités est \(0\).
-
\(11\) si la différence alternée de ses chiffres (de droite à gauche) est divisible par \(11\).
Exemple
-
\(2316\) est divisible par \(3\) car \(2+3+1+6=12\) est divisible par \(3\).
-
\(4128\) est divisible par \(4\) car \(28=4\times 7\).
-
\(918\) est divisible par \(9\) car \(9+1+8=18\) est divisible par \(9\).
-
\(1\,353\) est divisible par \(11\) car \(3-5+3-1=0\) est divisible par \(11\).
La division euclidienne dans \(\mathbb{N}\)
Théorème
Théorème (division euclidienne).
Soient \(a\in\mathbb{N}\) et \(b\in\mathbb{N}^{*}\).
Il existe un unique couple \((q,r)\in\mathbb{N}^{2}\) tel que :
\[a=b\times q + r \qquad \text{et} \qquad 0\leq r < b.\]
Définition
Avec les notations du théorème :
-
\(a\) est appelé le dividende.
-
\(b\) est le diviseur.
-
\(q\) est le quotient.
-
\(r\) est le reste.
Exemple
-
Division euclidienne de \(47\) par \(6\) :
\[47=6\times 7 + 5,\qquad 0\leq 5 < 6.\]
Quotient : \(q=7\), reste : \(r=5\). -
Division euclidienne de \(100\) par \(13\) :
\[100=13\times 7 + 9,\qquad 0\leq 9 < 13.\]
Remarque
\(a\) est divisible par \(b\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul.
Exercice n°2
Effectuer la division euclidienne de :
\[(a)\ 1\,234\ \text{par}\ 56;\qquad (b)\ 245\ \text{par}\ 13;\qquad (c)\ 7^{2}\ \text{par}\ 5.\]
Les nombres premiers
Définition et reconnaissance
Définition
Un entier naturel \(p\geq 2\) est dit premier s’il admet exactement deux diviseurs distincts : \(1\) et lui-même.
Remarque
-
Un entier naturel \(\geq 2\) qui n’est pas premier est dit composé.
-
\(0\) et \(1\) ne sont ni premiers, ni composés.
-
Liste des nombres premiers inférieurs à \(100\) :
\(2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71,\ 73,\ 79,\ 83,\ 89,\ 97\).
Proposition
Pour montrer qu’un entier naturel \(n\geq 2\) est premier, il suffit de vérifier qu’il n’est divisible par aucun nombre premier \(p\) tel que \(p\leq \sqrt{n}\).
Exemple
-
\(\sqrt{127}\approx 11{,}27\) : on teste \(2,\,3,\,5,\,7,\,11\). Aucun ne divise \(127\), donc \(127\) est premier.
-
\(\sqrt{217}\approx 14{,}73\) : on teste \(2,\,3,\,5,\,7,\,11,\,13\). On a \(217=7\times 31\), donc \(217\) est composé.
Exercice n°3
Les nombres \(331\) et \(1521\) sont-ils premiers ou composés ?
Décomposition en produit de facteurs premiers
Théorème
Théorème fondamental de l’arithmétique.
Tout entier naturel \(n\geq 2\) se décompose de manière unique (à l’ordre près des facteurs) en produit de nombres premiers :
\[n=p_{1}^{\alpha_{1}}\times p_{2}^{\alpha_{2}}\times \cdots \times p_{k}^{\alpha_{k}},\]
où \(p_{1}<p_{2}<\cdots<p_{k}\) sont des nombres premiers et \(\alpha_{1},\alpha_{2},\ldots,\alpha_{k}\in\mathbb{N}^{*}\).
Exemple
-
\(\phantom{1}12=2^{2}\times 3\).
-
\(\phantom{1}54=2\times 3^{3}\).
-
\(\phantom{1}245=5\times 7^{2}\).
-
\(1260=2^{2}\times 3^{2}\times 5\times 7\).
Remarque
Méthode pratique : on divise \(n\) successivement par les nombres premiers \(2,\,3,\,5,\,7,\,11,\ldots\) jusqu’à obtenir \(1\).
Exemple : décomposition de \(360\).
\[\begin{array}{rl} 360 &\div 2 = 180 \\ 180 &\div 2 = 90 \\ 90 &\div 2 = 45 \\ 45 &\div 3 = 15 \\ 15 &\div 3 = 5 \\ 5 &\div 5 = 1 \end{array} \qquad\text{donc}\qquad 360=2^{3}\times 3^{2}\times 5.\]
PGCD et PPCM
Définitions
Définition
Soient \(a\) et \(b\) deux entiers naturels non nuls.
-
Le plus grand diviseur commun de \(a\) et \(b\), noté \(\mathrm{PGCD}(a;b)\) ou \(a\wedge b\), est le plus grand des diviseurs communs à \(a\) et \(b\).
-
Le plus petit multiple commun non nul de \(a\) et \(b\), noté \(\mathrm{PPCM}(a;b)\) ou \(a\vee b\), est le plus petit des multiples communs non nuls de \(a\) et \(b\).
Définition
\(a\) et \(b\) sont dits premiers entre eux si \(\mathrm{PGCD}(a;b)=1\).
Exemple
-
\(D_{8}=\{1,2,4,8\}\), \(D_{20}=\{1,2,4,5,10,20\}\) donc \(\mathrm{PGCD}(8;20)=4\).
-
\(D_{17}=\{1,17\}\), \(D_{35}=\{1,5,7,35\}\) donc \(\mathrm{PGCD}(17;35)=1\) : \(17\) et \(35\) sont premiers entre eux.
-
\(M_{4}=\{4,8,12,16,20,24,\ldots\}\), \(M_{6}=\{6,12,18,24,30,\ldots\}\) donc \(\mathrm{PPCM}(4;6)=12\).
Méthode par décomposition en facteurs premiers
Soient \(a\) et \(b\) deux entiers naturels \(\geq 2\).
-
\(\mathrm{PGCD}(a;b)\) est le produit des facteurs premiers communs à \(a\) et \(b\), affectés du plus petit exposant trouvé dans les décompositions.
-
\(\mathrm{PPCM}(a;b)\) est le produit des facteurs premiers de \(a\) et de \(b\), affectés du plus grand exposant trouvé dans les décompositions.
Exemple
Soient \(a=2^{4}\times 5^{3}\times 7^{3}\) et \(b=2^{6}\times 5^{2}\times 11\).
\[\mathrm{PGCD}(a;b)=2^{4}\times 5^{2}=400, \qquad \mathrm{PPCM}(a;b)=2^{6}\times 5^{3}\times 7^{3}\times 11.\]
Exemple
Recherche de \(\mathrm{PGCD}(120;84)\) et \(\mathrm{PPCM}(120;84)\) :
\[120=2^{3}\times 3\times 5,\qquad 84=2^{2}\times 3\times 7.\]
\[\mathrm{PGCD}(120;84)=2^{2}\times 3=12,\qquad \mathrm{PPCM}(120;84)=2^{3}\times 3\times 5\times 7=840.\]
On vérifie : \(120\times 84=10\,080=12\times 840\).
Pour tous entiers naturels non nuls \(a\) et \(b\) :
\[\mathrm{PGCD}(a;b)\times \mathrm{PPCM}(a;b)=a\times b.\]
Algorithme d’Euclide pour le PGCD
L’algorithme d’Euclide repose sur la propriété suivante : si \(a=b\times q+r\) est la division euclidienne de \(a\) par \(b\) (avec \(b\neq 0\)), alors
\[\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r).\]
Remarque
Procédure :
-
On effectue la division euclidienne de \(a\) par \(b\) : \(a=b\times q_{1}+r_{1}\).
-
Puis on remplace \(a\) par \(b\) et \(b\) par \(r_{1}\), et on recommence : \(b=r_{1}\times q_{2}+r_{2}\).
-
On poursuit tant que le reste est non nul.
Le \(\mathrm{PGCD}\) est le dernier reste non nul.
Exemple
-
\(\mathrm{PGCD}(7;4)\) :
\[\begin{aligned}7 &= 4\times 1+3 \\ 4 &= 3\times 1+1 \\ 3 &= 1\times 3+0\end{aligned}\]
Dernier reste non nul : \(1\). Donc \(\mathrm{PGCD}(7;4)=1\). -
\(\mathrm{PGCD}(216;84)\) :
\[\begin{aligned}216 &= 84\times 2+48 \\ 84 &= 48\times 1+36 \\ 48 &= 36\times 1+12 \\ 36 &= 12\times 3+0\end{aligned}\]
Donc \(\mathrm{PGCD}(216;84)=12\). -
\(\mathrm{PGCD}(1275;575)\) :
\[\begin{aligned}1275 &= 575\times 2+125 \\ 575 &= 125\times 4+75 \\ 125 &= 75 \times 1+50 \\ 75 &= 50 \times 1+25 \\ 50 &= 25 \times 2+0\end{aligned}\]
Donc \(\mathrm{PGCD}(1275;575)=25\).
Exercice n°4
En utilisant l’algorithme d’Euclide, déterminer :
\[\mathrm{PGCD}(252;105),\qquad \mathrm{PGCD}(884;221),\qquad \mathrm{PGCD}(1\,001;273).\]