ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Après avoir défini le concept de nombre (sous-entendu entier), Livre VII :

Proposition XI, livre VII
Si le tout est au tout comme le nombre retranché est au nombre retranché, le nombre restant sera aussi
au nombre restant comme le tout est au tout.
Traduire en langage moderne sachant que a est à b ce que c est à d signifie a/b = c/d  

Pour tout couple (a,b) d'entiers naturels, b étant non nul, on peut écrire :

a = b x q + r, q et r entiers et 0 ≤ r < b

On dit que q est le quotient de la division euclidienne de a par b, appellation due au groupe Bourbaki (Théorie des ensembles, Ch. 3, §5, n°6) dans son entreprise de rénovation des mathématiques. L'entier r est le reste. L'entier a est le dividende (celui que l'on divise), b est le diviseur.

La condition 0 ≤ r < b assure l'unicité du quotient et du reste. Lorsque r est nul, a = b x q, on dit que a est un multiple de b ou que b est un diviseur de a. Si a est nul, q = r = 0. 0 est multiple de tout entier.

• Dans la division euclidienne de 38 par 3, le quotient est 12 et le reste est 2 :  38 = 3 x 12 + 2.

• Si l'on écrit 38 = 3 x 11 + 5, cette égalité n'est pas fausse mais ce n'est pas celle de la division euclidienne. Vu que 5 = 3 + 2, on peut ajouter 1 au quotient en écrivant 38 = 3 x 11 + 3 + 2 = 3 x (11 + 1) + 2 = 3 x 12 + 2.

 Collégiens & lycéens : Certaines calculatrices actuelles, utilisées au collège et au lycée, pratiquent la division euclidienne au moyen d'une touche spéciale. Celles qui ne possèdent pas cette fonction possèdent toutes aujourd'hui la touche "A b/c" mettant une fraction N/D sous la forme a + b/c. Le piège, chez certains constructeurs, est que la fraction b/c est affichée simplifiée irréductible.

Exemple : Quel est le reste de la division euclidienne de 348 par 24 ? la machine répond par une écriture symbolique, quelque chose comme : 14 ¬ 1 ¬ 2 laissant à penser que le quotient est 14 et le reste 1...
En fait 348 = 14 x 24 + 12. La calculatrice a trouvé a + b/c = 14 + 1/2, soit 14 + 12/24 : il faut penser à réécrire b/c avec le diviseur comme dénominateur !

Proposition (division euclidienne généralisée à un dividende dans Z) :    

On peut permettre à l'entier a (le dividende) d'être négatif , le diviseur b restant strictement positif. La condition sur le reste est inchangée. On suppose ici le dividende a non multiple de b, aZ, bN*. Dans ces conditions, on peut énoncer :

q est le quotient de la division euclidienne de a par b si et seulement si
bq < a < b(q + 1), le reste étant r = a - bq > 0.

Preuve : Le cas a = 0 est trivial. Considérons la suite d'entiers b, 2b, 3b, ..., nb, ... et posons S = {b, 2b, 3b, ..., nb, ...}. S n'est pas borné supérieurement.

i/ Lorsque a > 0, le diviseur b étant strictement positif, il existe nN tel que a < nb. Soit p la plus petite valeur de n pour qu'il en soit ainsi. Cet entier p est au moins égal à 1. Posons q = p - 1. Par définition de p, on a alors a  ≥ qb et a < pb <(q + 1)b. Donc bq ≤ a < b(q + 1), et r = a - bq vérifie 0 ≤ r < b.

ii/ Lorsque a < 0, soit q et r tels que | a | = bq + r avec bq < | a | < b(q + 1), et r =  | a | - bq. Vu que a = -| a |, on obtient en remplaçant : b(-q - 1) < a < -bq. Posons q' = -q - 1. On a bq' < a < b(q' + 1) et a = bq' + b - r. Le quotient est q' et le reste est r' = b - r.

• Exemple : Quel est le quotient et le reste dans la division euclidienne de -17 par 3 ? On a 17 = 35 + 2; donc 17 = -35 - 2 = 3(-5) - 2 + 3 - 3 = 3(-6) + 1. Le quotient est - 6 (soit -q - 1), le reste est 1 (soit b - r).

Multiples & diviseurs, Critères de divisibilité, exercices :             Notion de congruence :

Les nombres premiers :

On doit à Euclide l'étude et la première preuve de l'infinitude de l'ensemble des nombres premiers : nombre n'ayant aucun diviseur propre, et de l'existence, pour tout entier naturel n au moins égal à 2, d'un diviseur premier p dont le carré est inférieur à n, ce qui permet la recherche de primarité. Un nombre non premier est dit composé : il admet au moins un diviseur autre que 1 et lui-même (donc plus de deux diviseurs).

Ératosthène :            Distribution des nombres premiers :

1 fut considéré comme premier jusqu'à la fin du 19è siècle. Un diviseur propre d'un nombre N est un diviseur non trivial, c'est à dire distinct de l'unité et de N. Il est alors souhaitable, lorsqu'on travaille sur des problèmes d'arithmétique, que 1 ne soit pas premier. C'est cette raison qui conduit à définir aujourd'hui un nombre premier comme ci-dessus (nombre n'ayant aucun diviseur propre) ou comme un entier ayant exactement deux diviseurs distincts. Ce qui élimine 1 qui ne possède qu'un seul diviseur : lui-même.

Théorème :  

Tout entier naturel n admet une unique factorisation de la forme n = p₁^α x p₂^β x ... x p_k^γ où les p₁, p₂,..., p_k sont les diviseurs premiers de n et α, β, γ, ... des entiers non nuls.

Ce théorème fondamental d'arithmétique fit l'objet des propositions XXXIII et XXXIV des Éléments d'Euclide. Il est parfois appelé théorème d'Al-Farasi en l'honneur du mathématicien perse (1260-1320) à qui l'on doit sa première démonstration en termes "modernes".

Preuve de ce théorème et programme JavaScript :               Étude & recherche de nombres premiers :

Dans un passé récent, on appelait partie aliquote d'un nombre (du latin aliquot = un certain nombre de), un diviseur de N autre que N lui-même. Le sens étymologique est clair : si d divise N, d distinct de N, alors d est contenu un nombre entier de fois dans N.

PGCD de deux ou plusieurs entiers (plus grand diviseur commun), nombres premiers entre eux  :

Par exemple : le PGCD de 24 et 18 est 6. En effet 24 = 2 x 2 x 2 x 3 et 18 = 2 x 3 x 3.
                       Le plus grand diviseur commun sera donc 2 x 3 = 6.

Cette notion s'étend à plusieurs nombres :

Par exemple : Quel est le PGCD de 126 et 140 et 350 ?  126 = 2 x 3 x 3 x 7 , 140 = 2 x 2 x 5 x 7 et 350 = 2 x 5 x 5 x 7.
                        Rép. = 2 x 7 = 14.

On voit, au-delà du collège (où la notion de PGCD est au programme), que l'on peut retenir :

Le PGCD de plusieurs nombres est égal au produit de tous les facteurs premiers communs
à ces nombres affectés de leur plus petit exposant

Rappelons ici que deux nombres dont le PGCD est égal à 1, sont dits premiers entre eux ou encore : étrangers. Par exemple 12 et 35 sont premiers entre eux et cependant aucun de ces nombres n'est premier puisque 12 = 3 x 4 et 35 = 5 x 7. On écrit donc pgcd(12,35) = 1. On dit aussi que 12 est premier avec 35.

Cette notion de nombres premiers entre eux s'étend à plusieurs nombres pour signifier que, pris deux à deux, le PGCD est égal à 1. Par exemple 12, 25 et 91 sont premiers entre eux puisque :

pgcd(12,25) = 1, pgcd(12,91) = 1 et pgcd(25,91) = 1

Il est autorisé d'écrire : pgcd(12,25,91) = 1.

Si à tout couple d'entiers, on associe son pgcd, on définit ainsi une opération dans N. Posons pgcd(a,b) = a ^ b. Cette loi de composition interne est associative :

(a ^ b) ^ c = a ^ (b ^ c)

On parle aussi de nombres premiers entre eux dans leur ensemble si a ^ b ^ c = 1 en écrivant :

a ^ b ^ c = (a ^ b) ^ c = a ^ (b ^ c)

Ainsi, 6, 9 et 10 sont premiers entre eux dans leur ensemble car 6 ^ 9 ^ 10 = (6 ^ 9) ^ 10 = 3 ^ 10 = 1 et cependant, ils ne sont pas premiers deux à deux car 6 ^ 9 = 3 et 6 ^ 10 = 2.

 le PGCD, Plus Grand Commun Diviseur de deux nombres, est au programme des collèges (classe de 3ème). Remarquons encore et toujours qu'il serait plus correct de dire "en french" : PGDC. Les américains et les anglais (anglo-saxons) disent GCD : Greatest Common Divisor... Idem pour le PPCM : de l'anglais LCM : Least Common Multiple. No comment...

La définition récursive du PGCD (procédure qui fait appel à elle-même) peut s'écrire :

pgcd(a,b) = pgcd(b,r)

où r désigne le reste de la division de a par b ( division euclidienne). C'est la définition choisie par Euclide pour établir son algorithme de recherche :

PGCD selon Euclide :

Cette notion de récursion est fondamentale dans les algorithmes mathématiques (et informatiques). Elle permet des programmes de calcul très concis. L'algorithme doit posséder un point d'arrêt : ici ce serait si b = 0 alors pgcd = a.

On peut également procéder par différences :

PGCD par différences :

PPMC de deux entiers (plus petit multiple commun) et cas de plusieurs nombres :

Dans les calculs fractionnaires et certains problèmes arithmétiques, il est aussi utile de connaître le plus petit multiple commun de deux entiers : c'est le PPMC ou PPCM.

Par exemple : le PPCM de 24 et 90 est 72. En effet 24 = 2 x 2 x 2 x 3 et 90 = 2 x 3 x 3 x 5. Le plus petit multiple commun sera donc 2 x 2 x 2 x 3 x 3 x 5  = 8 x 9 x 5 = 360.

Cette notion s'étend à plusieurs nombres et le PPMC devient vite assez grand... mais, en général plus petit que le produit des nombres entrant en jeu :

Par exemple : Quel est le PPCM de 126 , 140 et 550 ?  126 = 2 x 3 x 3 x 7 , 140 = 2 x 2 x 5 x 7 et 550 = 2 x 5 x 5 x 11.
                       Rép. = 2 x 2 x 3 x 3 x 5 x 5 x 7 x 11 = 69 300. Le produit est 9 702 000

On pourra retenir que :

Le PPCM de plusieurs nombres est égal au produit de tous les facteurs premiers communs ou non
à ces nombres affectés de leur plus grand exposant

On démontre facilement que pour deux entiers a et b quelconques :

a x b = pgcd(a,b) x ppmc(a,b)

4.     Introduction au PGCD par un exercice élémentaire

5.  On doit remplir de cubes une caisse dont les dimensions, en cm, sont 150, 165 et 105. Quelle sera la plus grande des mesures possibles de l'arête des cubes ? 

Rép : pgcd(150,165, 105) = 15 car 150 = 2 x 3 x 5 x 5 , 165 = 3 x 5 x 11 et 105 = 3 x 5 x 21.

6.  Quel est le plus petit multiple commun aux dix premiers nombres entiers (non nuls) ?

Rép : 2520.

7.  Quel est le plus grand nombre de 3 chiffres qui, divisé par 3, 7 et 11 donne toujours le même reste 2 ? 

Rép : si n est ce nombre, n - 2 est multiple de 3, 7 et 11. 3, 7 et 11 sont premiers entre eux. Donc n - 2 est multiple de 231. On a déduira n = 926.

8.  Quel est le plus grand nombre de 3 chiffres qui, divisé par 6, 9 et 12 donne toujours le même reste 5 ? 

Rép : si n est ce nombre, n - 5 est multiple de 6, 9 et 12. Mais ces nombres ne sont pas premiers entre eux. Leur ppmc est 36. Donc n - 5 est multiple de 36. Plus grande valeur de n possible : pour éviter de tâtonner, on divise 999 - 5 par 36 : le quotient entier est 27.
On en déduit n = 27 x 36 + 5 = 977.

9.  Dans une gare de la région parisienne, les quais A, B et C desservent 3 destinations. dès 5h30 du matin, il y a un départ sur A, B et C respectivement toutes les 15, 25 et 18 minutes. A quelle heure y aura-t-il, pour la première fois, un départ simultané de trois trains ?

Rép : Soit T le nombre de minutes écoulé jusqu'au 1er départ simultané : T est le plus petit multiple commun à 15 = 3 x 5, 18 = 2 x 3 x 3 et 25 = 5 x 5. Par conséquent T = 3 x 5 x 2 x 3 x 5 = 450. 450 minutes sont 7h 30 min. Le 1er départ simultané au lieu à 13 h.

10.    a)  Montrer que si deux entiers naturels x et y sont premiers entre eux, il en est de même de 2x + y et 5x + 2y.
         b)  En déduire les solutions du système ab = 3m, (2a + b)(5a + 2b) = 1620, m désignant le ppmc de a et b.

Rép : a) 2(2x + y) + x = 5x + 2y. Donc si d divise 2x + y et 5x + 2y, alors d divise x. Or, 3(2x + y) - x - y = 5x + 2y. Donc si d divise 2x + y et 5x + 2y, comme il divise x, il devra diviser y. Inversement si d divise x et y, il divise évidemment 2x + y et 5x + 2y. Les paires {x,y} et {2x + y,5x + 2y} ayant les mêmes diviseurs, elles ont le même pgcd. Par conséquent si pgcd(x,y) = 1, alors pgcd(2x + y,5x + 2y) = 1.

b) ab = pgcd(a,b)ppmc(a,b), donc pgcd(a,b) = 3. Posons a = 3a' et b = 3b'. On a (2a' + b')(5a' + 2b') = 1620/9 = 180 avec a' et b' d'une part et  2a' + b' et 5a' + 2b' d'autre part sont premiers entre eux Or, 180 = 2² x 3² x 5 et le plus petit facteur est 2a' + b'. Les facteurs devant être premiers entre eux, ce dernier est donc nécessairement choisi dans {2², 5, 3²}. On remarque que 5a' + 2b' - 2(2a' + b') = a'. On procède par essais et élimination des cas :

• 2a' + b' = 4 , 5a' + 2b' = 45 : a' = 37 incompatible avec 2a' + b' = 4.

• 2a' + b' = 5 , 5a' + 2b' = 36 : a' = 26 incompatible avec 2a' + b' = 4

• 2a' + b' = 9 , 5a' + 2b' = 20 : a' = 2 , b' = 9 - 4 = 5 : pgcd(a',b') = 1. La solution est  a = 6, b = 15.

11.  Rechercher les entiers a et b tels que pgcd(a,b) = a - b  (niveau TerS Spé Math / Sup).

12.  Recherche du PGCD de deux entiers : a = n³ - n² - 12n  et  b = 2n² - 7n - 4  (niveau TerS Spé Math / Sup).

---

© Serge Mehl - www.chronomath.com