Chapitres Maths en MPSI, PCSI, MP2I, PTSI
Chapitres Maths en MPSI, PCSI, MP2I, PTSI
Cours : Arithmétique en Maths Sup en MPSI, PCSI et PTSI
Résumé de cours Exercices et corrigés
Cours en ligne de Maths en Maths Sup
Résumé de cours et méthodes – Maths sup Arithmétique
Plan :
1. Divisibilité
2. PGCD de deux éléments
3. Nombres premiers entre eux
4. PPCM
5. Nombres premiers
6. Relation de congruence
7. Synthèse des méthodes
On suppose dans tout ce chapitre sauf indication contraire que ou .
Si vous rencontrez des difficultés lors de votre entraînement sur l’arithmétique, n’hésitez pas à consulter nos profs de maths à domicile.
1. Divisibilité
1.1. Diviseurs et multiples
Si et , il y a équivalence entre :
divise ou est un diviseur de
est un multiple de
il existe tel que .
On note .
⚠️ Tout entier divise .
⚠️ ne divise que lui-même.
Si ,
l’ensemble des multiples de est .
Il n’y a pas de notation consacrée pour les diviseurs de .
J’utiliserai pour noter l’ensemble des diviseurs de .
si et ,
.
1.2. Propriétés
la relation « » est une relation d’ordre sur mais n’est pas une relation d’ordre sur .
Si ,
et .
et
si et , .
1.3. Diviseurs et multiples communs
Si sont des éléments de , on appelle
diviseur commun de tout tel que .
👍 sont des diviseurs communs à toute famille finie d’éléments de .
multiple commun de tout tel que .
👍 est un multiple commun de la famille .
1.4. Division euclidienne
Théorème de division euclidienne
Si et , il existe un unique couple tel que où
est le dividende de par
est le reste de la division euclidienne de par .
Remarque : et .
PROF DE MATHS PARTICULIER
Des cours de qualité et enseignants aguerris
Préparer des concours ou s'exercer
Avis Google France ★★★★★ 4,9 sur 5
2. PGCD de deux éléments
2.1. Définition et propriétés du PGCD
Soient et deux éléments de .
On appelle PGCD de et et on note l’entier naturel défini par
si
si , .
Propriétés
Si et sont deux éléments de ,
Si .
Si .
Si , .
Si est le reste de la division euclidienne de par , .
si , et sont dans
Relation de Bezout : soient et deux éléments de , il existe et dans tels que
⚠️ et ne sont pas uniques !
Si est solution, pour tout , est solution.
2.2. Algorithme d’Euclide
Algorithme d’Euclide
Soient et dans tels que
On note .
Par récurrence :
si , on note le reste de la division euclidienne de par .
Si est le dernier reste non nul (et donc ), .
Ces calculs permettent de trouver une relation de Bezout par une méthode appelée remontée de l’algorithme d’Euclide :
On part de la relation
écrite sous la forme
et on remplace en fonction de et , ce qui permet d’exprimer en fonction de et .
Et on réitère jusqu’à exprimer en fonction de et donc en fonction de et . On obtient une identité de Bezout.
2.3. Algorithme d’Euclide étendu
On se ramène au cas où et sont dans avec
On note , .
On note le premier reste nul dans la suite des divisions euclidiennes.
Plus précisément si , on écrit : avec .
On suppose et .
Alors les familles définies par
,
,
sont telles que
et on retient que
.
On peut mener les calculs en tableau :
initialisation
Calcul de la ligne si l’on connaît les lignes et si
par division euclidienne de et , on calcule le quotient placé en et le reste placé en .
on calcule
et on calcule de même ce qui permet de compléter la ligne :
On termine en ayant :
Les calculs de et sont inutiles.
sur la ligne donnant le dernier reste non nul, on obtient , et
👍 cette méthode est la méthode à utiliser en Python pour programmer le calcul du pgcd et de la relation de Bezout.
Exemple : relation de Bezout pour et par la remontée de l’algorithme et par l’algorithme d’Euclide étendu.
Correction : Algorithme d’Euclide.
Les divisions successives donnent :
le reste suivant est nul
Le dernier reste non nul est égal à 1, donc .
Bezout par remontée de l’algorithme d’Euclide
Par l’algorithme d’Euclide étendu
Dans les deux cas, .
3. Nombres premiers entre eux
3.1. Deux nombres premiers entre eux
Définition :
Soient et deux éléments de . On dit que et sont premiers entre eux lorsque .
👍 ssi sont les seuls diviseurs communs de et .
Propriétés
Théorème de Bezout
Soient et deux éléments de .
ssi il existe et dans tels que .
Soient ,
et .
Théorème de Gauss
Soient , et dans .
et .
Soient , et dans .
divise , divise et
divise .
Soient et deux éléments de et ,
alors et
où et .
Pour tout , il existe un unique couple tels que avec .
On dit que est la forme irréductible du rationnel .
3.2. Généralisation au cas de entiers
Si , et ,
on appelle PGCD de et on note l’entier naturel défini par
si ,
si ,
Identité de Bezout
Si , et ,
Il existe tel que
.
Si , et ,
.
Si , et , on dit que :
sont premiers dans leur ensemble si
sont premiers 2 à 2 si .
Théorème de Bezout
Si , et ,
sont premiers dans leur ensemble ssi , .
4. PPCM
Soient et deux éléments de .
On appelle PPCM de et et on note l’entier naturel défini par
si ,
Propriétés :
Soient et de
si ,
Si , et ,
on définit le PPCM de par
si ,
si ,
est le plus petit tel que .
Si , et ,
.
5. Nombres premiers
5.1. Ensemble
est premier lorsque les seuls diviseurs positifs de sont et .
On note l’ensemble des nombres premiers.
est un ensemble infini.
Si , n’est pas premier ssi admet un diviseur premier inférieur ou égal à .
Crible d’Eratosthène
Soit , . Pour obtenir la liste des nombres premiers inférieurs ou égaux à ,
on écrit la liste des entiers entre et .
pour tout , si n’a pas été supprimé par le passage précédent, on supprime dans la liste les multiples de strictement supérieurs à qui n’ont pas encore été supprimés lors des étapes précédentes.
La liste obtenue après le dernier passage est la liste des nombres premiers entre et .
Correction : Dans la liste des entiers de à ,
on barre les nombres pairs entre et 100
on barre les multiples stricts de 3 non encore barrés soit
on barre les multiples stricts de 5 soit multiples de qui n’avaient pas encore été barrés
on barre les entiers multiples de qui n’avaient pas encore été barrés.
Les entiers premiers inférieurs à 100 sont donc .
5.2. Valuation -adique
Si et ,
la valuation –adique de est .
Si et
.
Si , l’ensemble des tels que est fini.
On dit que la famille est une famille d’entiers presque nuls.
5.3. Décomposition primaire
Soit une famille d’entiers presque nulle (c’est à dire sauf éventuellement pour un nombre fini d’entiers )
si , on note
si , on note
Tout entier s’écrit d’une et d’une seule façon sous la forme
.
Cette décomposition est appelée décomposition primaire de .
Soient et deux éléments de
divise ssi ,
.
6. Relation de congruence
6.1. Rappels
Si , ,
définit une relation d’équivalence sur appelée relation de congruence modulo .
Pour la relation de congruence modu- lo , il y a classes d’équivalence :
, .
6.2. Propriétés
la relation de congruence modulo est une relation d’équivalence sur vérifiant si et ,
si ,
si ,
Soient et .
et .
Petit théorème de Fermat
Soit un nombre premier.
pour tout ,
si ne divise pas , .
7. Synthèse de méthodes
7.1. Déterminer le pgcd de et si
Se ramener si nécessaire au cas et puisque .
Utiliser l’algorithme d’Euclide.
Utiliser la décomposition primaire de et .
7.2. Montrer que si
Utiliser l’algorithme d’ Euclide.
Introduire diviseur de et et montrer que .
Utiliser la décomposition primaire de et .
Supposer qu’il existe qui divise et et démontrer que l’on arrive à une contradiction.
Trouver et dans tels que .
7.3. Utiliser si
.
Si divise et , .
Introduire et dans tels que .
Si de plus divise , divise (théorème de Gauss).
7.4. Démontrer que divise
Trouver tel que .
Montrer que le reste de la division euclidienne de par est nul.
Montrer que .
Montrer que .
Écrire où sont premiers deux à deux et montrer que , divise .
Montrer que vérifie , divise et que .
Appliquer le théorème de Fermat :
montrer que est premier et que avec
montrer que est premier et que avec .
7.5. Démontrer que n’est pas premier
Trouver diviseur de tel que .
Trouver un entier premier tel que divise .
(on rappelle qu’un nombre non premier admet un diviseur premier tel que ).
Complétez vos révisions et vos entraînements en maths au programme de Maths Sup, avec les autres cours en ligne de MPSI, PCSI et PTSI disponibles gratuitement :