[PDF] Arithmétique - Licence de mathématiques Lyon 1 PDF fetch.php?media=p13:algii:1-arith.pdf

Calculer pgcd(a, b) par l'algorithme d'Euclide 2 En déduire une identité de Bézout 27 Page 28 Maths en L

L'objectif est dans cette partie de créer une feuille de calcul donnant le PGCD de deux nombres Le tableau présentera les divisions successives effectuées

[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

On appelle PGCD de a et b le plus grand commun diviseur de a et b et note PGCD(a http://www maths-et-tiques fr/telech/Euclide ods (feuille de calcul OOo )

[PDF] Algorithme dEuclide - Département de Mathématiques dOrsay

(c) En utilisant la normalisation de (a), traiter l'algorithme d'Euclide qui permet de calculer le pgcd entre deux entiers relatifs quelconques a, b ∈ Z 6 Algorithme

[PDF] Applications de lalgorithme dEuclide sur les entiers et les polynômes

Préparation `a l'Agrégation de Mathématiques Université de Décrire l' algorithme d'Euclide permettant de calculer un p g c d de deux éléments d'un anneau

[PDF] ALGORITHME E POUR LA RECHERCHE PGCD DANS S - CORE

unfortunate (and mainly sociological) gap between mathematics and theoretical L'algorithme d'Euclide-pour le calcul du P G C D de deux entiers-est si ancien

[PDF] Arithmétique - Licence de mathématiques Lyon 1

Calculer pgcd(a, b) par l'algorithme d'Euclide 2 En déduire une identité de Bézout 27 Page 28 Maths en L

[PDF] PGCD et PPCM Nombres premiers entre eux

La méthode précédente, connue sous le nom d'algorithme d'Euclide, permet le calcul effectif du pgcd de deux entiers naturels Sa programmation est facile

[PDF] Exercices de mathématiques - Exo7

16 103 03 Pgcd, ppcm, algorithme d'Euclide Exercice 335 Calculer le pgcd des nombres suivants : 1 126, 230 2 390, 720, 450 3 180, 606, 750 Correction

[PDF] Exo7 - Cours de mathématiques - Formations en Informatique de Lille

Les calculs de cryptage se feront modulo n • Le décodage fonctionne grâce à une variante du petit théorème de Fermat 1 Division euclidienne et pgcd 1 1

Université Joseph Fourier, Grenoble I

Mathématiques, Informatique et Mathématiques Appliquées Licence Sciences et Technologies1eannéeArithmétique

Didier Piau et Bernard Ycart

Guère d"introduction tonitruante à faire, sinon pour souligner que ce chapitre a le charme de n"utiliser comme notions admises que les notations de la théorie des ensembles naïve et les connaissances évidentes sur les entiers, et qu"il présente donc l"agrément de donner une image de démonstrations (que l"on espère) totalement cré- dibles.

Table des matières

1 Cours 2

1.1 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 PGCD et PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Lemme de Gauss et décomposition en facteurs premiers . . . . . . . . . 8

1.5 Sous-groupes deZ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.7Z/nZ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Entraînement 22

2.1 Vrai ou Faux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4 Devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.5 Corrigé du devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 Compléments 38

3.1 Le code RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2 La course aux nombres premiers . . . . . . . . . . . . . . . . . . . . . . 38

3.3 La répartition des nombres premiers . . . . . . . . . . . . . . . . . . . . 38

Maths en L

1gneArithmétiqueUJF Grenoble1 Cours

1.1 Nombres premiers

On appelle entier (ou entier relatif, c"est-à-dire positif ou négatif) tout élément de

Z=?...,-3,-2,-1,0,1,2,3,...?

Définition 1.On dit qu"un entieraest unmultipled"un entierb, ou quebest un diviseurdealorsqu"il existe un entierktel quea=kb. Définition 2.On dit qu"un entierp≥2est premier lorsqu"il possède pour seuls diviseurs positifs1et lui-même. On notera au passage qu"au hasard des définitions, on parlera parfois d"entiers relatifs (les éléments deZ) et parfois d"entiers naturels (les éléments deN). Ce n"est qu"exceptionnellement très significatif; la principale fonction est d"être cohérent avec le reste du monde. Ainsi, comme partout ailleurs, dans ce cours, le nombre3est un nombre premier alors que-3n"en est pas un. En revanche, les nombres négatifs étant autorisés dans la définition de " diviseurs », l"entier3possède en tout et pour tout quatre diviseurs (à savoir-3,-1,1et3). Et tout de suite un joli théorème, qui remonte auxÉlémentsd"Euclide, écrits au IIIème siècle avant notre ère (c"est la proposition 20 du livre IX). Théorème 1.Il existe une infinité de nombres premiers. Vous connaissez probablement déjà une démonstration, il en existe plusieurs qui sont toutes bonnes à connaître, en voici une qui est très proche de celle du traité d"Euclide lui-même. Démonstration: SoitAl"ensemble des nombres premiers.Aest une partie deN, et est non vide car2est premier. On va supposerAfinie et aboutir à une absurdité. Supposons doncAfinie. Dès lors queAest une partie finie deN, évidemment non vide car2est premier,Apossède un plus grand élément. NotonsPce plus grand élément, le mystérieux " plus grand nombre premier ». Considérons alors l"entierN=P!+1(la factorielle deP, plus1). Pour tout entier Tout diviseur deN, et en particulier tout diviseur premier deN, est donc strictement supérieur àP. Or tout entier, et par exempleN, possède au moins un diviseur premier (pourquoi? exercice...). Mais alors, chacun de ces diviseurs premiers contredit la maximalité de

P. Absurdité!?

Maths en L

1gneArithmétiqueUJF Grenoble1.2 Division euclidienne

Il s"agit de formaliser avec précision la bonne vieille division euclidienne, celle que vous connaissez depuis l"école primaire. Théorème 2.Soitaun entier (relatif) etb≥1un entier strictement positif. Alors il existe un couple(q,r)unique (d"entiers) vérifiant la double condition : Démonstration: On va prouver successivement l"existence et l"unicité de(q,r). Existence de(q,r): la démonstration se prête bien à discuter selon le signe dea. Le cas oùa≥0est le cas contenant l"essentiel de la démonstration; lorsquea <0, on ne peut utiliser mot à mot la même preuve, mais on se ramène alors sans mal au cas intéressant déjà traité. •Premier cas (le cas significatif) : sia≥0. L"idée de la démonstration est de dire que le quotient deaparbest le plus grand entierqtel quebqsoit encore plus petit quea. d"entiers naturels; il est non vide, car il contient0. Il est fini : en effet soitdun entier tel qued≥a+ 1; on a alorsbd≥b(a+ 1)≥a+ 1> a, doncd??Aet ainsiAne contient que des entiers inférieurs ou égaux àa. L"ensembleApossède donc un plus grand élémentq. Posonsr=a-bq. La première condition sur(q,r)est alors évidemment vérifiée, c"est la seconde qui nécessite une vérification. Commeqest maximal parmi les éléments deA,q+1??A. Doncb(q+1)> a, donc r=a-bq < b.

L"existence est démontrée dans ce cas.

•Second cas (preuve sans imagination) : sia <0. On peut donc, en appliquant le premier cas, faire la division euclidienne dea?par En réinjectant la définition dea?, on écrit alorsa-ba=bq?+r, donca=b(q?+a)+r. Si on poseq=q?+a, on constate qu"on a réussi la division euclidienne deaparb. Unicité de(q,r): soit(q1,r1)et(q2,r2)des couples vérifiant les deux conditions exigées dans l"énoncé du théorème. On déduit dea=bq1+r1=bq2+r2queb(q1-q2) =r1-r2. Ainsi,r1-r2est un multiple deb. 3

Maths en L

Ainsir1-r2est un multiple debcompris strictement entre-betb. La seule possibilité est quer1-r2soit nul. On en déduitr1=r2, puis, en allant reprendre l"égalitéb(q1-q2) =r1-r2, queq1=q2.?

1.3 PGCD et PPCM

Les deux théorèmes qui se suivent sont agréablement parallèles; il est donc amusant de constater que leurs preuves sont plus différentes qu"on ne pourrait s"y attendre. Il est possible de les déduire l"un de l"autre, mais il est instructif de les prouver très séparément. Vous verrez donc plusieurs preuves de l"un comme de l"autre. Théorème 3.Soita≥1etb≥1deux entiers. Alors il existe un unique entierm≥1 tel que pour tout entierc≥1, cest un multiple deaet debsi et seulement sicest un multiple dem. Théorème 4.Soita≥1etb≥1deux entiers. Alors il existe un unique entierd≥1 tel que pour tout entierc≥1, cdiviseaetbsi et seulement sicdivised. Ces théorèmes sont vendus avec deux compléments, le premier occasionnellement utile, le second totalement fondamental.

Complément 1Pour tousaetb,md=ab.

Complément 2 (Identité de Bézout)

Pour tousaetb, il existe deux entiers (relatifs)setttels qued=sa+tb. Et tant qu"on y est avant de passer aux démonstrations : Définition 3.Leplus petit multiple communde deux entiersaetbest l"entierm apparaissant dans l"énoncé du théorème 3. Notation 1.Le plus petit multiple commun deaetbsera notéppcm(a,b). Définition 4.Leplus grand commun diviseurde deux entiersaetbest l"entierd apparaissant dans l"énoncé du théorème 4. Notation 2.Le plus grand commun diviseur deaetbsera notépgcd(a,b).

Première démonstration du théorème 3

Cette démonstration est la plus élémentaire; elle consiste à choisir pourmle mul- 4

Maths en L

1gneArithmétiqueUJF Grenoblevérifier qu"il marche. La preuve est en deux parties : d"abord l"existence dem(partie

significative) puis son unicité (partie très facile).

Existence dem

Introduisons l"ensembleAformé des entiers strictement positifs simultanément mul- tiples deaet deb. L"ensembleAn"est pas vide, puisqu"il contient l"entierab. Il admet donc un plus petit élémentm. On va vérifier que cet entiermconvient. Pour faire cette vérification, soit un entiern≥1; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens. •Preuve de l"implication directe : Supposons donc quenest un multiple commun deaetb, et montrons quenest un multiple dem. Pour ce faire, effectuons la division multiples dea,r=n-mqaussi; de même avecb. Ainsirest un multiple commun deaetb. Sirétait un entier strictement positif, vu l"inégalitér < mil contredirait la minimalité dem. C"est donc quer= 0et donc quenest un multiple dem. •Preuve de l"implication réciproque : Supposons ici quenest un multiple dem. Commemest lui-même multiple dea,nest à son tour multiple dea; de même avec b. C"est réglé.

Unicité dem

Soitmetm?vérifiant les hypothèses du théorème. Commemest un multiple dem (eh oui!), c"est un multiple commun deaetb, donc un multiple dem?. De même,m? est un multiple dem. Cela implique quemetm?sont forcément égaux au signe près. Comme ils sont tous deux strictement positifs, ils sont égaux. Fin de la démonstration. Voici maintenant une première démonstration de l"existence (et l"unicité) du pgcd, qui l"obtient à partir du ppcm. Cette démonstration a le confort d"être dépourvue d"idée subtile et l"avantage de prouver le Complément 1. Elle a l"inconvénient de ne pas prouver le Complément 2 et de ne pas fournir une méthode rapide de calcul du pgcd.

Première démonstration du théorème 4

Existence ded

On notemle ppcm deaetbet on posed=ab/m. Remarquons que ce nombred est bien un entier : en effet,abétant un multiple commun évident deaetb, c"est un multiple de leur ppcm. Reste à prouver qu"il convient. Pour faire cette vérification, soitn≥1un entier; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens. •Preuve de l"implication directe : supposons quenest un diviseur commun dea etb. On peut donc introduire deux entiersket?tels quea=knetb=?n. Pour travailler sur ce sur quoi nous avons des informations, à savoir les multiples deaetb, introduisons le nombren?=ab/n. Ce nombren?vaut aussi(a/n)b=kbet(b/n)a=?a. C"est donc un entier, et même un multiple commun deaetb. C"est donc un multiple 5

Maths en L

1gneArithmétiqueUJF Grenobledem. Il existe donc un entierctel quen?=cm, soitab/n=cab/d, doncd=cn. On

a bien prouvé quendivised. •Preuve de l"implication réciproque : puisquea=d(m/b)oùm/best un entier,d divisea; symétriquement puisqueb=d(m/a),ddiviseb. Supposons maintenant que ndivised. On voit alors aussitôt quendiviseaetb.

Unicité ded

C"est exactement le même principe que pour le ppcm, on laisse donc cette partie de la démonstration en exercice (très) facile. Preuve du Complément 1 : Il tombe immédiatement au vu de la formule qui donne dà partir dem. Fin de la démonstration. Comme promis, voici maintenant une deuxième démonstration du théorème 4, très différente dans son esprit, et qui permet pour guère plus cher de montrer simultanément le Complément 2.

Deuxième démonstration du théorème 4

La démonstration est une récurrence surb; techniquement, on gagne sérieusement

en confort si on autorisebà être nul, ce que l"on n"a pas fait, volontairement, en énonçant

le théorème dans l"espoir qu"il soit plus clair. On montrera donc légèrement mieux que

l"énoncé de la page précédente, puisqu"on prouvera le résultat sous l"hypothèse "a≥1

etb≥0». Avant de se lancer dans la récurrence proprement dite, on va donner un " résumé de la preuve » sous forme de programme informatique récursif.

Début du programme

*pgcd(a,0) =a. * Soitrle reste de la division euclidienne deaparb. Les diviseurs communs deaetbsont les diviseurs communs debetr.

D"où :pgcd(a,b) = pgcd(b,r).

Fin du programme

Ce résumé de démonstration convaincra peut-être les esprits les plus agiles, mais à notre niveau d"entraînement, il est plus prudent de faire ce qui est derrière les formu- lations récursives : une bonne vieille récurrence. On va démontrer par " récurrence forte » surb≥0l"hypothèse(Hb)suivante : (Hb)Pour tout entiera≥1, il existe deux entiers (relatifs)setttels que, pour toutn≥1,ndiviseaetbsi et seulement sindivisesa+tb.

Vérifions(H0).

Soitaun entier aveca≥1; tout entiern≥1qui diviseadivise aussib= 0puisque

0n= 0. Pour toutn≥1, on a donc :ndiviseaet0si et seulement sindivisea.

Prenons alorss= 1ett= 0. On a donc bien pour toutn≥1:ndiviseaet0si et seulement sindivisesa+t×0. 6

Maths en L

1gneArithmétiqueUJF GrenobleSoitbun entier fixé, avecb≥1. Supposons la propriété(Hc)vraie pour toutcavec

Soitaun entier aveca≥1. Notonsa=bq+rla division euclidienne deaparb (qu"on peut réaliser puisqueb≥1). Vérifions l"affirmation intermédiaire suivante : pour toutn≥1,nest un diviseur commun deaetbsi et seulement sinest un diviseur commun debetr. C"est-à-dire, avec des mots peut-être plus lisibles : " les diviseurs communs deaetbsont les mêmes que ceux debetr. » Soitnun diviseur commun deaetb, alorsndivise aussir=a-bq; réciproquement soitnun diviseur commun debetr, alorsndivise aussia=bq+r. L"affirmation intermédiaire est donc démontrée. r < b) sur l"entierb≥1. On en déduit qu"il existe deux entiers relatifss?ett?tels que pour toutn≥1,n divisebetrsi et seulement sindivises?b+t?r. Remarquons enfin ques?b+t?r=s?b+t?(a-bq) =t?a+(s?-q)b, et qu"ainsi, si on poses=t?ett=s?-q, on a bien prouvé que, pour toutn≥1,ndiviseaetbsi et seulement sindivisesa+tb. (Hb)est donc démontrée. On a donc bien prouvé(Hb)pour toutb≥0, donc a fortiori pour toutb≥1, ce qui prouve le théorème 4 et son Complément 2. En fait, il reste à prouver l"unicité ded, pour laquelle on renvoie à la démonstration précédente (où on écrivait qu"on la laissait en exercice).

Fin de la démonstration.

À présent, donnons un petit exemple sur des vrais nombres concrets, pour nous soulager l"esprit après tant de lettres.

Calcul du pgcd de137et24

On fait des divisions euclidiennes successives et on écrit dans la colonne de droite les conséquences de ces divisions. (1) 137 = 5×24 + 17pgcd(137,24) = pgcd(24,17) (2) 24 = 1×17 + 7pgcd(24,17) = pgcd(17,7) (3) 17 = 2×7 + 3pgcd(17,7) = pgcd(7,3) (4) 7 = 2×3 + 1pgcd(7,3) = pgcd(3,1) (5) 3 = 3×1 + 0pgcd(3,1) = pgcd(1,0) = 1

Doncpgcd(137,24) = 1.

Ces calculs permettent ensuite sans mal de reconstituer une identité de Bézout. - La dernière division avec un reste non nul est (4) qui donne1 = 7-2×3. 7

Maths en L

1gneArithmétiqueUJF Grenoble- On va repêcher une expression de3comme un reste dans la relation précédente,

soit (3), ce qui donne3 = 17-2×7. - On reporte cette expression de3donc1 = 7-2×(17-2×7). - On regroupe les termes en17et7donc1 =-2×17 + 5×7. - On va repêcher une expression de7comme un reste dans la relation précédente, soit (2), ce qui donne7 = 24-1×17. - On reporte cette expression de7donc1 =-2×17 + 5×(24-1×17). - On regroupe les termes en24et17donc1 = 5×24-7×17. - On va repêcher une expression de17comme un reste dans la relation précédente, soit (1), ce qui donne17 = 137-5×24. - On reporte cette expression de17donc1 = 5×24-7×(137-5×24). - On regroupe les termes en137et24donc

1 =-7×137 + 40×24.

- Et voilà!

Voici un autre exemple.

Calcul du pgcd de141et24

Voici les divisions euclidiennes successives et leurs conséquences en termes de pgcd. (1) 141 = 5×24 + 21pgcd(141,24) = pgcd(24,21) (2) 24 = 1×21 + 3pgcd(24,21) = pgcd(21,3) (3) 21 = 7×3 + 0pgcd(21,3) = pgcd(3,0) = 3 Doncpgcd(141,24) = 3et on vérifiera que ces calculs permettent de reconstituer l"identité de Bézout -141 + 6×24 = 3. Donnons une dernière définition avant de quitter les pgcd. Définition 5.On dit que deux entiersa≥1etb≥1sontpremiers entre euxlorsque leur seul diviseur commun positif est1. On veillera à ne pas confondre cette notion avec celle de nombre premier. (Par exemple, les calculs ci-dessus montrent que137et24sont premiers entre eux mais24 n"est pas premier.)

1.4 Lemme de Gauss et décomposition en facteurs premiers

Le lemme de Gauss permet de démontrer l"unicité de la décomposition en facteurs premiers. Ce dernier résultat semble plus facile d"usage pour un utilisateur peu expéri- menté, donc on énonce le lemme de Gauss sans commentaire, ou plus exactement sans autre commentaire que ce commentaire négatif. 8

Maths en L

1gneArithmétiqueUJF GrenobleLemme 1.Soita,betctrois entiers strictement positifs. Siadivise le produitbcet

siaest premier avecc, alorsadiviseb. Démonstration: Puisqueaest premier avecc, le pgcd deaetcest1, donc il existe des entiers relatifssetttels quesa+tc= 1. Multiplions cette identité parb: on obtient b=asb+tbc. Mais dans cette écriture,asbest évidemment multiple deatandis que tbcl"est parce quebcest multiple dea. On en déduit queb, somme des deux multiples deaque sontasbettbc, est lui-même un multiple dea.?

Théorème (énoncé approximatif)Tout entiern≥2peut être écrit de façon unique

comme produit de facteurs premiers. L"énoncé est approximatif car il n"est pas si clair de savoir ce que signifie "unique» : on peut écrire6 = 2×3 = 3×2mais il faut évidemment considérer que c"est la même chose. Pour pouvoir comprendre voire utiliser le théorème, cet énoncé suffira bien; mais pour le démontrer, il faut être plus précis. Théorème 5(énoncé précis).Tout entiern≥2peut être écrit comme produit de facteurs premiers. De plus, si on dispose de deux écrituresquotesdbs_dbs9.pdfusesText_15

[PDF] [PDF] Arithmétique - Licence de mathématiques Lyon 1

Université Joseph Fourier, Grenoble I

Didier Piau et Bernard Ycart

Table des matières

1 Cours 2

1.1 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 PGCD et PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Lemme de Gauss et décomposition en facteurs premiers . . . . . . . . . 8

1.5 Sous-groupes deZ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.7Z/nZ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Entraînement 22

2.1 Vrai ou Faux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4 Devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.5 Corrigé du devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 Compléments 38

3.1 Le code RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2 La course aux nombres premiers . . . . . . . . . . . . . . . . . . . . . . 38

3.3 La répartition des nombres premiers . . . . . . . . . . . . . . . . . . . . 38

Maths en L

1gneArithmétiqueUJF Grenoble1 Cours

1.1 Nombres premiers

Z=?...,-3,-2,-1,0,1,2,3,...?

P. Absurdité!?

Maths en L

1gneArithmétiqueUJF Grenoble1.2 Division euclidienne

L"existence est démontrée dans ce cas.

Maths en L

1.3 PGCD et PPCM

Complément 1Pour tousaetb,md=ab.

Complément 2 (Identité de Bézout)

Première démonstration du théorème 3

Maths en L

1gneArithmétiqueUJF Grenoblevérifier qu"il marche. La preuve est en deux parties : d"abord l"existence dem(partie

Existence dem

Unicité dem

Première démonstration du théorème 4

Existence ded

Maths en L

1gneArithmétiqueUJF Grenobledem. Il existe donc un entierctel quen?=cm, soitab/n=cab/d, doncd=cn. On

Unicité ded

Deuxième démonstration du théorème 4

Début du programme

D"où :pgcd(a,b) = pgcd(b,r).

Fin du programme

Vérifions(H0).

0n= 0. Pour toutn≥1, on a donc :ndiviseaet0si et seulement sindivisea.

Maths en L

1gneArithmétiqueUJF GrenobleSoitbun entier fixé, avecb≥1. Supposons la propriété(Hc)vraie pour toutcavec

Fin de la démonstration.

Calcul du pgcd de137et24

Doncpgcd(137,24) = 1.

Maths en L

1gneArithmétiqueUJF Grenoble- On va repêcher une expression de3comme un reste dans la relation précédente,

1 =-7×137 + 40×24.

Voici un autre exemple.

Calcul du pgcd de141et24

1.4 Lemme de Gauss et décomposition en facteurs premiers

Maths en L

1gneArithmétiqueUJF GrenobleLemme 1.Soita,betctrois entiers strictement positifs. Siadivise le produitbcet