I – Divisibilité et congruence
1. Divisibilité
Dans toute la suite de cette section, on notera par
Définition
Soient
Propriétés
- Tout entier relatif
divise (car ). divise tout entier relatif (car ).- Si
et alors pour tout , .
2. Division euclidienne
La division euclidienne est une notion mathématique que l'on aborde très tôt au cours de notre scolarité (dès la classe de CM1). Nous allons tenter de formaliser ceci :
Théorème de la division euclidienne
Soient
Vocabulaire
En reprenant les notations du théorème,
Donnons enfin une propriété qui nous sera utile dans la section suivante.
Propriété
Soit
3. Congruences dans
Définition
On dit que deux entiers relatifs
On signale que la congruence est une relation d'équivalence.
Propriétés
Soit
(réflexivité)- Si
, alors (symétrie) - Si
, et si , alors (transitivité)
De plus, la congruence est compatible avec les opérations usuelles sur les entiers relatifs.
Propriétés
Soit
- L'addition :
. - La multiplication :
. - Les puissances : pour tout
, .
II – PGCD et théorème de Bézout
1. Plus Grand Commun Diviseur
Définition
Soient
Avec cette définition, on peut dégager quelques propriétés.
Propriétés
Soient
- Pour tout
, - Si
, alors
Il existe une manière de déterminer le
Algorithme d'Euclide
Soient
- On fait la division euclidienne de
par et on appelle le reste. - Si
, alors . - Sinon on recommence l'étape 1 en remplaçant
par et par .
Terminons cette section par une définition.
Nombres premiers entre eux
On dit que deux nombres sont premiers entre eux si leur
2. Théorème de Bézout
Un résultat fondamental de l'arithmétique est le théorème de Bachet-Bézout (que l'on rencontre parfois sous le nom d'identité de Bézout).
Théorème de Bachet-Bézout
Soient
Théorème de Bézout
Une conséquence de ce théorème est que
Résolution d'une congruence simple
Supposons que l'on souhaite résoudre une congruence du type
- Si
ne divise pas , on cherche deux entiers et tels que (avec l'algorithme d'Euclide étendu par exemple). Les solutions de la congruence sont alors les entiers vérifiant . - Si
, cela revient à résoudre la congruence , et on se ramène au cas 1 (avec la nouvelle congruence à résoudre).
3. Lemme de Gauss
Lemme de Gauss
Soient
Corollaire
Soient
4. Équations diophantiennes
Définition
Une équation diophantienne linéaire en deux variables
Solutions de
En reprenant les notations précédentes, on pose
- Si
, on cherche une solution particulière à que l'on note . Alors les solutions de sont les couples où et . - Sinon,
n'a pas de solution.
III – Nombres premiers
1. Définition
Commençons cette section par définir ce qu'est un nombre premier. Il s'agit là d'une notion dont entend parler très tôt au cours de notre scolarité, sans pour autant vraiment rentrer dans le sujet. Détaillons donc un peu tout ceci.
Nombre premier
Un nombre entier
2. Propriétés
Voici quelques propriétés basiques que possèdent les nombres premiers.
Propriétés
Soit
- Si
n'admet aucun diviseur premier inférieur ou égal à , alors est premier. - Si
n'est pas premier alors admet au moins un diviseur premier inférieur ou égal à . - Si
est premier et ne divise pas un entier , alors et sont premiers entre eux.
Lemme d'Euclide
Soit
On donne enfin un résultat fondamental (mais qui reste très simple) sur l'ensemble des nombres premiers.
Infinité de nombres premiers
Il existe une infinité de nombres premiers.
Petit théorème de Fermat
Soit
3. Décomposition de nombres
Passons maintenant à un résultat fondamental de l'arithmétique : le principe de décomposition en produit de facteurs premiers (il s'agit même là d'un théorème qui est sobrement intitulé théorème fondamental de l'arithmétique).
Théorème fondamental de l'arithmétique
Soit
où