14
1ʳᵉ Bac · Sciences Maths · Chapitre 14
Arithmétique dans ℕ
1 · Résumé du cours
1.1 Divisibilité dans \(\mathbb{Z}\)
Diviseur, multiple
Soient \(a,b\in\mathbb{Z}\). On dit que \(a\) divise \(b\), noté \(a\mid b\), lorsqu'il existe \(k\in\mathbb{Z}\) tel que \(b=a\,k\). On dit alors que \(a\) est un diviseur de \(b\), et \(b\) un multiple de \(a\).
Exemples : \(3\mid12\) car \(12=3\times4\) ; \(7\nmid20\). Pour tout \(a\) : \(1\mid a\), \(a\mid a\), et \(a\mid0\) (car \(0=a\times0\)).
Exemples : \(3\mid12\) car \(12=3\times4\) ; \(7\nmid20\). Pour tout \(a\) : \(1\mid a\), \(a\mid a\), et \(a\mid0\) (car \(0=a\times0\)).
Règles de calcul
Pour tous entiers \(a,b,c,u,v\) :
- \(a\mid a\) (réflexivité) ;
- si \(a\mid b\) et \(b\mid c\), alors \(a\mid c\) (transitivité) ;
- si \(a\mid b\) et \(a\mid c\), alors \(a\mid(bu+cv)\) (combinaison linéaire — la règle la plus utile) ;
- si \(a\mid b\) et \(b\mid a\), alors \(a=b\) ou \(a=-b\) ;
- si \(a\mid b\) et \(b\neq0\), alors \(|a|\le|b|\).
La règle qui débloque presque tout
Pour montrer qu'un nombre \(d\) divise une expression, on l'écrit comme combinaison linéaire de choses que \(d\) divise déjà. Ex. : si \(d\mid n\) et \(d\mid(n+7)\), alors \(d\) divise la différence \((n+7)-n=7\) — donc \(d\in\{1,7\}\) si \(d\in\mathbb{N}^*\).
1.2 La division euclidienne
Théorème
Soient \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^*\). Il existe un unique couple \((q,r)\in\mathbb{Z}\times\mathbb{N}\) tel que
\[a=b\,q+r\quad\text{avec}\quad 0\le rquotient, \(r\) le reste.
Exemples : \(47=6\times7+5\) (\(q=7,r=5\)). Pour \(a=-47\) : \(-47=6\times(-8)+1\), donc \(q=-8,r=1\) — le reste est toujours positif.
Exemples : \(47=6\times7+5\) (\(q=7,r=5\)). Pour \(a=-47\) : \(-47=6\times(-8)+1\), donc \(q=-8,r=1\) — le reste est toujours positif.
Propriété
\(b\mid a\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul.
Méthode — utiliser les restes possibles
Pour démontrer une propriété de divisibilité « pour tout entier \(n\) », on discute selon le reste de \(n\) dans la division par \(b\) : seulement \(b\) cas (\(r=0,1,\dots,b-1\)). C'est le raisonnement par disjonction des cas.
Exemple : \(n(n+1)\) est pair. Si \(n=2k\), \(n(n+1)=2k(n+1)\) ; si \(n=2k+1\), \(n+1=2(k+1)\) et \(n(n+1)=2n(k+1)\). Dans les deux cas \(2\mid n(n+1)\).
Exemple : \(n(n+1)\) est pair. Si \(n=2k\), \(n(n+1)=2k(n+1)\) ; si \(n=2k+1\), \(n+1=2(k+1)\) et \(n(n+1)=2n(k+1)\). Dans les deux cas \(2\mid n(n+1)\).
1.3 PGCD et algorithme d'Euclide
PGCD
Soient \(a,b\) deux entiers naturels non tous deux nuls. L'ensemble de leurs diviseurs communs admet un plus grand élément, le plus grand commun diviseur \(\mathrm{pgcd}(a,b)\) (ou \(a\wedge b\)).
Lemme d'Euclide
Si \(a=bq+r\) (division euclidienne), alors \(\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r)\).
Preuve : tout diviseur commun de \(a,b\) divise \(r=a-bq\) ; réciproquement tout diviseur commun de \(b,r\) divise \(a=bq+r\). Mêmes diviseurs communs, donc même plus grand. ∎
Preuve : tout diviseur commun de \(a,b\) divise \(r=a-bq\) ; réciproquement tout diviseur commun de \(b,r\) divise \(a=bq+r\). Mêmes diviseurs communs, donc même plus grand. ∎
Méthode — algorithme d'Euclide
On remplace \((a,b)\) par \((b,r)\) et on recommence, jusqu'à un reste nul. Le dernier reste non nul est le PGCD.
Exemple \(\mathrm{pgcd}(1071,462)\) : \[\begin{array}{rcl}1071 &=& 462\times2+147\\ 462 &=& 147\times3+21\\ 147 &=& 21\times7+0\end{array}\] Dernier reste non nul : \(21\), donc \(\mathrm{pgcd}(1071,462)=21\).
Exemple \(\mathrm{pgcd}(1071,462)\) : \[\begin{array}{rcl}1071 &=& 462\times2+147\\ 462 &=& 147\times3+21\\ 147 &=& 21\times7+0\end{array}\] Dernier reste non nul : \(21\), donc \(\mathrm{pgcd}(1071,462)=21\).
Entiers premiers entre eux
\(a\) et \(b\) sont premiers entre eux lorsque \(\mathrm{pgcd}(a,b)=1\). Si \(d=\mathrm{pgcd}(a,b)\), il existe \(a',b'\) premiers entre eux tels que \(a=d\,a'\), \(b=d\,b'\) : c'est la fraction irréductible \(\frac ab=\frac{a'}{b'}\).
1.4 PPCM
PPCM
Le plus petit commun multiple strictement positif de \(a\) et \(b\) (non nuls) est noté \(\mathrm{ppcm}(a,b)\) (ou \(a\vee b\)).
Relation fondamentale
Pour tous entiers naturels non nuls \(a,b\) : \(\mathrm{pgcd}(a,b)\times\mathrm{ppcm}(a,b)=a\times b\).
Exemple : \(\mathrm{pgcd}(12,18)=6\), donc \(\mathrm{ppcm}(12,18)=\frac{12\times18}{6}=36\).
Exemple : \(\mathrm{pgcd}(12,18)=6\), donc \(\mathrm{ppcm}(12,18)=\frac{12\times18}{6}=36\).
1.5 Les nombres premiers
Nombre premier
Un entier \(p\ge2\) est premier lorsqu'il admet exactement deux diviseurs positifs : \(1\) et \(p\). Un entier \(n\ge2\) non premier est composé.
\(1\) n'est pas premier
\(1\) n'a qu'un seul diviseur positif, pas deux. L'exclure rend unique la décomposition en facteurs premiers (sinon on ajouterait autant de facteurs \(1\) que l'on veut).
Les 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.\]
Il y en a \(25\). Le seul premier pair est \(2\).
Test de primalité
Si un entier \(n\ge2\) n'est divisible par aucun nombre premier \(p\le\sqrt n\), alors \(n\) est premier.
Exemple : \(n=211\), \(\sqrt{211}\approx14{,}5\) ; on teste \(2,3,5,7,11,13\) : aucun ne divise \(211\), donc \(211\) est premier.
Exemple : \(n=211\), \(\sqrt{211}\approx14{,}5\) ; on teste \(2,3,5,7,11,13\) : aucun ne divise \(211\), donc \(211\) est premier.
Euclide — infinité de nombres premiers
L'ensemble des nombres premiers est infini.
Preuve (absurde) : supposons-les en nombre fini \(p_1,\dots,p_k\) ; posons \(N=p_1\cdots p_k+1\ge2\). \(N\) admet un diviseur premier \(p\), l'un des \(p_i\) ; alors \(p\mid N\) et \(p\mid p_1\cdots p_k\), donc \(p\mid1\) — impossible. Contradiction. ∎
Preuve (absurde) : supposons-les en nombre fini \(p_1,\dots,p_k\) ; posons \(N=p_1\cdots p_k+1\ge2\). \(N\) admet un diviseur premier \(p\), l'un des \(p_i\) ; alors \(p\mid N\) et \(p\mid p_1\cdots p_k\), donc \(p\mid1\) — impossible. Contradiction. ∎
1.6 Décomposition en facteurs premiers
Théorème fondamental de l'arithmétique
Tout entier \(n\ge2\) s'écrit de manière unique (à l'ordre près) :
\[n=p_1^{\alpha_1}\,p_2^{\alpha_2}\cdots p_k^{\alpha_k},\]
où les \(p_i\) sont des premiers distincts et \(\alpha_i\in\mathbb{N}^*\).
Exemples : \(360=2^3\times3^2\times5\) et \(84=2^2\times3\times7\).
Exemples : \(360=2^3\times3^2\times5\) et \(84=2^2\times3\times7\).
Lire le PGCD et le PPCM sur la décomposition
Exposant le plus petit pour le PGCD, le plus grand pour le PPCM :
\[\mathrm{pgcd}=\prod p_i^{\min(\alpha_i,\beta_i)},\qquad \mathrm{ppcm}=\prod p_i^{\max(\alpha_i,\beta_i)}.\]
Exemple : \(\mathrm{pgcd}(360,84)=2^2\times3=12\), \(\mathrm{ppcm}(360,84)=2^3\times3^2\times5\times7=2520\).
Nombre de diviseurs
Si \(n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\), le nombre de diviseurs positifs est \((\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\).
Exemple : \(360=2^3 3^2 5^1\) a \((3+1)(2+1)(1+1)=24\) diviseurs.
Exemple : \(360=2^3 3^2 5^1\) a \((3+1)(2+1)(1+1)=24\) diviseurs.
1.7 Congruences modulo \(n\)
Congruence
Soit \(n\in\mathbb{N}^*\). Deux entiers \(a,b\) sont congrus modulo \(n\), noté \(a\equiv b\ [n]\), lorsque \(n\mid(a-b)\) ; autrement dit \(a\) et \(b\) ont le même reste dans la division par \(n\).
Exemples : \(17\equiv2\ [5]\) car \(17-2=15\) ; \(-3\equiv4\ [7]\) car \(-3-4=-7\).
Exemples : \(17\equiv2\ [5]\) car \(17-2=15\) ; \(-3\equiv4\ [7]\) car \(-3-4=-7\).
Compatibilité avec les opérations
Si \(a\equiv b\ [n]\) et \(c\equiv d\ [n]\), alors
\[a+c\equiv b+d\ [n],\qquad a\,c\equiv b\,d\ [n],\qquad a^m\equiv b^m\ [n]\ (m\in\mathbb{N}).\]
Le super-pouvoir des congruences
On peut remplacer un nombre par son reste avant de calculer. C'est ce qui permet de traiter des puissances énormes.
Exemple — reste de \(7^{100}\) modulo \(5\) : \(7\equiv2\ [5]\), donc \(7^{100}\equiv2^{100}\ [5]\). Or \(2^4=16\equiv1\ [5]\) et \(100=4\times25\), donc \(2^{100}=(2^4)^{25}\equiv1\ [5]\). Le reste est \(1\).
Exemple — reste de \(7^{100}\) modulo \(5\) : \(7\equiv2\ [5]\), donc \(7^{100}\equiv2^{100}\ [5]\). Or \(2^4=16\equiv1\ [5]\) et \(100=4\times25\), donc \(2^{100}=(2^4)^{25}\equiv1\ [5]\). Le reste est \(1\).
Critères de divisibilité
Comme \(10\equiv1\ [9]\) et \(10\equiv1\ [3]\), un entier est congru à la somme de ses chiffres modulo \(9\) (et modulo \(3\)) : il est divisible par \(3\) (resp. \(9\)) ssi la somme de ses chiffres l'est.
2 · Exercices résolus
Euclide
Exercice 1
Déterminer \(\mathrm{pgcd}(1128,468)\) par l'algorithme d'Euclide, en déduire \(\mathrm{ppcm}(1128,468)\) et rendre \(\frac{1128}{468}\) irréductible.
Voir la correction
Algorithme d'Euclide : \[\begin{array}{rcl}1128 &=& 468\times2+192\\ 468 &=& 192\times2+84\\ 192 &=& 84\times2+24\\ 84 &=& 24\times3+12\\ 24 &=& 12\times2+0\end{array}\] Dernier reste non nul : \(12\), donc \(\mathrm{pgcd}(1128,468)=12\).
\(\mathrm{ppcm}=\frac{1128\times468}{12}=1128\times39=43\,992\).
\(1128=12\times94\) et \(468=12\times39\), donc \(\frac{1128}{468}=\frac{94}{39}\), irréductible (\(\mathrm{pgcd}(94,39)=1\)). ∎
Disjonction
Exercice 2
Montrer que pour tout \(n\in\mathbb{N}\), \(n(n+1)(n+2)\) est divisible par \(6\).
Voir la correction
Par \(2\) : parmi \(n\) et \(n+1\), l'un est pair, donc \(2\mid n(n+1)\), donc \(2\mid n(n+1)(n+2)\).
Par \(3\) : selon le reste de \(n\) modulo \(3\) : si \(n\equiv0\), \(3\mid n\) ; si \(n\equiv1\), \(n+2\equiv0\) ; si \(n\equiv2\), \(n+1\equiv0\). Dans tous les cas \(3\mid n(n+1)(n+2)\).
Comme \(2\) et \(3\) sont premiers entre eux et divisent le produit, \(6=2\times3\) le divise aussi. ∎
PGCD variable
Exercice 3
Soit \(n\in\mathbb{N}\). Déterminer les valeurs possibles de \(d=\mathrm{pgcd}(n+3,\ n+7)\).
Voir la correction
\(d\) divise \(n+3\) et \(n+7\), donc leur différence \((n+7)-(n+3)=4\). Donc \(d\) est un diviseur positif de \(4\) : \(d\in\{1,2,4\}\).
Ces valeurs sont atteintes : \(n=0\) → \(\mathrm{pgcd}(3,7)=1\) ; \(n=1\) → \(\mathrm{pgcd}(4,8)=4\) ; \(n=3\) → \(\mathrm{pgcd}(6,10)=2\). Donc \(d\in\{1,2,4\}\). ∎
L'essentiel du chapitre
- \(a\mid b\iff\exists k\in\mathbb{Z},\ b=ak\). Règle-reine : si \(d\) divise \(a\) et \(b\), il divise toute combinaison \(au+bv\).
- Division euclidienne : \(a=bq+r\), \(0\le r
- Algorithme d'Euclide : \(\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r)\) ; dernier reste non nul = PGCD.
- \(\mathrm{pgcd}(a,b)\times\mathrm{ppcm}(a,b)=a\times b\).
- Premier : exactement deux diviseurs ; tester par les premiers \(\le\sqrt n\) ; infinité (Euclide).
- Décomposition unique : \(\min\) des exposants → PGCD, \(\max\) → PPCM ; \(\prod(\alpha_i+1)\) diviseurs.
- Congruences : \(a\equiv b\ [n]\iff n\mid(a-b)\), compatibles avec \(+,\times\) et les puissances.
© Math Excellence · anassmaths.com