Arithmétique dans Z

Bonjour, dans ce chapitre, nous allons voir ce qu’est l’arithmétique, et plus particulièrement l’arithmétique modulaire et dans Z.

Voici la table des matières : ≠

• Divisibilité et division Euclidienne.
• PGCD.
• Algorithme d’Euclide.
• Nombres premiers entre eux.
• Théorème de Bézout et corollaires.
• PPCM.
• Une infinité de nombres premiers.
• Crible d’Ératosthène et Lemme d’Euclide.
• Congruences et petit théorème de Fermat.

 

Divisibilité et division Euclidienne :

Propriétés générales :

Vous vous souvenez surement de vos longs exercices de début de collège lorsqu’on vous demandait de poser et résoudre un nombre incalculable de division Euclidienne ?
Nous allons voir ici quelques théorèmes, ainsi que la résolution d’une division euclidienne en la posant sous forme d’équation.

Tout d’abord, rappelons la forme d’une division euclidienne :

Voyons le théorème de la division euclidienne, ce théorème dit que :
a est multiple de b, où b divise a, si, et seulement si, le reste dans la division euclidienne de a par b est égal à 0.
De manière analogue, on peut dire que b divise a s’il existe un q ∈ Z tel que a = b × q. On note alors b|a (b divise a).

Précisons que :
Si b > a alors a = b x 0 + a  donc le quotient est 0 et le reste a.
Si a = b alors a = b x 1 + 0  donc le quotient est 1 et le reste 0.
Si 2|a, alors a est pair.
Si a|1, alors a = 1 ou a = -1.
Si a|b et b|c, alors a|c.
Si a|b et a|c, alors a|b+c.
Si b|a et a|b, alors b = ±a.

Il existe une autre formule pour effectuer une division euclidienne et qui revient exactement au même : a = bq + r.

En effet, diviser 50 par 8 par exemple, revient à multiplier le diviseur par le quotient et à ajouter le reste.
50 = 8 × 6 + 2, avec a le dividende = 50, b le diviseur = 8, q le quotient = 6 et r le reste = 2. Evidemment, 0≤r<b.

Autre exemple, a = 6789 et b = 34, alors 6789 = 34 × 199 + 23. On constate bien que le reste est plus petit que le diviseur.

 

Propriétés de divisibilité dans Z :

Dans l’ensemble des entiers relatifs, on peut également ajouter quelques propriétés :

• Si b divise a, alors -b divise a également. Par exemple si 5 divise 10, alors -5 divise 10 également.

 

PGCD :

Prenons a et b, deux entiers dans Z, non tous les deux nuls.
Propriétés et vocabulaire :

• Le plus grand diviseur commun de a et de b est le plus grand entier qui divise à la fois a et à la fois b. Il se note pgcd(a,b).
  Par exemple, le pgcd(21,14) = 7, car 7 est le plus grand entier qui divise à la fois 14 et 21.
• Le pgcd a de (a,ka) = a, avec k ∈ Z et a ≥ 0.
  Par exemple le pgcd(10,9×10) = 10.
• Pour tout a ≥ 0, pgcd(a,0) = 0 et le pgcd(a,1) = 1.
  Il est important de rajouter que 0 est divisible par tout entier naturel.
• Le pgcd(a,b) = pgcd(b,r). Autrement dit, le pgcd de a et b est le pgcd de b et du reste de la division euclidienne de a par b.
  Par exemple, le pgcd(46,6) = pgcd(6,4). Le pgcd(6,4) = 2, et on constate que le pgcd(46,6) = 2 également. La propriété est donc vérifiée.
  Il existe une façon plus générale de démontrer cette égalité. On pose pgcd(a,b) = pgcd(b,a-qb) pour tout q ∈ Z.
  Pourquoi affirme on cela ? Prenons et supposons que d est un diviseur de a et de b, alors d divise bq – a = r.
  Si d est un diviseur de b et de r, alors d divise aussi bq + r = a, autrement dit, les diviseurs de a et de b sont les mêmes que ceux de b et de r.

 

Algorithme d’Euclide :

L’algorithme d’Euclide sert à calculer le pgcd de deux nombres a et b.
Il s’agit d’une décomposition, de divisions successives de a et b afin d’arriver à un reste nul, et donc de définir le pgcd de ces deux nombres.

Comment définit on cet algorithme ?

Un exemple, prenons a = 600 et b = 124, et calculons le pgcd de ces deux nombres grâce à l’algorithme d’Euclide.

On pose 600 = 4 × 124 + 104 qui est la division euclidienne de a par b suivant la propriété a = q × b + r.

On fait donc 124 = 104 × 1 + 20. En effet, b est devenu a, r est devenu b.
Puis, de la même manière, 104 = 20 × 5 + 4.
Vous avez compris, à présent, 20 = 4 × 5 + 0.

Sur la dernière ligne, le reste est nul, le pgcd est le dernier reste non nul, autrement dit, 4. 4 est donc le pgcd(600,124).

Justifions pourquoi pgcd(600,124) = 4.
Par le lemme vu précédemment qui dit que pgcd(a,b) = pgcd(b,r) appliqué à la première ligne, et ce lemme appliqué à la seconde, puis la troisième, et la dernière. Ainsi, on arrive au pgcd(4,0), donc le pgcd(600,124) = 4.

 

Nombres premiers entre eux :

Première propriété, a et b sont premiers entre eux si pgcd(a,b) = 1.

Prenons un exemple, ∀ a ∈ Z, a et a+1 sont premiers entre eux. Pourquoi ?
Si on prend d, un diviseur de commun à a et a +1. Alors d|a et d|a+1, donc d|a+1 – a.
Mais a+1 – a = 1 donc d|1. Le problème, c’est que les seuls diviseurs de 1 sont 1 et -1.
Par conséquent, la preuve est faite ! Le plus grand diviseur qui divise à la fois a et a+1 est 1, donc, a et a+1 sont premiers entre eux.

Exemple, 15 et 16 sont premiers entre eux, 57 et 58 sont premiers entre eux, etc…

 

Théorème de Bézout et corollaires :

Théorème de Bézout :

Qu’est ce que c’est ? A quoi sert il ?
Le théorème de Bézout est un moyen de « remonter » dans l’autre sens l’algorithme d’Euclide. Donnons sa définition :

Soient a et b deux entiers. Il existe des entiers u et v dans Z, tel que a × u + b × v = pgcd(a,b)
On appelle ces entiers u et v des coefficients de Bézout. Ils ne sont pas uniques ! Il existe une infinité de couple u et v qui conviennent.

Reprenons l’exemple que nous avions vu pour le pgcd. Prenons a = 600 et b = 124. On a vu que pgcd(600,124) = 4.

Si on remonte ligne par ligne, on peut décomposer de cette manière :

• 104 = 20 × 5 + 4 ⇒ 4 = 104 – 20 × 5
• 124 = 104 × 1 + 20 ⇒ 4 = 104 – (124 – 104 × 1) × 5, en simplifiant, on a 4 = 124 × (-5) + 104 × 6
• 600 = 4 × 124 + 104 ⇒ 4 = 124 × (-5) + (600 – 124 × 4) × 6
• Donc, 4 = 600 × 6 + 124 × (-29).

Prenons un autre exemple, a = 9945 et b = 3003.
Posons 9945u + 3003v = 39. 39 étant le pgcd(9945,3003).

Avec l’algorithme d’Euclide, on a donc :

• 9945 = 3003 × 3 + 936
• 3003 = 936 × 3 + 195
• 936 = 195 × 4 + 156
• 195 = 156 × 1 + 39
• 156 = 39 × 4 + 0.

Cherchons maintenant u et v en remontant ce calcul :

• 39 = 195 – 156 × 1
• 39 = 195 – (936 – 195 × 4)
  1 × 195 + (-1) × 936 + 195 × 4
  (-1) × 936 + 5 × 195
• 39 = (-1) × 936 + 5 × (3003 – 3 × 936)
  5 × 3003 + (-16) × 936
• 39 = 5 × 3003 – 16 × (9945 – 3 × 3003)
• 39 = (-16) × 9945 + 53 × 3003.

C’est beaucoup de calculs d’un coup, peut être n’avez vous pas compris les étapes. En fait, il faut à chaque point/ligne exprimer le reste en fonction de a et b de la ligne du dessus. Par exemple, lorsque nous mettons (936 – 194 × 4), cela n’est rien d’autre que 156 exprimé en fonction de la ligne au dessus, tout comme (3003 – 3 × 936) qui est égal à 195. Sur chaque ligne, le côté droit de l’équation doit être toujours égale au reste. Sur les lignes intermédiaires, nous essayons de factoriser afin de simplifier la suite du calcul.

 

Corollaire « réciproque » du théorème de Bézout : 

On peut se servir du théorème de Bézout pour démontrer que deux nombres sont premiers entre eux :

a et b sont premiers entre eux si et seulement si il existe u, v ∈ Z tels que a × u + b × v =1.

On va en quelque sorte faire la réciproque du théorème de Bézout, en supposant qu’il existe u et v, tels que a × u + b × v = 1.
Etant donné que le pgcd(a,b)|a, alors le pgcd(a,b)|a × u. En effet, par exemple, si pgcd(12,13) = 1, alors 1 divise n’importe quel multiple de 12, de même qu’il divise n’importe quel multiple de 13, donc on peut aussi dire que pgcd(a,b)|b × v.
Par conséquent, pgcd(a,b)|a × u + b × v = 1, donc pgcd(a,b) = 1.

Prenons un exemple, on veut montrer que (2n + 3) et (5n + 7) sont premiers entres eux et ∀n ∈ Z.
Il faut trouver des coefficients u et v tels que u(2n + 3) + v(5n + 7)= 1.
essayons de trouver deux coefficients, qui, lorsqu’on fait la somme des deux premiers termes, ces derniers s’annulent. Eh bien, par exemple, prenons u = 5 et v = -2.
On a donc 5(2n + 3) + (-2)(5n + 7) = 10n + 15 – 10n – 14. On simplifie :
On a donc 5(2n + 3) + (-2)(5n + 7) = 1 (10n – 10n = 0, 15 – 14 = 1).

 

En revanche, si on trouve u’ et v’, tels que a × u’ et b × v’ = d, cela implique seulement que pgcd(a,b)|d. Par exemple, on prend pgcd(12,8) = 4, on suppose que u’ = 1 et v’ = 3, alors a × u’ + b × v’ = 12 × 1 + 8 × 3 = 36. Mais 36 ne divise ni 12 ni 8, en revanche, 4 divise bien 36.

 

Corollaire sur le pgcd :

Ce corollaire est très simple et intuitif, il dit que si d|a et d|b, alors d|pgcd(a,b).

Prouvons le :

4 divise 16, et 4 divise 24, donc 4 divise le pgcd(16,24), car 4 divise 8.

 

 

Corollaire « lemme/théorème de Gauss » : 

Le corollaire de Gauss dit ceci :

Si a|b × c et que pgcd(a,b) = 1 (Donc que les nombres sont premiers entres eux) alors a|c.

On sait, d’après le théorème de Bézout, que ∃ u,v ∈ Z, tel que au + bv = 1.
Donc, si on multiplie par c des deux côtés, on a auc + bvc = c.
Mais comme a|bc, il existe un k dans Z, tel que bc = ak. On remplace maintenant bc par ak dans l’équation :
auc + akv = c. Si on factorise par a, on a :
a(uc + kv) = c. Donc ça y est, on a démontré que a|c.

Exemple, si 4|7 × c, alors alors 4|c. Supposons que c = 9, alors 4 divise bien 7 × 9 = 64.
Contre exemple, si on prend c = 5, alors étant donné que 4 ne divise pas 7 × 5, 4 ne divise pas 5.

 

Équations diophantiennes de type ax + by = c :

Nous allons ici expliquer comment résoudre ce qu’on appelle une équation diophantienne* à l’aide du théorème de Bézout.
* Une équation diophantienne est une équation dans laquelle les coefficients a et b et les inconnues x et y sont des entiers relatifs.

Soient a, b et c ∈ Z.

L’équation ax + by = c.

Énonçons les propriétés :

• L’équation (E) possède des solutions (x,y) dans Z² si et seulement si le pgcd(a,b)|c.
• Si le pgcd(a,b)|c, alors il existe une infinité de solutions, et ces dernières sont alors les (x,y) = (x0 + αk, y0 + βk), avec k parcourant Z, et x0,y0,α et β ∈ Z.

Démontrons ceci avec un exemple :

On va déterminer les entiers x et y ∈ Z, tels que 5x + 7y = 12 :

Tout d’abord, servons nous du théorème de Bézout, et résolvons l’équation 5x + 7y = 1, en essayant de trouver une solution particulière pour cette dernière :

On pose x = 1 – 7y/5 (On a simplement isolé x).

On va tenter de faire en sorte de prendre y tel que l’équation tombe sur un entier. Il faudrait par exemple, un nombre qui se termine par 1 ou 6, de sorte qu’en divisant par 5, le nombre trouvé se termine par 0 ou 5, et soit donc divisible par 5.

Prenons y = 3.
On a donc y = 3, et x = 1 – 7× 3/5 = -4.
On a là déjà, une solution particulière (x,y) = (-4;3).

A présent, trouvons l’ensemble des solutions, ou la solution générale de l’équation 5x + 7y = 1.

On connait une solution particulière de cette équation, alors on peut remplacer de telle sorte que :

5x + 7y = 5 × (-4) + 7 × 3.
Mettons les facteurs du même côté à présent :
5x – 5 × (-4) = -7y + 7 × 3.
Maintenant, nous factorisons :
5(x + 4) = 7(3 – y).
Nous allons pouvoir mettre en avant des relations de divisibilité entre nos valeurs. Regardons à gauche de l’égalité, on voit qu’il y a un facteur 5, mais si il y a un facteur 5 à gauche, il y a forcément un facteur 5 à droite, ce qui veut dire que 5 divise 7(3 – y). Cependant, ce facteur 5 ne peut pas être 7, car 5 et 7 sont premiers entre eux, donc le facteur 5 est obligatoirement dans la parenthèse.
ceci découle directement du théorème de Gauss, rappelons le : Si a divise bc, et si a et b sont premiers entre eux, alors a divise c.

Donc, on peut dire que que 5 divise 7(3 – y)
Mais 5 et 7 sont premiers entre eux, donc 5 divise 3 – y.

A présent, faisons la même chose dans l’autre sens, on voit que 7 divise 5(x + 4). 7 Ne peut pas diviser 5, donc 7 divise (x + 4).

Posons maintenant 3 – y = 5k. Si 5 divise 3 – y, on peut trouver un entier k, tel que 3 – y = 5k.
De même peut trouver un entier k’, tel que x + 4 = 7k’.

Maintenant posons l’équation 5x + 7y = 1, et remplaçons par les résultats que nous avons trouvé juste avant :
5(x + 4) = 7(3 – y) ⇒ 5 × 7k’ = 7 × 5k = 35k’ = 35k, donc k’ = k.

On peut donc écrire que :
x = -4 + 7k
y = 3 – 5k avec k ∈ Z.
Voilà les solutions de notre équation 5x + 7y = 1.

Pour finir, et résoudre l’équation initiale de cet exemple, on sait que nous avions trouvé les valeurs de x et y pour une solution particulière de l’équation 5x + 7y, nous avions vu que :
5 × (-4) + 7 × 3 = 1. Donc, si on multiplie par 12 de par et d’autre, on a 5 × (-4) × 12 + 7 × 3 × 12 = 12.
Mais là aussi, on peut tirer une solution particulière de notre équation, on peut dire que x = (-4) × 12 = -48 et y = 3 × 12 = 36. Solution particulière de (x,y) = (-48;36).

De manière analogue à tout à l’heure, on peut dire que les solutions de notre équation 5x + 7y = 12 sont :
x = -48 + 7k
y = 36 – 5k avec k ∈ Z.

Dernière étape, vérifions par réciproque que lorsque l’on remplace ces couples fonctionnent dans l’équation ,donc :

5(-48 + 7k) + 7(36 – 5k) = -240 + 35k + 252 – 35k.
35k et -35k se simplifient, et 252 – 240 = 12. L’équation est bien vérifiée.

 

PPCM :

Le plus petit commun diviseur de deux entiers a et b, est le plus petit entier positif, à la fois divisible par a et par b.
Par exemple, ppcm(12,9) = 36. 36 est le plus petit entier positif que 9 et 12 puisse diviser.

Le ppcm et le pgcd sont liés par une formule :

pgcd(a,b) × ppcm(a,b) = |a × b| (valeur absolue de a fois b).

Par exemple, le pgcd(12,9) = 3. Le ppcm(12,9) = 36 et pgcd(12,9) × ppcm(12,9) = 12 × 9 et 12 × 9 = 3 × 36.

Propriété du ppcm:

Si a|c et b|c, alors ppcm(a,b)|c.
Par exemple, si 6|36 et 9|36, alors le ppcm(6,9) = 18 et 18|36.

Attention en revanche à ne pas commettre l’erreur et dire que ab|c, car ici, 6 × 9 ne divise pas 36.

 

Un infinité de nombres premiers :

Commençons par énoncer un principe de base sur les nombres premiers :

Ce théorème dit que pour tout entier naturel n, (n ≠ 1), admet au moins un diviseur premier.

Il faut également ajouter que dans le produit donnant un nombre entier, un des facteurs est forcément un nombre premier, la preuve :
Par exemple , si n = 13 admet un diviseur premier, lui même, car 13|n.
Si n = 36, alors on décompose, on a 36 = 4 × 9. Mais ni 4 ni 9 ne sont premiers, donc on continu, 36 = 2² + 3³. 2 et 3 sont ils premiers, oui.

Une autre propriété, définit les nombres premiers comme ceci : Supposons un nombre entier p ≥ 2, on dit que ce nombre est premier si ses seuls diviseurs possibles sont 1 et p.

Nous allons maintenant démontrer par l’absurde, qu’il existe un nombre infini de nombres premiers :
On suppose qu’il existe un nombre fini de n nombres premiers qu’on note : p1, p2, p3, …, pn, et on pose N (nombre qu’on construit) = p1 × p2 × p3 × … × pn + 1.

On va à présent définir un entier i, tel que 1 ≤ i ≤ n et nous allons prouver que l’entier N, n’est pas divisible par pi (p indice i et non le nombre pi).

Par exemple, N = 2 × 3 × 5 × 7 × 11 × pn + 1.
En fait, l’énoncé nous demande de prouver que N n’est pas divisible par 2, par 3, par 5, par 7 , par 11 etc…
Pour commencer, pourquoi n’est il pas divisible par 2 ? Eh bien, on remarque que tout ceci « N = 2 × 3 × 5 × 7 × 11 × pn + 1 », on peut écrire également N = 2 ×( tout le reste ), donc 2 divise ce nombre là, quel qu’il soit, c’est un nombre pair, mais si on rajoute 1 ? Si on rajoute 1, on se trouve dans une situation ou le nombre en question devient forcément impair, et n’est donc plus divisible par 2.
on peut faire la même chose avec 3, on peut écrire N = 3 × (tout le reste), mais si on rajoute 1, eh bien l’entier N ne peut plus être divisible par 3… La même chose avec 5, 7, etc…

Disons les choses de manière plus rigoureuse maintenant :

Pour tout entier i, pi|p1 × p2 × p3 × … × pn donc si pi|N, alors pi|p1 × p2 × p3 × … × pn + 1. En d’autre termes si pi divise N, pi divise p1 × p2 × p3 × … × pn, il divise également N – p1 × p2 × p3 × … × pn, qui est égal à 1. Mais ceci est absurde, pourquoi ? Car cela voudrait dire que pi divise 1 également ? Mais si c’est le cas, pi ne peut pas être un entier, car aucun entier ne divise 1…

Essayons de voir ça avec une propriété de divisibilité dans Z. Si a|b et a|b+c, alors a|c. Dans notre cas de figure, a = pi, b = p1 × p2 × p3 × … × pn et c = 1.

En conclusion, N n’est pas divisible par pi, et n’a donc pas de diviseur premier, ce qui démontre bien la contradiction avec ce théorème : *(Pour tout entier naturel n, (n ≠ 1), admet au moins un diviseur premier.) Par conséquent, si N n’a pas de diviseur premier, c’est absurde, en conclusion à cela, on peut affirmer qu’il existe un nombre infini de nombres premiers.

 

Crible d’Ératosthène et lemme d’Euclide: 

Crible d’Ératosthène :

Le crible d’Ératosthène permet de trouver les premiers nombres premiers.

Pour notre exemple, on va écrire les 25 premiers entiers et utiliser le crible pour trouver les nombres premiers :

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

2 ne peut avoir comme diviseur que 1 et 2, donc 2 est premier. On raye donc 2 et on on fait de même avec tous les multiples suivants de 2 qui ne sont pas premiers :

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Ensuite, 3 est nécessairement premier, il n’est pas divisible par un nombre plus petit, sinon il serait barré. On laisse donc 3, et on barre tous les multiples de 3 :

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Le nombre 5 est le suivant, et est également premier, on barre donc les multiples de 5 :

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Comment montrer qu’un nombre est premier sans le crible d’Ératosthène ? Si un nombre n n’est pas premier, alors un de ses facteurs est plus petit que √n.
Par exemple, pour tester si un nombre inférieur à 100 est premier, il suffit de tester sur ce nombre les diviseurs inférieurs à √100, c’est à dire 10. Il suffit donc de tester la divisibilité par 2,3,5,7.
89 par exemple est forcément premier, car il n’est divisible ni par 2, ni par 3, ni par 5, ni par 7.

 

Lemme d’Euclide :

On définit p, un nombre premier. Si p|ab, alors p divise a, ou p divise b. C’est tout à fait logique.

Ce n’est pas fini, on dit, si p ne divise pas a, que p et a sont premiers entre eux, et donc, par le lemme de Gauss, p|b.

Si p est une nombre premier, alors √p ∉ Q. Exemple, √7 = 2,6457513110645905905016157536393…………….. Ceci n’est pas un rationnel.

On peut prouver ceci par l’absurde encore une fois :

Écrivons √p = a/b. avec a ∈ Z et b ∈ N* et pgcd (a,b) = 1.

Prouvons ceci par l’absurde :

On écrit √p = a/b. Avec a ∈ Z et b ∈ N et pgcd(a,b) = 1.
Posons pb² = a² (On multiplie par b des deux côtés et on se débarrasse de la racine en élevant les deux côtés de l’égalité au carré).
Donc, si b|a, et p|a², par conséquent et par le lemme d’Euclide, p|a² également.
De manière analogue, on écrit a = pa’, avec a’ un entier. Etant donné que b|a, b²|pa’².
Et ainsi, p|b² et donc p|b. Mais à présent, on a p|a et p|b, donc a et b ne sont pas premiers entres eux, ce qui démontre une contradiction…
Conclusion : √p n’est pas un nombre rationnel.

 

Théorème de décomposition en produit de facteurs premiers :

Soit n ≥ 2, un entier. Il existe des nombres entiers p1 < p2 < … < pr, et des exposants entiers α1, α2, α3,…,αr tels que :

n = p1α1 × p2α2 × … × prαr.

De plus, les pi et αi sont uniques (i = 1, 2, 3,…, r).

Donnons un exemple :
24 = 2² × 3.
36 = 2² × 9. Est ce correct ? Non, 9 n’est pas un nombre premier, donc il faut écrire 36 = 2² × 3².

Question qu’on pourrait se poser, pourquoi 1 n’est pas un nombre premier? Pourtant, il n’est divisible que par lui même !
Une des principale raison est qu’il n’y aurait plus unicité de la décomposition, mais une infinité de possibilités, par exemple on pourrait écrire :
36 = 1 × 2² × 3², mais aussi 36 = 1² × 2² × 3², ou encore 36 = 1³ × 2² × 3² etc…

D’autres exemple :

504. On commence par diviser le nombre par 2 jusqu’à ce que cela ne soit plus possible. Ensuite, on teste la division par 3, par 5, et par 7.
504 = 2³ × 3² × 7.
300 = 2² × 3 × 5².

On peut en déduire le pgcd et le ppcm de ces deux nombres.
On commence par réécrire les nombres ci dessus avec tous les nombres premiers (quitte à mettre des exposants 0) :

504 = 2³ × 3² × 5 ^0× 7^1 et 300 = 2² × 3^1 × 5² × 7^0.

• Le pgcd s’obtient en prenant le plus petit exposant de chaque facteur premier :
  pgcd(504,300) = 2² × 3^1 × 5^0 × 7^0 = 12.
• Le ppcm s’obtient en prenant le plus grand exposant de chaque facteur premier :
  ppcm(504,300) = 2³ × 3² × 5² × 7^1 = 12600.

 

Congruences et petit théorème de Fermat :

Définition :

Tout d’abord, et avant de voir plus en détails les propriétés des congruences, définissons de quoi il s’agit.

La congruence sur les entiers est une relation qui permet d’unir deux entiers.
On dit que ces dits deux entiers sont congrus modulo n, si leur différence est divisible par n.

• Autrement dit, fixons un n ≥ 2. a est congru à b modulo n si n divise b -a .
  Une autre formulation serait de dire ∃ k ∈ Z, tq a = b +kn.

Exemple :

15 ≡ 1 (mod 7), puisque 15 – 1 = 14, et 14 est un multiple de 7 (ou 7 est un diviseur de 14).
72 ≡ 2 (mod 7), puisque 72 – 2 = 70, et 70 est un multiple de 7.
3 ≡ -11 (mod 7), puisque 3 – -11 = 14.

Autre propriété :

• a ≡ 0 (mod n) si et seulement si n|a.
• Si la division euclidienne de a par n est a = bn + r (avec 0 ≤ r ≤ n), cela revient alors au même que a ≡ r (mod n).
• La relation « congru modulo n », est une relation d’équivalent qui vérifie :
  a ≡ a (mod n). Réflexivité.
  Si a ≡ b (mod n), alors b ≡ a (mod n). Symétrie.
  Si a ≡ b (mod n) et b ≡ c (mod n), alors a ≡ c (mod n). Transitivité.

 

• Soient a, b, c et d ∈ Z tels que a ≡ b (mod n) et c ≡ d (mod n), alors :

1. a + c ≡ b + d (mod n).
2. a × c ≡ b × c (mod n)
   Montrons que ceci est vrai :
   a ≡ b (mod n), donc il existe k  ∈ Z tel que a = b + kn. De même manière,
   c ≡ d (mod n), donc il existe l ∈ Z tel que c = d + ln.
   Alors a × c = (b + kn) × (d + ln) = bd + n(bl + dk + kln) = bd + mn, ceci est exactement dire que ac ≡ bd (mod n).
3. .a^k ≡ b^k (mod n), pour tout k ≥ 0.
   Cela nous permet d’affirmer par exemple que 5x + 8 = 3 (mod 5) pour tout x ∈ Z.
   En effet, 8 est congru à 3 modulo 5, et 5 est congru à 0 modulo 5, 8 + 5 = 13, et 13 ≡ 3 (mod 5). donc 5 × x vaut aussi 0 modulo 5.
   Autre exemple, 11 ≡ 1 (mod 10), donc, par la propriété du point 3, qui dit que (a^k ≡ b^k (mod n), pour tout k ≥ 0), 11, à n’importe quelle puissance est congru à 1, avec cette même puissance de telle sorte que 11^2345 ≡ 1^2345 ≡ 1 (mod 10).

Parlons de du critère de divisibilité par 9. Vous savez surement qu’un nombre est divisible par 9 si et seulement si, la somme de ses chiffres est divisible par 9.

La divisibilité par 9 (9|N) équivaut à ce que N ≡ 0 (mod 9).
Calculons les puissances de 10 :
10 ≡ 1 (mod 9), 10² ≡ 1 (mod 9), 10³ ≡ 1 (mod 9). En effet, 100 – 1 = 99, et 1000 – 1 = 999, qui sont tous deux des des multiples de 9. Autrement dit, 10^n ≡ 1 (mod 9).

Revenons à notre entier N, et réécrivons le en base 10.
N = ak…a3a2a1a0. a0 est le chiffre des unités, a1, le chiffre des dizaines, a2 le chiffre des centaines etc…
Cela se traduit par N = 10^k ak + …. + 10^3 a3 + 10^2 a2 + 10^1 a1 + a0.
Si on passe au calcul modulo 9 :
N ≡ ak + … + a3 + a2 + a1 + a0 (mod 9). Chacun des 10^n est congru a 1 (mod 9).
A présent, on a bien N ≡ 0 (mod 9) si et seulement si, la somme des chiffres vaut 9 (mod 9).

Illustrons ceci, car il est peut être compliqué de comprendre au premier abord :

Prenons N = 488 889, et montrons est divisible par 9.
On décompose N avec des puissances de 10 ⇒ N = 4.10^5 + 8.10^4 + 8.10³ + 8.10² + 8.10 + 9.
On réduit modulo 9, ce qui veut dire qu’on élimine les puissances de 10.
Donc N ≡ 4 + 8 + 8 + 8 + 8 + 9 (mod 9)
Donc N ≡ 45.
Mais 45 est congru à 9 (mod 9), donc 488 889 ≡ 0 (mod 9).

Tout ceci semble peut être un petit peu bizarre, mais il suffit de voir que le nombre N est un multiple de 9, ensuite, et étant donné que 488 889 – 9 = 488880 est toujours un multiple de 9, alors, tout simplement, le reste est nul, et donc 488889 est congru à 0 (mod 9).

Un autre exemple, on va essayer de calculer 2^21 (mod 37). Il existe plusieurs méthodes :

• La première, consiste à calculer 2^21, puis d’effectuer la division euclidienne de 21 par 37. Le reste est le résultat.
  C’est assez laborieux. 2^21 = 2 097 152. 2 097 152/37 = 56679 + 29. Donc, 29 ≡ 2^21 (mod 37).
• Deuxième méthode : On calcule successivement les 2^k modulo 37 :
  2^1 ≡ 2 (mod 37), 2² ≡ 4 (mod 37), 2³ ≡ 8 (mod 37), 2^4 ≡ 16 (mod 37), 2^5 ≡ 32 (mod 37) et 2^6 ≡ 64 (mod 37).
  Ensuite, on utilise les congruences, 64 ≡ 27 (mod 37), puis, pour 2^7 ≡ 2 × 2^6 ≡ 2 × 27 = 54 ≡ 17 (mod 37).
  On continue ainsi de suite, par exemple, 2^8 ≡ 34 (mod 37) (car 2^8 = 2 × 2^7, et on a dit que 2^7 = 54 ≡ 17 (mod 37)). Mais si 2^8 ≡ 34 (mod 37), on peut aussi dire que 2^8 ≡ 34 ≡ -3 (mod 37), car 34 — 3 = 37.
  Pour 2^9 ≡ 2 × 2^8 ≡ 2 × (-3)  ≡ -6 ≡ 31 (mod 37), car 31 –6 = 37.
• Il existe une troisième méthode encore plus efficace. On écrit l’exposant 21 en base 2 : 21 = 2^4 + 2² + 2^0 = 16 + 4 + 1.
  Donc, selon les propriétés des puissances, on peut écrire 2^21 = 2^16 × 2^4 × 2^1, grâce à cette technique, il est facile de calculer chaque terme, car les exposants sont des puissances de 2.
  En effet, 2^8 ≡ (2^4)² ≡ 16^2 ≡ 256 ≡ 34 ≡ -3 (mod 37).
  Ensuite, on pose 2^16 ≡ (2^8)² ≡ (-3)² ≡ 9 (mod 37).
  Ainsi, 2^21 ≡ 2^16 × 2^4 × 2^1 ≡ 9 × 16 × 2 ≡ 288 ≡ 29 (mod 37).

Conclusion, 2^21 ≡ 29 (mod 37).

 

Équations de congruence de type ax ≡ b (mod n) :

On va voir ici comment résoudre ce type d’équation, avec x, un entier.

Par exemple :

9x ≡ 6 (mod 24).

• Donc, il existe un x ∈ Z, tel que 9x ≡ 6 (mod 24), si et seulement si il existe un x et un k dans Z, tels que 9x = 6 + 24k.
• Première étape, voir si l’équation 9x – 24k = 6  a bien des solutions, et oui, elle en a, car pgcd(24,9) = 3, et 3 divise 6. Il s’agit bien d’une équation diophantienne.
• Maintenant, si on divise les deux côté de l’égalité par le pgcd, on a 3x – 8k = 2.
• On a donc une solution particulière ici, car (x0 = 6, k0 = 2) (faisable de tête dans ce cas de figure, autrement, il faut utiliser l’algorithme d’Euclide ou le théorème de Bézout en isolant x, en trouvant un y entier qui satisfasse l’équation etc…).
• Une fois que l’on a une solution particulière, on sait trouver toutes les solutions, x = 6 + 8l, avec l ∈ Z.
• On regroupe les solutions sous forme modulo 24, comme l’énoncé le souhaite, et on a x1 = 6 + 24m, x2 = 14 + 24m, x3 = 22 + 24m etc…  avec m ∈ Z, car si on remplace, on a :
  x1 = 8 ≡ 6 (mod 24), x2 = 16 ≡ 14 (mod 24), x3 = 24 ≡ 22 (mod 24) etc…

 

Petit théorème de Fermat :

Le petit théorème de Fermat dit que si p est un nombre premier, et a ∈ Z, alors a^p ≡ a (mod p).
La corollaire dit également que si p ne divise pas a, alors a^p-1 ≡ 1 (mod p).

• Prenons un exemple, et calculons 14^3141 (mod 17).
• On sait par le petit théorème de Fermat, que 14^16 ≡ 1 (mod 17), car 17 est un nombre premier.
• Écrivons maintenant la division Euclidienne de 3141 par 16 : 3141 = 16 × 195 + 5.
• Donc, cela veut dire que 14^3141 = 14^(16×195+5) ou 14^16×195 + 14^5.
• Que voit on ici ? On sait que 14^16 ≡ 1 (mod 17), donc on peut simplifier par (14^16)^196 et 1^196. On trouve donc simplement :
• 14^5 (mod 17).
• A présent, il faut calculer 14^5 (mod 17), mais ceci n’est pas très compliqué, si vous avez suivi les points précédents :
• On sait que 14 ≡ -3 (mod 17), 14² ≡ (-3)² mod 17, et 14³ ≡ 14² × 14 ≡ 9 × (-3) ≡ -27 ≡ 7 (mod 17) (car -27 – 7 = -34).
• Donc à présent, faisons 14^5. 14^5 ≡ 14² × 14³ ≡ 9 × 7 ≡ 63 ≡ 12 (mod 17).

Conclusion, 14^3141 ≡ 14^5 ≡ 12 (mod 17).

 

 

Euclide (300 avant J-C), était un mathématicien de la Grèce antique, connu pour ses découvertes et théorèmes en géométrie et en arithmétique.