Sujet : Algèbre, Arithmétique dans Z, PGCD et PPCM

2 pages

Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Sujet : Algèbre, Arithmétique dans Z, PGCD et PPCM

algebre-mpsi

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

2 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

[http://mp.cpgedupuydelome.fr] édité le 6 août 2013 Enoncés 1 PGCD et PPCM Exercice 1 [ 01195 ] [correction] Déterminer le pgcd et les coeﬃcients de l’égalité de Bézout (1730-1783) des entiers a et b suivants : a) a = 33 et b = 24 b) a = 37 et b = 27 c) a = 270 et b = 105. Exercice 2 [ 01196 ] [correction] Soient a,b,d∈Z.

Sujets

Classe préparatoire aux grandes écoles

Mathématiques, physique et sciences de l'ingénieur

Public Readiness and Emergency Preparedness Act

exercices

Informations

Publié par	algebre-mpsi
Nombre de lectures	773
Licence :	En savoir + Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
Langue	Français

Extrait

[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 coeﬃcients 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 que123ou 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−12b−1) = 2pgcd(ab)−1.

?alors

Exercice 5[ 01199 ][correction]
Soientd m∈N. Donner une condition nécessaire et suﬃsante 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((xyyx)=605=)

(x+y 0= 100
pgcd(x y) = 1

Diﬀusion autorisée à titre entièrement gratuit uniquement - dD

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)∈ {(112)(26)(34)(43)(62)(121)}.
Les couples(26)et(62)et 6 ne sont pas premiers entre eux.sont à éliminer car 2
Finalement(x y)∈ {(560)(1520)(2015)(605)}.
Inversement : ok. FinalementS={(560)(1520)(2015)(605)}.
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)∈ {(19)(37)(73)(91)}puis
(x y)∈ {(1090)(3070)(7030)(9010)}.
Inversement : ok. FinalementS={(1090)(3070)(7030)(9010)}.

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−12b−1) =pgcd(2a0−12a1−1) =pgcd(2a1−12a2−1) =  =pgcd(2am−120−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éﬁnissonsa2     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+ 43n+ 3)|6.

Exercice 4 :[énoncé]
a) On aa=bq+ravec06r < b.

Diﬀusion 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

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