Sujet : Algèbre, Arithmétique dans Z, PGCD et PPCM
2
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
2
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Licence :
Langue
Français
Publié par
Licence :
Langue
Français
[http://mp.cpgedupuydelome.fr] édité le 6 août 2013
PGCD et PPCM
Enoncés
Exercice 1[ 01195 ][correction]
Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers
aetbsuivants :
a)a= 33etb= 24b)a= 37etb= 27c)a= 270etb= 105.
Exercice 2[ 01196 ][correction]
Soienta b d∈Z. Montrer l’équivalence :
(∃u v∈Z au+bv=d)⇔pgcd(a b)|d
Exercice 3[ 01197 ][correction]
Montrer que le pgcd de2n+ 4et3n+ 3ne peut tre que123ou 6.
Exercice 4[ 01198 ][correction]
a) Montrer que sirest le reste de la division euclidienne dea∈Nparb∈N
2r−1est le reste de la division euclidienne de2a−1par2b−1.
b) Montrer que pgcd(2a−12b−1) = 2pgcd(ab)−1.
?alors
Exercice 5[ 01199 ][correction]
Soientd m∈N. Donner une condition nécessaire et suffisante pour que le système
(pgcd(x y) =d
ppcm(x y) =m
possède un couple(x y)∈N2solution.
Exercice 6[ 01200 ][correction]
Résoudre dansN2l’équation :
pgcd(x y) +ppcm(x y) =x+y
Exercice 7[ 01201 ][correction]
Résoudre dansN2les systèmes :
a)(pcmdcgpp((xyyx)=605=)
b)
(x+y 0= 100
pgcd(x y) = 1
1
Diffusion autorisée à titre entièrement gratuit uniquement - dD
2
avecu=ku0etv=kv0∈Z
Corrections
Exercice 7 :[énoncé]
a) Soit(x y)solution. pgcd(x y) = 5doncx= 5x0ety= 5y0avecx0 y0∈N
premiers entre eux.
ppcm(x y) = 5x0y0= 60doncx0y0= 12d’où
(x0 y0)∈ {(112)(26)(34)(43)(62)(121)}.
Les couples(26)et(62)et 6 ne sont pas premiers entre eux.sont à éliminer car 2
Finalement(x y)∈ {(560)(1520)(2015)(605)}.
Inversement : ok. FinalementS={(560)(1520)(2015)(605)}.
b) Soit(x y)solution. pgcd(x y) = 10doncx= 10x0ety= 10y0avecx0 y0∈N
premiers entre eux.
x+y= 10(x0+y0) = 100doncx0+y010
.
=
Sachantx0∧y0= 1, il reste(x0 y0)∈ {(19)(37)(73)(91)}puis
(x y)∈ {(1090)(3070)(7030)(9010)}.
Inversement : ok. FinalementS={(1090)(3070)(7030)(9010)}.
Ainsi(x y)est de la forme(δ δk)ou(δk δ)aveck∈N.
Inversement ces couples sont solutions.
1 +x0y0=x0+y0⇔(x0−1)(y0−1) = 0⇔x0= 1ouy0= 1
L’équation devient :
et on a alors
d=au+bv
pgcd(2a−12b−1) =pgcd(2a0−12a1−1) =pgcd(2a1−12a2−1) = =pgcd(2am−120−1) = 2am−1
Exercice 5 :[énoncé]
Si le système possède une solution alorsd|mest une condition nécessaire.
Inversement sid|malorsx=dety=mdonne un couple(x y)∈N2solution.
2a−1 = 2bq+r−1 = 2bq+r−2r+ 2r−1 = (2b−1)(1 + 2b+∙ ∙ ∙+ 2b(q−1))2r+ 2r−1
avec062r−1<2b−1.
b) Posonsa0=a,a1=bet définissonsa2 amcomme par l’algorithme
d’Euclide avecam=pgcd(am−1 am−2).
On a
Exercice 3 :[énoncé]
3×(2n+ 4)−2×(3n+ 3) = 6donc pgcd(2n+ 43n+ 3)|6.
Exercice 4 :[énoncé]
a) On aa=bq+ravec06r < b.
Diffusion autorisée à titre entièrement gratuit uniquement - dD
Exercice 6 :[énoncé]
Soit(x y)∈N2un couple solution. Posonsδ=pgcd(x y).
On peut écrire
x=δx0ety=δy0avecx0∧y0= 1
[http://mp.cpgedupuydelome.fr] édité le 6 août 2013
Z.
Exercice 1 :[énoncé]
a) pgcd(a b) = 3et3a−4b= 3.
b) pgcd(a b) = 1et11b−8a= 1
c) pgcd(a b) = 15et2a−5b= 15
Corrections
au0+bv0=pgcd(a b)
Exercice 2 :[énoncé]
(⇒)Supposonsd=au+bvavecu v∈Z.
pgcd(a b)|aet pgcd(a b)|bdonc pgcd(a b)|au+bv=d.
(⇐)Supposons pgcd(a b)|d. On peut écrired=kpgcd(a b)aveck∈
Par l’égalité de Bézout, il existeu0 v0∈Ztels que
