I – Divisibilité et congruence

1. Divisibilité

Dans toute la suite de cette section, on notera par l'ensemble des nombres entiers relatifs (i.e. ) et par l'ensemble des nombres entiers naturels (i.e. ).

Définition

Soient et deux entiers relatifs. On dit que divise (ou que est un multiple de ) s'il existe tel que . On note ceci par .

Si on a divise , alors divise . Par exemple, comme divise , alors divise également .

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 , . On suppose . On appelle division euclidienne de par , l'opération qui à , associe le couple d'entiers relatifs tel que . Un tel couple existe forcément et est unique.

Vocabulaire

En reprenant les notations du théorème, s'appelle le dividende, le diviseur, le quotient et le reste de la division euclidienne.

Exemple

On souhaite effectuer la division euclidienne de par . Posons-la :

Division euclidienne

  • On cherche combien de fois est contenu dans (cela ne sert à rien de commencer par car ). On a et donc on écrit sous le diviseur et le reste . Puis, on abaisse le chiffre des unités qui est .
  • On recommence : combien de fois est-il contenu dans ? Comme et , est contenu fois dans et il reste .
  • Comme , la division euclidienne est terminée : on a .

Donnons enfin une propriété qui nous sera utile dans la section suivante.

Propriété

Soit tel que . Deux entiers relatifs et ont le même reste dans la division euclidienne par si et seulement si est un multiple de .

3. Congruences dans

Définition

On dit que deux entiers relatifs et sont congrus modulo (où est un entier naturel supérieur ou égal à ) si et ont le même reste dans la division euclidienne par . On note alors .

On remarque que est un multiple de si et seulement si .

Exemple

Par exemple, .

Congruences

On signale que la congruence est une relation d'équivalence.

Propriétés

Soit . Pour tout , , :

  • (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 . Soient , , et tels que et . Alors on a la compatibilité avec :

  • L'addition : .
  • La multiplication : .
  • Les puissances : pour tout , .

Exemple

Comme , et , on a .

II – PGCD et théorème de Bézout

1. Plus Grand Commun Diviseur

Définition

Soient , non tous nuls. Le Plus Grand Commun Diviseur de et (noté ) est le plus grand entier positif qui les divise simultanément.

Avec cette définition, on peut dégager quelques propriétés.

Propriétés

Soient , non tous nuls.

  • Pour tout ,
  • Si , alors

Il existe une manière de déterminer le de deux entiers naturels non nuls et avec appelée Algorithme d'Euclide.

Algorithme d'Euclide

Soient , non tous nuls. Pour obtenir , on procède comme suit :

  1. On fait la division euclidienne de par et on appelle le reste.
  2. Si , alors .
  3. 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 est égal à 1.

Petite remarque : si on note le de deux nombres et , alors on a que et sont deux nombres premiers entre eux.

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 et deux entiers relatifs non nuls. On note leur PGCD. Alors il existe deux entiers relatifs et tels que .

Théorème de Bézout

Une conséquence de ce théorème est que et sont premiers entre eux si et seulement s'il existe deux entiers relatifs et tels que .

Exemple

Calculons et déduisons-en deux entiers relatifs et tels que .

Commençons par calculer le de et par l'algorithme d'Euclide :

La division euclidienne de par donne .

La division euclidienne de par donne .

La division euclidienne de par donne .

On a . Déterminons et :

Donc .

On a par conséquent et . L'algorithme que l'on vient d'utiliser pour trouver et s'appelle l'algorithme d'Euclide étendu.

Résolution d'une congruence simple

Supposons que l'on souhaite résoudre une congruence du type d'inconnue . On pose . Alors :

  1. 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 .
  2. Si , cela revient à résoudre la congruence , et on se ramène au cas 1 (avec la nouvelle congruence à résoudre).

Exemple

On souhaite résoudre la congruence . Alors, comme , on a . On se ramène donc à résoudre (où et sont premiers entre eux).

On écrit l'identité de Bézout appliquée à et : . Donc les solutions à la congruence du début sont les entiers vérifiant (i.e. les de la forme $x = 3k

  • 1ùk \in \mathbb{Z}$).

3. Lemme de Gauss

Lemme de Gauss

Soient , et trois entiers non nuls. Si et est premier avec , alors .

Corollaire

Soient , et trois entiers non nuls. Si , et que et sont premiers entre eux, alors .

4. Équations diophantiennes

Définition

Une équation diophantienne linéaire en deux variables et est une équation de la forme où les coefficients , et sont des entiers relatifs et où les solutions sont également des entiers relatifs.

Solutions de

En reprenant les notations précédentes, on pose . Alors :

  • Si , on cherche une solution particulière à que l'on note . Alors les solutions de sont les couples et .
  • Sinon, n'a pas de solution.

Exemple

On cherche à résoudre l'équation diophantienne . Commençons par chercher une solution particulière .

Comme , on a . En divisant les deux côtés de l'égalité par , on a .

Cherchons une solution particulière à . On écrit l'identité de Bézout appliquée à et : . Ainsi, en multipliant les deux côtés de l'égalité par , on obtient : .

On a trouvé une solution particulière à qui est le couple ) où et . On pourrait appliquer la formule pour donner la forme générale des solutions de , mais essayons de ne pas l'utiliser.

Soit une autre solution de . On a . D'où (en passant les et du même côté de l'égalité et en faisant de même pour et , puis en factorisant).

Ainsi, on a que . Or, et sont premiers entre-eux, donc par le lemme de Gauss, . Il existe donc tel que , d'où .

De même, avec et premiers entre eux, donc par le lemme de Gauss, . Il existe donc tel que , d'où .

En réinjectant tout ça dans , on obtient .

Les solutions de sont donc les couples et (et on a bien les mêmes résultats qu'avec la formule).

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 est dit premier si ses seuls diviseurs positifs sont et lui-même.

Exemple

, , , , et sont des nombres premiers.

2. Propriétés

Voici quelques propriétés basiques que possèdent les nombres premiers.

Propriétés

Soit supérieur ou égal à 2, alors on a les propriétés suivantes :

  • 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 un nombre premier et et deux entiers. Si alors ou .

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.

Démonstration

Petit théorème de Fermat

Soit un nombre premier et un entier non divisible par . Alors .

Cela revient au même de dire que si est un entier quelconque et que est un nombre premier, alors .

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 supérieur ou égal à 2, alors peut s'écrire de la façon suivante :

, , ... , des nombres premiers tels que et , , ... , des entiers naturels non nuls.

Exemple

Décomposons en produit de facteurs premiers.

  • ( est le plus petit nombre premier qui divise ).
  • ( est le plus petit nombre premier qui divise ).
  • ( est le plus petit nombre premier qui divise ).
  • ( est le plus petit nombre premier qui divise ).
  • ( est un nombre premier, c'est terminé).

On a donc .

Vous avez aimé ce cours ?

Faîtes-le nous savoir dans les commentaires !

Avatar (prévisualisation)
Il n'y a pas de commentaire sur ce cours pour le moment.