Tronc Commun · Sciences · Chapitre 2

Arithmétique dans ℕ

L'arithmétique, c'est l'étude des nombres entiers et de la façon dont ils se divisent les uns les autres. Ce chapitre commence par les notions de pair et d'impair (n = 2k ou n = 2k + 1), la clé de nombreuses démonstrations, puis introduit la divisibilité, les critères qui permettent de reconnaître d'un coup d'œil un multiple de 2, 3, 4, 5, 9 ou 11, et la division euclidienne a = bq + r avec 0 ≤ r < b — l'outil fondateur de tout le reste. Vous rencontrerez ensuite les nombres premiers, la brique élémentaire de tous les entiers, la décomposition en facteurs premiers (unique !), et deux quantités que vous calculerez sans cesse : le PGCD (plus grand diviseur commun, obtenu par l'algorithme d'Euclide) et le PPCM (plus petit multiple commun), reliés par pgcd(a,b) × ppcm(a,b) = a × b. C'est aussi ce qui permet de rendre une fraction irréductible en une seule étape.

1 · Résumé du cours

L'arithmétique étudie les entiers naturels et les relations de divisibilité entre eux. Dans ce chapitre, on apprend à reconnaître les nombres pairs et impairs, à effectuer une division euclidienne, à utiliser les nombres premiers et à calculer le PGCD et le PPCM de deux entiers.

1.1 L'ensemble des entiers naturels

Définition L'ensemble des entiers naturels est \(\mathbb{N}=\{0,1,2,3,\ldots\}\). L'ensemble des entiers naturels non nuls est noté \[\mathbb{N}^{*}=\mathbb{N}\setminus\{0\}=\{1,2,3,\ldots\}.\]

Exemple. \(18\in\mathbb{N}\) et \(0\in\mathbb{N}\), tandis que \(-3\notin\mathbb{N}\), \(\dfrac23\notin\mathbb{N}\) et \(\sqrt2\notin\mathbb{N}\).

Propriété — quelques propriétés utiles Pour tous \(a,b\in\mathbb{N}\) : \[a+b=0\iff a=b=0,\qquad ab=0\iff a=0\ \text{ou}\ b=0.\] De plus, \(ab=1\) si et seulement si \(a=b=1\).

1.2 Nombres pairs et nombres impairs

Définition Soit \(n\in\mathbb{N}\).

\(n\) est pair s'il existe \(k\in\mathbb{N}\) tel que \(n=2k\) ;
\(n\) est impair s'il existe \(k\in\mathbb{N}\) tel que \(n=2k+1\).

Propriété — règles de parité Tout entier naturel est soit pair, soit impair, jamais les deux à la fois. Pour deux entiers naturels \(a\) et \(b\) : \[\begin{array}{c|c|c|c}\text{Parité de }a & \text{Parité de }b & a+b & ab\\ \hline \text{paire} & \text{paire} & \text{paire} & \text{paire}\\ \text{paire} & \text{impaire} & \text{impaire} & \text{paire}\\ \text{impaire} & \text{paire} & \text{impaire} & \text{paire}\\ \text{impaire} & \text{impaire} & \text{paire} & \text{impaire}\end{array}\] En particulier, le produit de deux entiers consécutifs \(n(n+1)\) est toujours pair.

Méthode — étudier une parité On remplace un entier pair par \(2k\) et un entier impair par \(2k+1\), puis on transforme l'expression obtenue afin de faire apparaître l'une de ces deux formes.

Exemple. Si \(n=2k+1\) est impair, alors \(n^2=(2k+1)^2=2(2k^2+2k)+1\). Ainsi, le carré d'un entier impair est impair.

1.3 Diviseurs et multiples

Définition Soient \(a\in\mathbb{N}\) et \(d\in\mathbb{N}^{*}\). On dit que \(d\) divise \(a\) s'il existe \(k\in\mathbb{N}\) tel que \(a=d\,k\). On note \(d\mid a\). On dit aussi que \(d\) est un diviseur de \(a\) et que \(a\) est un multiple de \(d\).

Exemple. \(145=5\times29\), donc \(5\mid145\) et \(29\mid145\). Le nombre \(145\) est un multiple de \(5\) et de \(29\).

Propriété — calculs avec la divisibilité Soient \(a,b,c\in\mathbb{N}\) et \(d\in\mathbb{N}^{*}\).

\(1\) divise tout entier naturel et tout entier naturel non nul se divise lui-même.
\(0\) est un multiple de tout entier naturel non nul.
Si \(d\mid a\) et \(d\mid b\), alors \(d\mid(a+b)\) ; si \(a\ge b\), alors \(d\mid(a-b)\).
Si \(d\mid a\), alors \(d\mid ac\).
Si \(d\mid a\) et \(a\mid b\), alors \(d\mid b\).

1.4 Critères de divisibilité

Propriété Un entier naturel est divisible par :

\(2\) si son chiffre des unités est \(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\) ;
\(8\) si le nombre formé par ses trois derniers chiffres est divisible par \(8\) ;
\(9\) si la somme de ses chiffres est divisible par \(9\) ;
\(11\) si la différence entre la somme des chiffres de rang impair et celle des chiffres de rang pair est un multiple de \(11\) ;
\(25\) si le nombre formé par ses deux derniers chiffres est divisible par \(25\).

Exemple. Pour \(n=47\,520\) : le chiffre des unités est \(0\), donc \(n\) est divisible par \(2\) et \(5\) ; \(4+7+5+2+0=18\), donc \(n\) est divisible par \(3\) et \(9\) ; \(20\) est divisible par \(4\), donc \(n\) l'est aussi ; \(520=8\times65\), donc \(n\) est divisible par \(8\).

Bien appliquer un critère Un critère de divisibilité fournit une condition nécessaire et suffisante. Par exemple, un entier est divisible par \(9\) si et seulement si la somme de ses chiffres est divisible par \(9\).

1.5 Division euclidienne dans ℕ

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 \[\boxed{a=bq+r\quad\text{avec}\quad 0\le rdividende, \(b\) le diviseur, \(q\) le quotient et \(r\) le reste.

Exemple. La division euclidienne de \(2026\) par \(37\) s'écrit \(2026=37\times54+28\), avec \(0\le28<37\). Le quotient est \(54\) et le reste est \(28\).

Propriété Pour \(b\in\mathbb{N}^{*}\), on a \(b\mid a\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul.

1.6 Nombres premiers

Définition Un entier naturel \(p\ge2\) est premier s'il admet exactement deux diviseurs positifs : \(1\) et \(p\). Un entier \(n\ge2\) qui n'est pas premier est dit composé.

Exemple. Les nombres premiers inférieurs à \(30\) sont \(2,3,5,7,11,13,17,19,23,29\). Le nombre \(1\) n'est pas premier et \(2\) est le seul nombre premier pair.

Méthode — tester si un entier est premier Pour déterminer si \(n\ge2\) est premier, il suffit de tester sa divisibilité par les nombres premiers \(p\) tels que \(p\le\sqrt n\). Si l'un de ces nombres premiers divise \(n\), alors \(n\) est composé ; si aucun ne divise \(n\), alors \(n\) est premier.

Exemple. \(\sqrt{97}<10\). Il suffit donc de tester \(2,3,5\) et \(7\). Aucun ne divise \(97\), donc \(97\) est premier. En revanche, \(299=13\times23\) : le nombre \(299\) est composé.

1.7 Décomposition en facteurs premiers

Théorème fondamental de l'arithmétique Tout entier naturel \(n\ge2\) se décompose, de façon unique à l'ordre des facteurs près, sous la forme \[n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s},\] où \(p_1,p_2,\ldots,p_s\) sont des nombres premiers distincts et \(\alpha_1,\alpha_2,\ldots,\alpha_s\in\mathbb{N}^{*}\).

Méthode — décomposer un entier On divise successivement l'entier par le plus petit nombre premier possible : \(2\), puis \(3\), puis \(5\), puis \(7\), etc. On poursuit jusqu'à obtenir le quotient \(1\), puis on regroupe les facteurs identiques à l'aide de puissances.

Exemple. \(1344=2\times672=2^2\times336=\cdots=2^6\times3\times7\). Ainsi, \(1344=2^6\times3\times7\) est sa décomposition en facteurs premiers.

1.8 PGCD et entiers premiers entre eux

Définition Soient \(a,b\in\mathbb{N}^{*}\). Le PGCD de \(a\) et \(b\), noté \(\operatorname{pgcd}(a,b)\), est leur plus grand diviseur commun. Les entiers \(a\) et \(b\) sont premiers entre eux lorsque \(\operatorname{pgcd}(a,b)=1\).

Méthode — PGCD par décomposition On décompose \(a\) et \(b\) en facteurs premiers. Le PGCD est le produit des facteurs premiers communs, chacun étant affecté du plus petit exposant présent dans les deux décompositions.

Exemple. \(120=2^3\times3\times5\) et \(1764=2^2\times3^2\times7^2\). Donc \(\operatorname{pgcd}(120,1764)=2^2\times3=12\).

Théorème — algorithme d'Euclide Si \(a=bq+r\) est la division euclidienne de \(a\) par \(b\), alors \(\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)\). En répétant les divisions euclidiennes, le PGCD est le dernier reste non nul.

Exemple. Calculons \(\operatorname{pgcd}(1053,325)\) : \[\begin{aligned}1053&=325\times3+78,\\ 325&=78\times4+13,\\ 78&=13\times6+0.\end{aligned}\] Le dernier reste non nul est \(13\), donc \(\operatorname{pgcd}(1053,325)=13\).

1.9 PPCM de deux entiers naturels

Définition Soient \(a,b\in\mathbb{N}^{*}\). Le PPCM de \(a\) et \(b\), noté \(\operatorname{ppcm}(a,b)\), est leur plus petit multiple commun strictement positif.

Méthode — PPCM par décomposition On décompose \(a\) et \(b\) en facteurs premiers. Le PPCM est le produit de tous les facteurs premiers présents, chacun étant affecté du plus grand exposant rencontré.

Exemple. À partir des décompositions de \(120\) et \(1764\) : \(\operatorname{ppcm}(120,1764)=2^3\times3^2\times5\times7^2=17640\).

Propriété — relation fondamentale Pour tous \(a,b\in\mathbb{N}^{*}\) : \[\boxed{\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=a\times b.}\]

Méthode — rendre une fraction irréductible Pour rendre \(\dfrac ab\) irréductible, on calcule \(d=\operatorname{pgcd}(a,b)\), puis on divise le numérateur et le dénominateur par \(d\) : \(\dfrac ab=\dfrac{a\div d}{b\div d}\).

Exemple. \(\operatorname{pgcd}(360,84)=12\), donc \(\dfrac{360}{84}=\dfrac{360\div12}{84\div12}=\dfrac{30}{7}\). La fraction \(\dfrac{30}{7}\) est irréductible.

L'essentiel du chapitre

Pair : \(n=2k\) ; impair : \(n=2k+1\).
\(d\mid a\) signifie qu'il existe \(k\in\mathbb{N}\) tel que \(a=dk\).
Division euclidienne : \(a=bq+r\) avec \(0\le r
Pour tester si \(n\) est premier, on teste les nombres premiers jusqu'à \(\sqrt n\).
PGCD : facteurs communs avec les plus petits exposants.
PPCM : tous les facteurs avec les plus grands exposants.
L'algorithme d'Euclide donne le PGCD comme dernier reste non nul.
\(\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=ab\).

2 · Exercices résolus

PGCD · PPCM

Exercice 1

Décomposer \(360\) et \(84\) en produits de facteurs premiers, puis calculer leur PGCD et leur PPCM.

Voir la correction

On obtient \(360=2^3\times3^2\times5\) et \(84=2^2\times3\times7\).

Pour le PGCD, on conserve les facteurs communs avec les plus petits exposants : \(\operatorname{pgcd}(360,84)=2^2\times3=12\).

Pour le PPCM, on conserve tous les facteurs avec les plus grands exposants : \(\operatorname{ppcm}(360,84)=2^3\times3^2\times5\times7=2520\).

Enfin, \(12\times2520=30240=360\times84\), ce qui vérifie la relation fondamentale. \(\blacksquare\)

Divisibilité · parité

Exercice 2

Montrer que si \(n\) est impair, alors \(n^2-1\) est divisible par \(8\).

Voir la correction

Comme \(n\) est impair, il existe \(k\in\mathbb{N}\) tel que \(n=2k+1\). Alors \[n^2-1=(2k+1)^2-1=4k^2+4k=4k(k+1).\]

Les entiers \(k\) et \(k+1\) sont consécutifs : l'un des deux est pair. Il existe donc \(m\in\mathbb{N}\) tel que \(k(k+1)=2m\). Par conséquent, \(n^2-1=4\times2m=8m\). Ainsi, \(8\mid(n^2-1)\). \(\blacksquare\)

Algorithme d'Euclide

Exercice 3

Effectuer la division euclidienne de \(1053\) par \(325\), puis utiliser l'algorithme d'Euclide pour calculer \(\operatorname{pgcd}(1053,325)\).

Voir la correction

La première division donne \(1053=325\times3+78\), avec \(0\le78<325\).

On poursuit : \(325=78\times4+13\), puis \(78=13\times6+0\).

Le dernier reste non nul est \(13\). Par l'algorithme d'Euclide, \(\operatorname{pgcd}(1053,325)=13\). \(\blacksquare\)

QCM interactifTeste-toi sur ce chapitre — 10 questions auto-corrigéesCommencer le QCM