Prepa Help
Prepa Help › Cours › Mathématiques, 1re année

Arithmétique dans l'ensemble des entiers relatifs : divisibilité, PGCD, PPCM, nombres premiers et décomposition

Divisibilité et division euclidienne, PGCD et algorithme d'Euclide, PPCM, nombres premiers et leur infinité, décomposition en facteurs premiers et calcul du PGCD et du PPCM, arithmétique en Python ; selon la classe, entiers premiers entre eux, valuations p-adiques et forme irréductible d'un rationnel, relation et théorème de Bézout, lemme de Gauss, congruences, inverse modulo n et petit théorème de Fermat.

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

L'arithmétique des entiers étudie la divisibilité : diviseurs et multiples, division euclidienne et restes, PGCD calculé par l'algorithme d'Euclide, PPCM, nombres premiers et leur infinité, décomposition en facteurs premiers, qui donne les diviseurs d'un entier, son PGCD et son PPCM avec un autre. Le chapitre montre aussi comment programmer ces calculs en Python. Il est au programme de MPSI et de PCSI au Maroc, et de MPSI, MP2I, PCSI et PTSI en France, la PTSI travaillant dans N\mathbb{N} ; il ne concerne pas la TSI ni la TPC. Les entiers premiers entre eux, les valuations et la forme irréductible d'un rationnel sont étudiés en MPSI, en MP2I et en PCSI au Maroc ; la relation de Bézout, le lemme de Gauss, les congruences et le petit théorème de Fermat le sont seulement en MPSI et en MP2I.

Ce que tu sauras faire

Ce chapitre étudie la divisibilité des entiers relatifs : diviseurs, restes, plus grand diviseur commun, nombres premiers. À la fin, tu dois savoir :

L’essentiel du chapitre Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Divisibilité
  • a∣ba \mid b s'il existe k∈Zk \in \mathbb{Z} tel que b=kab = ka. D(a)=D(−a)\mathcal{D}(a) = \mathcal{D}(-a) ; 00 est multiple de tout entier et ne divise que 00.
  • Transitivité ; si a∣ba \mid b et a∣ca \mid c, alors a∣bu+cva \mid bu + cv pour tous u,v∈Zu, v \in \mathbb{Z}.
  • Si a∣ba \mid b et b≠0b \neq 0, alors ∣a∣≤∣b∣\lvert a\rvert \leq \lvert b\rvert. Si a∣ba \mid b et b∣ab \mid a, alors b=±ab = \pm a.
  • a−ba - b divise an−bna^n - b^n.
À retenir Division euclidienne
  • Pour a∈Za \in \mathbb{Z} et b∈N∗b \in \mathbb{N}^*, il existe un unique (q,r)∈Z2(q, r) \in \mathbb{Z}^2 tel que a=bq+ra = bq + r et 0≤r<b0 \leq r < b. Le quotient est q=⌊ab⌋q = \left\lfloor \frac ab\right\rfloor.
  • b∣ab \mid a si et seulement si r=0r = 0.
  • Deux entiers ont le même reste par nn si et seulement si nn divise leur différence. Le reste d'une somme, d'un produit, d'une puissance ne dépend que des restes.
À retenir PGCD et algorithme d'Euclide
  • Pour a,ba, b non tous deux nuls, a∧ba \wedge b est le plus grand diviseur commun ; a∧0=∣a∣a \wedge 0 = \lvert a\rvert ; convention 0∧0=00 \wedge 0 = 0.
  • Si a=bq+ra = bq + r, alors a∧b=b∧ra \wedge b = b \wedge r.
  • Algorithme d'Euclide : le PGCD est le dernier reste non nul.
  • D(a)∩D(b)=D(a∧b)\mathcal{D}(a) \cap \mathcal{D}(b) = \mathcal{D}(a \wedge b) : tout diviseur commun divise le PGCD. Deux PGCD qui se divisent l'un l'autre sont égaux.
À retenir PPCM
  • Pour a,ba, b non nuls, a∨ba \vee b est le plus petit multiple commun strictement positif ; a∨0=0a \vee 0 = 0.
  • Les multiples communs de aa et bb sont les multiples de a∨ba \vee b : si a∣ca \mid c et b∣cb \mid c, alors a∨b∣ca \vee b \mid c (et pas forcément ab∣cab \mid c).
  • (a∧b)(a∨b)=∣ab∣(a \wedge b)(a \vee b) = \lvert ab\rvert.
À retenir Nombres premiers
  • pp est premier si p≥2p \geq 2 et si ses seuls diviseurs positifs sont 11 et pp ; 11 n'est pas premier.
  • Le plus petit diviseur d≥2d \geq 2 d'un entier n≥2n \geq 2 est premier. Si nn n'a aucun diviseur premier p≤np \leq \sqrt n, il est premier.
  • Crible d'Ératosthène : barrer les multiples de chaque nombre premier, en commençant par son carré, s'arrêter quand p2>Np^2 > N.
  • Théorème d'Euclide : il y a une infinité de nombres premiers.
À retenir Décomposition en facteurs premiers
  • Tout n≥2n \geq 2 s'écrit de façon unique p1α1⋯pkαkp_1^{\alpha_1}\cdots p_k^{\alpha_k}, avec p1<⋯<pkp_1 < \cdots < p_k premiers et αi≥1\alpha_i \geq 1.
  • Un nombre premier qui divise un produit divise l'un des facteurs (souvent appelé lemme d'Euclide).
  • Les diviseurs positifs de nn sont les ∏piβi\prod p_i^{\beta_i} avec 0≤βi≤αi0 \leq \beta_i \leq \alpha_i ; il y en a ∏(αi+1)\prod(\alpha_i + 1).
  • PGCD : plus petits exposants ; PPCM : plus grands exposants.

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 20 méthodes, 21 pièges corrigés, la carte mentale, 44 exercices corrigés, 5 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit

Plan du cours

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

  1. Montrer qu'un entier en divise un autre
  2. Démontrer une divisibilité qui dépend de nn par récurrence
  3. Effectuer une division euclidienne et raisonner sur les restes
  4. Calculer un PGCD par l'algorithme d'Euclide
  5. Montrer qu'un entier divise un PGCD, ou que deux PGCD sont égaux
  6. Trouver le PGCD de deux entiers qui dépendent de nn
  7. Calculer un PPCM, résoudre un problème de période ou un système PGCD-PPCM
  8. Résoudre une équation en entiers
  9. Montrer qu'un entier est premier ou composé
  10. Montrer qu'il existe une infinité de nombres premiers d'une forme donnée
  11. Utiliser la décomposition en facteurs premiers
  12. Programmer l'arithmétique en Python
  13. Montrer que deux entiers sont premiers entre eux, rendre une fraction irréductible
  14. Calculer avec les valuations pp-adiques
  15. Obtenir une relation de Bézout
  16. Résoudre ax+by=cax + by = c dans Z2\mathbb{Z}^2
  17. Utiliser Bézout et Gauss pour une divisibilité ou une coprimalité
  18. Calculer modulo nn
  19. Inverser modulo nn et résoudre ax≡b [n]ax \equiv b \ [n]
  20. Résoudre un système de deux congruences à la main

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (18)

Entraînement (19)

Approfondissement (7)

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Questions fréquentes

Comment écrire la division euclidienne d'un entier négatif ?

Pour a∈Za \in \mathbb{Z} et b∈N∗b \in \mathbb{N}^*, il existe un unique couple (q,r)(q, r) tel que a=bq+ra = bq + r et 0≤r<b0 \leq r < b ; le quotient est la partie entière q=⌊ab⌋q = \left\lfloor \frac ab\right\rfloor. Le reste n'est jamais négatif : −17=5×(−4)+3-17 = 5 \times (-4) + 3, quotient −4-4 et reste 33. L'égalité −17=5×(−3)−2-17 = 5 \times (-3) - 2 est vraie, mais ce n'est pas la division euclidienne.

Comment calculer un PGCD avec l'algorithme d'Euclide ?

On divise le plus grand entier par le plus petit, puis le diviseur par le reste, et ainsi de suite : le PGCD est le dernier reste non nul. Cela marche parce que, si a=bq+ra = bq + r, les diviseurs communs de aa et bb sont ceux de bb et rr. Par exemple 75=42+3375 = 42 + 33, 42=33+942 = 33 + 9, 33=3×9+633 = 3 \times 9 + 6, 9=6+39 = 6 + 3, 6=2×36 = 2 \times 3 : donc 75∧42=375 \wedge 42 = 3.

Quel lien entre le PGCD et les diviseurs communs ?

Les diviseurs communs de aa et bb sont exactement les diviseurs de leur PGCD : D(a)∩D(b)=D(a∧b)\mathcal{D}(a) \cap \mathcal{D}(b) = \mathcal{D}(a \wedge b). Un entier qui divise aa et bb divise donc a∧ba \wedge b. Ce résultat se démontre par l'algorithme d'Euclide, et il permet de montrer que deux PGCD sont égaux par double divisibilité.

Si a et b divisent c, est-ce que ab divise c ?

Pas en général : 66 et 99 divisent 1818, mais 5454 ne divise pas 1818. Ce qui est toujours vrai, c'est que le PPCM de aa et bb divise cc, puisque les multiples communs de aa et bb sont exactement les multiples de a∨ba \vee b.

Quelle relation entre PGCD, PPCM et produit ?

Pour des entiers non nuls, (a∧b)(a∨b)=∣ab∣(a \wedge b)(a \vee b) = \lvert ab\rvert. Sur les décompositions en facteurs premiers, le PGCD prend pour chaque nombre premier le plus petit des deux exposants, le PPCM le plus grand. Avec 72=23×3272 = 2^3 \times 3^2 et 108=22×33108 = 2^2 \times 3^3, on trouve 72∧108=3672 \wedge 108 = 36, 72∨108=21672 \vee 108 = 216 et 36×216=72×10836 \times 216 = 72 \times 108.

Comment savoir si un entier est premier ?

Un entier n≥2n \geq 2 est premier si ses seuls diviseurs positifs sont 11 et nn ; 11 n'est pas premier. Il suffit d'essayer les nombres premiers pp tels que p2≤np^2 \leq n : si aucun ne divise nn, alors nn est premier. Ainsi 221=13×17221 = 13 \times 17 est composé, alors que 211211 est premier, puisque ni 22, 33, 55, 77, 1111 ni 1313 ne le divisent et que 172>21117^2 > 211. Pour lister tous les nombres premiers jusqu'à NN, on utilise le crible d'Ératosthène.

Pourquoi y a-t-il une infinité de nombres premiers ?

Si p1,…,pkp_1, \ldots, p_k étaient tous les nombres premiers, l'entier N=p1p2⋯pk+1N = p_1 p_2 \cdots p_k + 1 aurait un diviseur premier, égal à l'un des pip_i ; ce pip_i diviserait NN et le produit p1⋯pkp_1 \cdots p_k, donc leur différence 11, ce qui est impossible. C'est le théorème d'Euclide.

Combien un entier a-t-il de diviseurs ?

On le décompose en facteurs premiers, n=p1α1⋯pkαkn = p_1^{\alpha_1} \cdots p_k^{\alpha_k} : ses diviseurs positifs sont les p1β1⋯pkβkp_1^{\beta_1} \cdots p_k^{\beta_k} avec 0≤βi≤αi0 \leq \beta_i \leq \alpha_i, et il y en a (α1+1)⋯(αk+1)(\alpha_1 + 1)\cdots(\alpha_k + 1). Par exemple 72=23×3272 = 2^3 \times 3^2 a 4×3=124 \times 3 = 12 diviseurs positifs, et 600=23×3×52600 = 2^3 \times 3 \times 5^2 en a 2424.

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.

Toute ta prépa au même endroit

Pour chaque chapitre : le cours, l'essentiel, les méthodes, les pièges, les exercices corrigés, les problèmes de concours, et un assistant qui répond à tes questions. Programmes du Maroc et de France.

Essayer gratuitement Prepa Help

← Suites récurrentes