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.
- 20méthodes
- 44exercices corrigés
- 5problèmes
- 21pièges
- 30figures
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 ; 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 :
- écrire une division euclidienne et raisonner sur les restes ;
- calculer un PGCD par l'algorithme d'Euclide, un PPCM, et raisonner sur les diviseurs communs ;
- reconnaître un nombre premier et utiliser la décomposition en facteurs premiers ;
- programmer ces calculs en Python.
L’essentiel du chapitre Extrait gratuit
- s'il existe tel que . ; est multiple de tout entier et ne divise que .
- Transitivité ; si et , alors pour tous .
- Si et , alors . Si et , alors .
- divise .
- Pour et , il existe un unique tel que et . Le quotient est .
- si et seulement si .
- Deux entiers ont le même reste par si et seulement si divise leur différence. Le reste d'une somme, d'un produit, d'une puissance ne dépend que des restes.
- Pour non tous deux nuls, est le plus grand diviseur commun ; ; convention .
- Si , alors .
- Algorithme d'Euclide : le PGCD est le dernier reste non nul.
- : tout diviseur commun divise le PGCD. Deux PGCD qui se divisent l'un l'autre sont égaux.
- Pour non nuls, est le plus petit multiple commun strictement positif ; .
- Les multiples communs de et sont les multiples de : si et , alors (et pas forcément ).
- .
- est premier si et si ses seuls diviseurs positifs sont et ; n'est pas premier.
- Le plus petit diviseur d'un entier est premier. Si n'a aucun diviseur premier , il est premier.
- Crible d'Ératosthène : barrer les multiples de chaque nombre premier, en commençant par son carré, s'arrêter quand .
- Théorème d'Euclide : il y a une infinité de nombres premiers.
- Tout s'écrit de façon unique , avec premiers et .
- Un nombre premier qui divise un produit divise l'un des facteurs (souvent appelé lemme d'Euclide).
- Les diviseurs positifs de sont les avec ; il y en a .
- PGCD : plus petits exposants ; PPCM : plus grands exposants.
Une méthode du chapitre Extrait gratuit
On demande le PGCD de deux entiers donnés, surtout s'ils sont grands, ou une justification algorithmique.
Si , alors . L'algorithme d'Euclide divise successivement ; le PGCD est le dernier reste non nul.
- Se ramener à (valeurs absolues).
- Écrire les divisions successives dans un tableau : dividende, diviseur, quotient, reste.
- S'arrêter au premier reste nul ; lire le dernier reste non nul.
- Contrôler : le résultat divise et .
« Par l'algorithme d'Euclide : , , …, . Le dernier reste non nul est , donc . »
Calculer .
| dividende | diviseur | quotient | reste |
|---|---|---|---|
Le dernier reste non nul est : . Contrôle : et .
- Prendre le dernier reste, qui est nul, au lieu du dernier reste non nul.
- Écrire une égalité dont le reste dépasse le diviseur.
- S'arrêter trop tôt, sur un reste qui ne divise pas le précédent.
Exercices 5, 11, 26 et 28, problèmes 1 et 2.
Un exercice corrigé Extrait gratuit
On veut couvrir le panneau rectangulaire d'une bibliothèque de quartier, de cm sur cm, par des carreaux carrés identiques, dont le côté est un nombre entier de centimètres, sans découpe ni chevauchement.
- Montrer que le côté d'un carreau doit diviser et .
- Quel est le plus grand côté possible ? Combien faut-il alors de carreaux ?
- Quels sont tous les côtés possibles ?
- 1 : une rangée le long d'un bord contient un nombre entier de carreaux.
- 2 : calculer par l'algorithme d'Euclide.
- 3 : les diviseurs communs sont les diviseurs du PGCD.
Un pavage exact par des carrés de côté demande que tienne un nombre entier de fois dans chaque côté : est un diviseur commun. Le plus grand est le PGCD, et l'ensemble des côtés possibles est l'ensemble des diviseurs du PGCD.
1. Le long du côté de cm, les carreaux sont posés bord à bord, sans découpe : si l'on en pose , alors . De même le long de l'autre côté. Donc divise et . Réciproquement, si divise les deux, une grille de colonnes et rangées pave exactement le panneau.
2. Par l'algorithme d'Euclide :
Donc : le plus grand côté est cm. Il faut carreaux.
3. Les côtés possibles sont les diviseurs communs de et , c'est-à-dire les diviseurs positifs de : cm.
Un problème de pavage exact ou de partage en parts égales se traduit par des diviseurs communs ; le plus grand est le PGCD, et tous les autres sont ses diviseurs. Voir la méthode 4.
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 gratuitUne question ? WhatsAppPlan du cours
- 1. Divisibilité dans
- 1.1 Diviseurs et multiples
- 1.2 Propriétés
- 1.3 Inversibles, entiers associés, divisibilité et ordre
- 2. Division euclidienne
- 2.1 Le théorème
- 2.2 Restes et disjonction de cas
- 2.3 Quotient et partie entière, calcul pratique
- 3. PGCD de deux entiers et algorithme d'Euclide
- 3.1 Définition
- 3.2 Le lemme des restes
- 3.3 L'algorithme d'Euclide
- 3.4 Diviseurs communs et PGCD
- 3.5 Entiers premiers entre eux
- 4. PPCM
- 4.1 Définition
- 4.2 Multiples communs
- 5. Nombres premiers
- 5.1 Définition, plus petit diviseur
- 5.2 Le crible d'Ératosthène
- 5.3 Il y a une infinité de nombres premiers
- 6. Décomposition en facteurs premiers
- 6.1 Le théorème fondamental de l'arithmétique
- 6.2 Un nombre premier qui divise un produit
- 6.3 Les diviseurs d'un entier
- 6.4 PGCD et PPCM par la décomposition
- 7. Arithmétique en Python
- 7.1 Division et PGCD
- 7.2 Primalité, crible, décomposition
- 7.3 Exponentiation rapide
- 8. Valuations -adiques et forme irréductible
- 8.1 Valuation
- 8.2 Divisibilité, PGCD et PPCM par les valuations
- 8.3 Forme irréductible d'un rationnel
- 9. Relation de Bézout et lemme de Gauss
- 9.1 Relation de Bézout, algorithme d'Euclide étendu
- 9.2 Théorème de Bézout
- 9.3 Lemme de Gauss et conséquences
- 9.4 PGCD d'un nombre fini d'entiers
- 9.5 Démonstration de l'unicité de la décomposition
- 10. Congruences et petit théorème de Fermat
- 10.1 Rappel et opérations
- 10.2 Critères de divisibilité, cycles de restes
- 10.3 Inverse modulo , équation
- 10.4 Systèmes de deux congruences
- 10.5 Petit théorème de Fermat
- 10.6 Programmes Python
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.
- Montrer qu'un entier en divise un autre
- Démontrer une divisibilité qui dépend de par récurrence
- Effectuer une division euclidienne et raisonner sur les restes
- Calculer un PGCD par l'algorithme d'Euclide
- Montrer qu'un entier divise un PGCD, ou que deux PGCD sont égaux
- Trouver le PGCD de deux entiers qui dépendent de
- Calculer un PPCM, résoudre un problème de période ou un système PGCD-PPCM
- Résoudre une équation en entiers
- Montrer qu'un entier est premier ou composé
- Montrer qu'il existe une infinité de nombres premiers d'une forme donnée
- Utiliser la décomposition en facteurs premiers
- Programmer l'arithmétique en Python
- Montrer que deux entiers sont premiers entre eux, rendre une fraction irréductible
- Calculer avec les valuations -adiques
- Obtenir une relation de Bézout
- Résoudre dans
- Utiliser Bézout et Gauss pour une divisibilité ou une coprimalité
- Calculer modulo
- Inverser modulo et résoudre
- 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)
- Divisions euclidiennes de 1000 et de −1000 par 7
- Divisibilité de 5n³ + n par 6
- Divisibilité de 3^(2n+1) + 2^(n+2) par 7
- Restes d'un carré dans les divisions par 4 et par 8
- Algorithme d'Euclide pour 1071 et 462
- Deux PGCD qui dépendent de n
- Un système PGCD et PPCM
- Le nombre 2027 est-il premier ? Et 2021 ?
- Décomposer 360 et 756
- Le crible en Python
- Paver un panneau de 252 cm sur 198 cm
- Une fraction toujours irréductible
- Les zéros à la fin de l'écriture de factorielle 1000
- Bézout pour 473 et 220
- L'équation 147x + 495y = 12
- Deux calculs de restes
- Inverse modulo 30, congruence modulo 21
- Si a ∧ b = 1, alors (a + b) ∧ ab = 1
Entraînement (19)
- Le PGCD de 15a + 4b et 11a + 3b
- Les nombres de Mersenne
- Si a^m + 1 est premier, a est pair et m est une puissance de 2
- Les nombres 2^(2^n) + 1 et l'infinité des nombres premiers
- L'équation xy = 2x + 3y dans Z²
- Quels entiers sont différence de deux carrés ?
- L'équation 3x³ + xy + 4y³ = 349 dans N²
- Nombre et somme des diviseurs
- Deux entiers de somme 144 et de PPCM 420
- Critères de divisibilité par 9, par 11 et par 7
- Le problème d'Ibn al-Haytham
- L'équation x² + y² = 3z²
- Exponentiation rapide en Python
- Racine carrée d'un entier : entière ou irrationnelle
- Le petit théorème de Fermat par les coefficients binomiaux
- Systèmes de congruences
- Le théorème de Wilson
- Deux divisibilités par le petit théorème de Fermat
- Premiers dans leur ensemble, premiers deux à deux
Approfondissement (7)
- La règle de Thabit ibn Qurra pour les nombres amiables
- Le PGCD de a^m − 1 et a^n − 1
- La somme des chiffres de 4444^4444
- Le PGCD de deux termes de la suite de Fibonacci
- Le produit de diviseurs premiers entre eux
- Un chiffrement RSA à petits nombres
- Divisibilité de p² − 1 par 24 et de p^16 − 1 par 16 320
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.
- Diviseurs, nombres premiers et plus grand diviseur commun
- L'algorithme d'Euclide et la suite de Fibonacci
- Une majoration du PPCM des premiers entiers
- Un encadrement du nombre de nombres premiers
- Le petit théorème de Fermat et une suite récurrente
Questions fréquentes
Comment écrire la division euclidienne d'un entier négatif ?
Pour et , il existe un unique couple tel que et ; le quotient est la partie entière . Le reste n'est jamais négatif : , quotient et reste . L'égalité 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 , les diviseurs communs de et sont ceux de et . Par exemple , , , , : donc .
Quel lien entre le PGCD et les diviseurs communs ?
Les diviseurs communs de et sont exactement les diviseurs de leur PGCD : . Un entier qui divise et divise donc . 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 : et divisent , mais ne divise pas . Ce qui est toujours vrai, c'est que le PPCM de et divise , puisque les multiples communs de et sont exactement les multiples de .
Quelle relation entre PGCD, PPCM et produit ?
Pour des entiers non nuls, . 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 et , on trouve , et .
Comment savoir si un entier est premier ?
Un entier est premier si ses seuls diviseurs positifs sont et ; n'est pas premier. Il suffit d'essayer les nombres premiers tels que : si aucun ne divise , alors est premier. Ainsi est composé, alors que est premier, puisque ni , , , , ni ne le divisent et que . Pour lister tous les nombres premiers jusqu'à , on utilise le crible d'Ératosthène.
Pourquoi y a-t-il une infinité de nombres premiers ?
Si étaient tous les nombres premiers, l'entier aurait un diviseur premier, égal à l'un des ; ce diviserait et le produit , donc leur différence , 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, : ses diviseurs positifs sont les avec , et il y en a . Par exemple a diviseurs positifs, et en a .
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.