Ch Arithmetique

Pour tout a O : pgcd(a, O) a et pgcd(a, 1) 1 1. 3. Algorithme d’Euclide Lemme 1 Soient a, b c . Écrivons la division euclidienne a = bq + r. Alors pgcd(a, b) = pgcd(b, r) En fait on a même pgcd(a, b) = pgcd(b, a — qb) pour tout q Z. Mais pour optimiser l’algorithme d’Euclide on applique le lemme avec q le quotient. Démonstration Nous allons montrer que les diviseurs de a et de b sont exactement les mêmes que les diviseurs de b et r . Cela impliquera le résultat car les plus grands diviseurs seront bien sûr les mêmes. – Soit d un diviseur de a et de b. Alors d divise b donc aussi bq, en plus d divise a donc d divise q —a —r. Soit d un diviseur de b et de r . Alors d divise aussi bq + r = a. Algorithme d’Euclide. On souhaite calculer le pgcd de a, b E N’ . On peut supposer a b. On calcule des divisions euclidiennes successives. Le pgcd sera le dernier reste non nul. – division de a par b, a = bq 1 + r 1 . Par le lemme 1, pgcd(a, b) = pgcd(b, r 1 ) et sirl = O alors pgcd(a, b) b sinon on continue : -b=rl q 2+ r 2, pgcd(a, b) = pgcd(b, r 1 ) = pgcd(r 1 , r 2 r 1 r2q3+r3 , pgcd(a, b) pgcd(r 2, r 3), – r k—2 = rk—l q k 4 r k, pgcd(a, b) = pgcd(r k—l , r k), r k 1 = r k q k + 0. pgcd(a, b) = pgcd(r k, O) = r k

Comme à chaque étape le reste est plus petit que le quotient on sait que O r i+l < ri . Ainsi l'algorithme se termine car nous sommes sûr d'obtenir un reste nul, les restes formant une suite décroissante d'entiers positifs ou nuls : b > r 1 > r 2 > … o Exemple 4 Calculons le pgcd de a = 600 et b – 124. 600 124 104 20 Ainsi pgcd(600, 124) = 4. Voici un exemple plus compliqué : 39 Ainsi pgcd(9945, 3003) = 39. 1-4. Nombres premiers entre eux Définition 3 Deux entiers a, b sont premiers entre eux si pgcd(a, b) 1 Exemple 6 Pour tout a e Z, a et a+ 1 sont premiers entre eux.

En effet soit d un diviseur commun à a t à a + 1. Alors d divise aussi a + 1 — a. Donc d divise 1 mais alors d -—1 oud = +1. Le plus grand diviseur de a et a + 1 est donc 1. Et donc pgcd(a, a + 1) – 1 Si deux entiers ne sont pas premiers entre eux, on peut s’y ramener en divisant par leur pgcd Exemple 7 Pour deux entiers quelconques a, b E z, notons d = pgcd(a, b). La décomposition suivante est souvent utile : a=ad b = bd avec a, b e Zet pgcd(a , b) = 1 Mini-exercices 1. Écrire la division euclidienne de 111 111 par 20xx, où 20xx est l’année en cours. 2.

Montrer qu’un diviseur positif de 10 008 et de 10 014 appartient nécessairement ? 3. alculer pgcd(560, 133), pgcd(12 121, 789), pgcd(99 999, 1110). 4. Trouver tous les entiers 1 question avec 52. PAGF s OF l’algorithme d’Euclide. Les entiers u, v ne sont pas uniques. Les entiers u, v sont des coefficients de Bézout. Ils s’obtiennent en «remontant» l’algorithme d’Euclide. Exemple 8 Calculons les coefficients de Bézout pour a = 600 et b = 124. Nous reprenons les calculs effectués pour trouver pgcd(600, 124) = 4. La partie gauche est l’algorithme d’Euclide.

La partie droite s’obtient de bas en haut. On exprime le pgcd à l’aide de la dernière ligne où le reste est non nul. Puis on remplace le reste de la ligne récédente, et ainsi de sulte jusqu’? arriver à la première ligne. 4 OF exacts. Ici on vérifie à la fin que 600 x 6+ 124 (—29) 4. Exemple 9 Calculons les coefficients de Bézout correspondant à pgcd(9945, 3003) = 39. 9945 3003 936 195 156 pgcd(a, b) = 4. Corollaire 3. Lemme de Gauss Soient a, b, ce Z. Si al bc et pgcd(a, b) = 1 alors al c Exemple : si 417 x c, et comme 4 et 7 sont premiers entre eux, alors 41 c.

Comme pgcd(a, b) = 1 alors il existe u, v EZ tels que au + 1. On multiplie cette égalité par c pour obtenir acu bcv = c. Mais al acu et par hypothèse al bcv donc a divise acu + bcv = c. 2. 3. ?quations ax + by = c 7 Proposition Considérons Péquation où a, b, ce Z. 1 . L’équation (E) possède des solutions (x, y) E Z2 si et seulement si pgcd(a, b) I c. 2. Si pgcd(a, b) I c alors il existe même une infinité de solutions entières et elles sont exactement les (x, y) (xo + a k, yo + k) avec xo , yo a, fixés et k parcourant Z.

Le premier point est une conséquence du théorème de Bézout. Nous allons voir sur un exemple comment prouver le second point et calculer explicitement les solutions. Il est bon de refaire toutes les étapes de la démonstr fois. PAGF 8 OF 46 161 = 46 x 3+23 46 = 23 *240 Donc pgcd(368, 1 61) = 23. Comme 115 = 5 x 23 alors pgcd(368, 161)1115. par le théorème de Bézout, l’équation (E) admet des solutions entières. – Deuxième étape. Trouver une solution particulière : la remontée de l’algorithme d’Euclide.

On effectue la remontée de l’algorithme d’Euclide pour calculer les coefficients de Bézout. 368 – 161 x 2+46 23 – 161 + (368 -2 x 161) x 161 x 7 +368 x 161 -3*46 on trouve donc 161 x 7 + 368 x = 23. comme 115 multipliant par 5 on obtient • 161 = 5 x 23 en Ainsi (xD , yo ) (35, —1 S) est une solution particulière de – Troisième étape. Recherche de toutes les solutions. Soit (x, y) E Z2 une solution de (E). Nous savons que (xo ,yO) est aussi solution. Ainsi . 161x +368y= 115 115 (on n’a aucun intérêt à re PAGF q OF par leurs valeurs). La suite du raisonnement serait fausse. Ainsi 7116(y -yo or pgcd(7, 16) = 1 donc par le lemme de Gauss 71 y —yO. Il existe donc k E z tel que y —yo = 7 x k. Repartant de l’équatlon (+) : — xo ) = -16(y —yo On obtient maintenant — xo ) = —16 x 7 x k. D’où x — xo – —1 6k. (C’est le même k pour x et pour y. ) Nous avons donc (x, y) = (xo — 16k, yo + 7k). Il n’est pas dur de voir que tout couple de cette forme est solution de l’équation (E). Il reste donc juste ? substituer (xo yo ) par sa valeur et nous obtenons : Les solutions entières de 161x + 368y = 115 sont les (x. ) = (35 — 16k, —15 + 7k), k parcourant Z. pour se rassurer, prenez une valeur de k au hasard et vérifiez que vous obtenez bien une solution de l’équation. 2. 4. ppcm Définition 4 Le ppcm(a, b) (plus petit multiple commun) est le plus petit entier par b. O divisible par a et Par exemple ppcm(12, 9) = 36. Le pgcd et le ppcm sont liés par la formule suivante : Proposition 2 Si a, b sont des entiers (non tous les deux nuls) alors pgcd(a, b) x ppcm(a, b) ab posons d = pgcd(a, b) et m = abl