0% ont trouvé ce document utile (0 vote)
65 vues23 pagesCCCCCCCCCCC
Transféré par
Copie DartalibCopyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
0% ont trouvé ce document utile (0 vote)
65 vues23 pagesCCCCCCCCCCC
Transféré par
Copie DartalibCopyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
ENSEMBLES ET APPLICATIONS 5. RELATION o'tquivatence 30
+ B= ...,-8, 1, 6, 13,20,...} = 6 +72
Mais ensuite 7 = {...—7,0,7,14,21,...} =0 = 72. Ainsi Z/7Z = {0,1,2,
5} posside 7 éléments.
Remarque.
Dans beaucoup de situations de la vie courante, nous raisonnons avec les modulos. Par exemple pour 'heure :
les minutes et les secondes sont modulo 60 (aprés 59 minutes on repart a zéro), les heures modulo 24 (ou
modulo 12 sur le cadran a aiguilles). Les jours de la semaine sont modulo 7, les mois modulo 12,...
Mini-exercices.
1. Montrer que la relation définie sur N par xe@y <=> 222 EN est une relation e’équivalence. Montrer
quil y a3 classes d'équivalence.
2, Dans R* montrer que la relation définie par (x, y)@(x',y/) <> x+y’ =x" +y est une relation
aéquivalence. Montrer que deux points (x, y) et (x’, y’) sont dans une méme classe si et seulement
sils appartiennent & une méme droite dont vous déterminerez la direction.
3. On définit une addition sur Z/nZ par p+] = p +4. Calculer la table d’addition dans 2/62 (Cest-&-dire
toutes les sommes B+ J pour B,J € Z/62). Méme chose avec la multiplication B xj =P *G. Mémes
questions avec 2/52, puis 2/82.
Auteurs du chapitre Arnaud Bodin, Benjamin Boutin, Pascal Romon Nombres complexes
1, Les nombres complexes, définitions et opératicns
. Racines carrées, équaticn du
rie
Préambule
Léquation x +5 = 2 a ses coefficients dans N mais pourtant sa solution x =—3 n'est pas un entier naturel.
Il faut ici considérer ensemble plus grand Z, des entiers relatifs,
xt5=2 2 + cae
NOE? yg Pg Rc
3 a ses coefficients dans Z mais sa solution x =
2
De méme l'équation 2x = est dans l'ensemble plus grand
des rationnels Q. Continuons ainsi, I’équation x? = } & coefficients dans Q, a ses solutions x, = +1/V2
et x) =—1/¥3 dans ensemble des réels R. Ensuite l'équation x? = —V/2 & ses coefficients dans R et ses
solutions x; = +i v'V2 et x. =—i VV dans l'ensemble des nombres complexes C. Ce processus est-il sans
fin? Non! Les nombres complexes sont en quelque sorte le bout de la chaine car nous avons le théoréme
de d’Alembert-Gauss suivant : « Pour n’importe quelle équation polynomiale agx" + dy yx"! +--+ ax? +
x + a9 = 0 oit les coefficients a, sont des complexes (ou bien des réels), alors les solutions x;,...,X, sont dans
ensemble des nombres complexes »
Outre la résolution d’équations, les nombres complexes sappliquent a la trigonométrie, a la géométrie
(comme nous le verrons dans ce chapitre) mais aussi a Pélectronique, a la mécanique quantique, ete.
1. Les nombres complexes
1.1. Dét
Définition 1.
Un nombre complexe est un couple (a, b) € R que l'on notera a +ib NowipRes COMPLEXES 1. Les Nomares comPLexes 32
Cela revient a identifier 1 avec le vecteur (1, 0) de R, et i avec le vecteur (0,1). On note € l'ensemble des
nombres complexes. Si b =0, alors z =a est situé sur l'axe des abscisses, que l'on identifi & R, Dans ce
cas on dira que z est réel, et R apparait comme un sous-ensemble de C, appelé axe réel. $i b #0, x est dit
imaginaire et si b #0 et a=0, z est dit imaginaire pur,
1.2. Opérations
Siz=a+ibet2/ =a’ +ib’ sont deux nombres complexes, alors on définit les opérations suivantes
+ addition ; (a +ib)+(a’ +ib')=(a+a’)+i(b+b')
ik.
R
+ multiplication : (a +ib) x (a’ +ib’) = (aa’ — bb’) + i(ab’ + ba’). On développe en suivant les régles de
Ja multiplication usuelle avec la convention suivante :
1.3. Partie réelle et imaginaire
Soit =a +ib un nombre complexe, sa partie réelle est le réel a et on la note Re(2); sa partie imaginaire
est le réel b et on la note Im(2).
Re(z) Nowpnes compLexes 1
Par identification de © a R®, Vécriture 2 = Re(z) + ilm(2) est unique :
Re(2) = Re(2’)
za! > et
Im(z) = Im(z’)
En particulier un nombre complexe est réel si et seulement si sa partie imaginaire est nulle. Un nombre
complexe est nul si et et seulement si sa partie réelle et sa partie imaginaire sont nuls.
1.4, Calculs
Quelques définitions et calculs sur les nombres complexes.
+ Lopposé de 2 =a+ib est -z = (—a)+i(—b) =a ib.
+ La multiplication par un scalaire AER: A+ = (Aa) + i(AB).
+ Linverse : siz 6, il existe un unique 2! € C tel que 22/= 1 (08 1=1+4ix0).
Pour la preuve et le calcul on écrit z = a+ib puis on cherche 2’ = a’ + ib’ tel que 22’ = 1. Autrement
dit (@-+ib)(a! +ib') = 1. En développant et idencifiant les parties réelles et imaginaires on obtient les
équations
{ aa’—bb’=1 (Ly)
ab! +ba’=0 (Lz)
En écrivant aL, +bL2 (on multiplie la ligne (L) para, la ligne (L) par b et on ad
onen déduit
a’ (a? +b?
{ bi (a? +b?
Linverse de 2, noté 3, est done
itionne) et—bL +aLy
cll_a@_ |, -b _ a~ib
e z OR aR a2+b2
+ Ladivision : $ estle nombre complexe z x 3.
« Propriété d'intégrité : si za’ = 0 alors s = 0 ou 2’ =0.
+ Puissances : 2? = 22, 2" =2%--- x2 (1 fois, n EN). Par convention 2° = 1 et2* = (2)"= 2.
Proposition 1.
Pour tout 2 € C différent de 1
Lee tetenten
La preuve est simple : notons § = 1+z+2?+---+2", alors en développant S « (1— 2) presque tous les
termes se télescopent et on trouve $-(1—z)=1—2""7, Nowpnes compLexes 1
Remarque.
I nly pas ordre naturel sur C, il ne faut done jamais écrire z > 0 ou z <2!
1.5. Conjugué, module
Le conjugué de 2=a+ib est 3 =a—ib, autrement dit Re(Z) = Re(2) et Im(3) =—Im(z). Le point Z est le
symétrique du point z par rapport & l'axe réel
Le module de x =a +ib est le réel positif |z| = va? +52. Comme z x
Je module vaut aussi |z| = V2.
? alors
(a+ib)(a—ib)
Quelques formule :
Proposition 2 (Liinégalité triangulaire).
e+e'| (xtiy=atid
2 en identifiant parties
et parties imaginaires.
Petite astuce ici : nous rajoutons P'équation ||? = |z| (qui se déduit bien sfir de «o?
x? +y* = Ja? + B2, Nous obtenons des systémes équivalents aux précédents :
aya Vere
Discutons suivant le signe du réel b. Si b > 0, x et y sont de méme signe ou nuls (car 2xy = b > 0) done
ont (VatwtisasiVVar+it—a),
aa ( VVatw tai Vere 5*—a)
En particulier si b = 0 le résultat dépend du signe de a, sia > 0, Va? =a et par conséquent @ = +7,
tandis que sia <0, Ja? =—a et done w = +i ya = +i Via] oO
v2
etsib<0
Il west pas nécessaire d’apprendre ces formules mais il est indispensable de savoir refaire les calculs.
Exemple 2.
Les racines carrées de i sont +42(1 +i) et —2(1 +i).
En effet
Rajoutons la conditions |o|* = |i| pour obtenir le systéme équivalent au précédent
2 1
xeay’
axy=1 =
ery
=sbsl Nowpnes compLexes Rac
2.2. Equation du second degré
Proposition 4.
Léquation du second degré az* + bz +c = 0, ott a,b,c € C et a # 0, posséde deux solutions 21,2, € C
éventuellement confondues.
Soit A = b* —4ac le discriminant et 5 € € une racine carrée de A. Alors les solutions sont
b+, | nbn 8
2a ar
a
Et si A =0 alors la solution z = 2 =z» = —b/2a est unique (elle est dite double). Si on s‘autorisait & écrire
5 = VB, on obtiendrait la méme formule que celle que vous connaissez lorsque a, b,¢ sont réels.
Exemple 3.
“1s
+ 242415005 V3, les solutions sont 2 ae
2, 142040
+ P4244 =0,A=i,6 = 2(1 +i), les solutions sontz aeeor) t+ 4a+).
On retrouve aussi le résultat bien connu pour le cas des équations a coefficients réels
Corollaire 1.
Si les coefficients a, b,¢ sont réels alors A € B et les solutions sont de trois types :
b
+ siA=0, laracine double est réelle et vaut —>-,
=ba va
+ si A> 0, ona deux solutions réelles —S"—,
b+iv—a
+ si A <0, ona deux solutions complexes, mais non réelles, — 7
a
Démonstration. On écrit la factorisation
be by _ boc
a?tbzte = a(2?4+22+£)=a((2+2) 2 4f
+b (+3 ‘) (( xa) ats)
(+2)-4 = (+2)-S
NEY aa) ~ 48) 2a) ~ a2
((+z:)-a)(+z)*)
a((2+2)-2)((2+ 2 )42
2a)” 2a 2a) * 2a
o(e-=222) (2-82) 3kEZ,0=0'42kn o> {
Proposition 5.
Largument satisfait les propriétés suivantes :
+ arg(sz’) = arg(z) + arg(z’) (mod 2m)
+ arg(2") = narg(z) (mod 27)
+ arg(1/z) = —arg(z) (mod 2n)
+ arg(#) = args (mod 2) Nowpnes compLexes 3, ARGUN
Démonstration
zz’ = |e|(cos@ +isin 9) |2'| (cos 6’ +isin 6’)
= |z2’|(cos @ cos &’ —sin @ sin 6’ + i(cos sin 6’ + sin @ cos 0’))
|=2'|(cos(@ + 0’) +isin(9 +0"))
done arg(zz’) = arg(z) + arg(z’) (mod 27). On en déduit les deux autres propriétés, dont la deuxitme par
récurrence. a
3.2. Formule de Moivre, nota’
n exponentielle
La formule de Moivre est
(cos 0 + isin 0)" = cos(nd) +isin(nd)
Démonstration. Par récurrence, on montre que
(cos@ +isind)" = (cos@ +isind)"" x (cosé +isiné)
(cos ((n— 1) 6) + isin (x1) 8)) x (cos + isin)
= (cos((n—1) 4) cos 6 — sin ((n—1) 4) sin 8)
+i(cos((n—1) 0)sin0 + sin ((n—1) 8) cos 0)
= cosnd +isinnd
Nous définissons la notation exponentielle par
cos +isin®
et donc tout nombre complexe s'écrit,
pee
‘ott p = |z| est le module et 6 = arg(z) est un argument.
Avec la notation exponentielle, on peut écrire pour z = pe'® et 2’ = p'e'™”
22! = pp'e'®el®" = pp'ele8)
2 = (pe!) =p (c= preino
Az =1/ (pel?) = de“?
z=pel?
La formule de Moivre se réduit & Pégalité :| (e'?)" = el"? |.
Et nous avons aussi : pe’ = p’e!® (avec p, p’ > 0) si et seulement si p = p! et @ = 6’ (mod 2).
3.3. Racines n-iéme
Définition 3.
Pour z €€ et n EN, une racine n-
-me est un nombre w € C tel que «” NowipRes COMPLEXES 3, ARGUMENT ET
Proposition 6.
Ty an racines n-iémes @o,@1,...,@n-1 de x = pel®,
ce sont:
Démonstration. Ecrivons co", Nous obtenons
done pel? = " = (re'*)" = r"e'"*. Prenons tout dabord le module : |rteint| =r" et done
p'” (il agit ici de nombres réels). Pour les arguments nous avons e'"' =e! et donc nt (mod 2)
(n‘oubliez surtout pas le modulo 2x1). Ainsi on résout nt = 0 + 2kr (pour k € Z) et done t= $ + 2. Les.
= | Mais en fait il n'y a que n solutions distinctes
CAF ty = Wp, @quy = 01, -- Ainsi les n solutions sont 699, €215.-+5@n-a-
solutions de l'équation eo" =z sont donc les @, =p!"
a
Par exemple pour z
groupe multiplicatit.
|, on obtient les nt racines n-igmes de Vunité e**!™, k
1 qui forment un
mens
j
Racine 3-iéme de lunité ( = 1,n=3) Racine 3-iéme de —1 (2 =—1, n= 3)
Les racines 5-iéme de l'unité (2 =
=5) forment un pentagone régulier
3.4. Applications a la trigonométrie
Voici les formules d’Buler, pour @€R:
eae éfne
6=—>— , sine
cos 3 sin
i@ ie _,i8 Nowpnes compLexes 3, ARGUN
Ges formules s‘obtiennent facilement en utilisant la définition de la notation exponentielle. Nous les
appliquons dans la suite a deux problémes : le développement et la linéarisation.
Développement. On exprime sinn@ ou cosnd en fonction des puissances de cos et sind.
Méthode : on utilise la formule de Moivre pour écrire cos(n@) + isin(n®) = (cos@ +isin#)" que l'on
développe avec la formule du binéme de Newton.
Exemple 4.
cos3+isin3@ = (cosé +isind)?
= cos! 0 + 3icos?¢ sin@ —3cos@ sin? @— isin? 9
(cos? @ — 30s 6 sin? @) + i(3 cos? 6 sin @ —sin® @)
En identifiant les parties réelles et imaginaires, on déduit que
3cos* 8 sin 6 —sin® 9.
c0s36 =cos*@—3cos@sin?@ et sin3
Linéarisation. On exprime cos" 9 ou sin” 9 en fonction des cosk@ et sink® pour k allant de 0A n.
5)". on développe a Vaide du bindme de Newton
‘Méthode : avec la formule d’Euler on écrit sin" 9 = (£
puis on regroupe les termes par paires conjuguées.
Exemple 5.
sin’ @ =
((el? ae! Pe? + Bel? (en! — (e128)
8)
Og 80 gio _,-io
4 2i 2i
sin3@ | 3sin@
(e289 —3e!9 4-36-18 —
Mini-exercices.
1. Mettre les nombres suivants sont la forme module-argument (avec la notation exponentiell): 1 i,
1, “i, 84,141, ¥B—i, Vi, Zhe, (/3 Holt 20xxx est Pannée en cours.
2, Calculer les racines 5-iéme de i.
3, Calculer les racines carrées de + 4 de deux facons différentes. En déduire les valeurs de cos et
sing.
4, Donner sans calcul la valeur de coy +21 +--+ + @q_1, Olt les 02; sont les racines n-idme de 1
5, Développer cos(40) ; linéariser cos* @ ; calculer une primitive de @ > cos* @ s compuaxts eT ctoeTare 42
Nowpnes compLexes
4. Nombres complexes et géomeétrie
On associe bijectivement 4 tout point M du plan affine R* de coordonnées (x, y), le nombre complexe
2=x+iy appelé son affixe.
4.1, Equation complexe d’une droite
Soit
ax+by=c
Véquation réelle d'une droite 9 : a,b,c sont des nombres réels (a et b n'étant pas tous les deux nuls)
inconnues (x, y) € R?,
Eerivons z =x + iy €€, alors
yattt a
2 2i
donc 9 a aussi pour équation a(z + 2) —ib(z —2) = 2c ou encore (a—ib)s + (a +ib)z = 2c. Posons
@=atib eC’ etk=2c ER alors 'équation complexe une droite est
Gr4 wi =k
4.2. Equation complexe d'un cercle
Soit (A,r) le cercle de centre 1 et de rayon r. C'est ensemble des points M tel que dist(9,M) =r. Si
Yon note w Vaffixe de 0 et z Vaffixe de M. Nous obtenons :
dist(9,M)=r > z-ol=r > pol =r? > (2-e)E—0)
et en développant nous trouvons que l’équation complexe du cercle centré en un point daffixe w et de
rayon rest
ek—O2— wt
aleP
olweCetreR.
4.3. Equation Esl = k
Proposition 7.
Soit A,B deux points du plan et k € R,. Lensemble des points M tel que MA =k est
+ une droite qui est la médiatrice de [AB], si k = 1,
+ un cercle, sinon. Nowpnes compLexes 4
ES ComPLExES eT GéoméTRIE 43
Exemple 6.
Prenons A le point d'affixe +1,B le point daffixe —1. Voici les figures pour plusieurs valeurs de k.
Par exemple pour k = 2 le point M dessiné vérifie bien MA = 2MB.
Démonstration. Si les affixes de A,B,M sont respectivement a,b,z, cela revient a résoudre Péquation
a
= kes e—aP = led P
<= (e-a)@—a) = M(e— b)@—B)
=> (1k?) —2(4 — k*b) — (a — kb) + |al? —k? [bP
Done si k = 1, on pose @ = a~ kb et Péquation obtenue 26 + Ze = |a|*—K?|b|? est bien celle d'une
droite, Et bien stir Fensemble des points qui vérifient MA = MB est la médiatrice de [AB]. Si k # 1 on pose
oo Crest I’équation d'un cercle de centre
s-1°P alors léquation obtenve est 22-26-00
et de rayon r satisfaisant r?—|o[? = =SEHCEE, soit r? = EERE 4 atic a
Ces caleuls se refont au cas par cas, il n'est pas nécessaire d’apprendre les formules.
Mini-exercices.
1, Calculer l'équation complexe de la droite passant par 1 et i
2, Calculer 'équation complexe du cercle de centre 1 + 2i passant par i
le-il
3. Caleuler Yéquation complexe des solutions de (==>; = 1, puis dessiner les solutions
le—
Ie
4, Méme question avec
Auteurs du chapitre Arnaud Bodin, Benjamin Boutin, Pascal Romon Arithmétique
Préambule
Une motivation : Varithmétique est au coeur du cryptage des communications. Pour crypter un message on
commence par le transformer en un -ou plusieurs~ nombres. Le processus de codage et décodage fait appel
& plusieurs notions de ce chapitre
+ On choisit deux nombres premiers p et q que l'on garde secrets et on pose n= p xq. Le principe étant
‘que méme connaissant m il est trés difficile de retrouver p et q (qui sont des nombres ayant des centaines
de chiffres)..
+ La clé secrite et la clé publique se calculent a Vaide de Palgorithme d’Euclide et des coefficients de
Bézout.
+ Les caleuls de cryptage se feront modulo n.
+ Le décodage fonctionne grace & une variante du petit théoréme de Fermat.
1. Division euclidienne et pgcd
1.1. Divisibilité et division euclidienne
Définition 1.
Soient a,b €Z. On dit que b divise a et on note bla s'il existe q € Z tel que
ba
Exemple 1.
7121 ; 6148; @ est pair siet seulement si 2a.
+ Pour tout a €Z on aal0 et aussi 1a.
Si all alors a= +1 owa=—1.
(alb et bla) => b
{alb et ble) => ale
{alb et ale) => alb +e L. Division evcuprenne er poco 46
‘Théoréme 1 (Division euclidienne).
Soit a € Z et b EN \ {0}. Il existe des entiers q,r € Z tels que
qtr et (O 0 pour simplifier. Soit 4 = {n €N | bn < a}. C'est un ensemble non vide
car
0 W. De plus pourn €.W, onan a carq+1¢4, done
‘éléments dans W, notons
qb 0 pour avoir —1 < q—q' <1. Comme q—q’ est un entier, la seule possibilité est
q—q = et done q =4q'. Repartant de r’—r = b(q—q') on obtient maintenant r =r’
1.2. pged de deux entiers
Définition 2.
Soient a,b € Z deux entiers, non tous les deux nuls. Le plus grand entier qui divise & la fois a et b
s‘appelle le plus grand diviseur commun de a, b et se note pged(a, b).
Exemple 3.
+ pgcd(21,14) =7, pgcd(12, 32) = 4, pged(21, 26) = 1
+ pged(a,ka) =a, pour tout ke Zeta >0.
+ Cas particuliers. Pour tout a > 0 : pged(a,0) =a et pged(a, 1) = 1 L. Division evcuprene er poco 47
1.3. Algorithme d’Euclide
Lemme 1.
Soient a, b € N*. Eerivons la division euclidienne a = bq +r. Alors
pged(a, b) = pgcd(b,r)
En fait on a méme pged(a, b) = pged(b, a —qb) pour tout q € Z. Mais pour optimiser Palgorithme d'Euctide
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 stir les mémes.
+ Soit d un diviseur de a et de b, Alors d divise b donc aussi bq, en plus d divise a done d divise a— bq = r.
+ Soit d un diviseur de b et de r. Alors d divise aussi bq +r =a
oO
Algorithme d’Euclide.
On souhaite caleuler le pged de a, b € N*. On peut supposer a > b. On caleule des divisions euclidiennes
successives. Le pged sera le dernier reste non nul.
+ division dea par b, a= bq, +r). Parle lemme 1, pged(a, b) = pgcd(b,r,) et sir; = Oalors pged(a, b) =b
sinon on continue
+ b=riq+r, pged(a,b) = pged(b,r)
+ 1 =Tads+rs, pged(a, b) = pged(r2,rs)
pgcd(ry, ra),
+ rhea = raeade + Pe P8CAC@, b) = pged(raa re),
© re = ede +0. pged(a, b) = pged(ry, 0) = ry.
Comme & chaque étape le reste est plus petit que le quotient on sait que 0 < riyx ry > ry >-+ BO.
Exemple 4.
Calculons le pged de a = 600 et b = 124.
600
124!
104!
20 4 x 5+ 0
Ainsi pged(600, 124) = 4.
Voici un exemple plus compliqué
Exemple 5.
Calculons pged(9945, 3003),
9945 = 3003 x 3 + 936
3003 = 936 x 3 + 195
936 = 195 x 4 + 156
195 = 156 x 1 + 39
156 = 39 x 440
Ainsi pged(9945, 3003) = 39. 1.4. Nombres premiers entre eux
Définition 3.
Deux entiers a,b sont premiers entre eux si pged(a, b) = 1
Exemple 6.
Pour tout a € 2, a et a +1 sont premiers entre eux. En effet soit d un diviseur commun aa et &.a+1. Alors
d divise aussi a+ 1—a. Done d divise 1 mais alors d =—1 ow d = +1. Le plus grand diviseur de a et a+1
est done 1. Et done pged(a,a+1)=1.
Si deux entiers ne sont pas premiers entre eux, on peut s'y ramener en divisant par leur pged :
Exemple 7.
Pour deux entiers quelconques a,b € Z, notons d = pged(a, b). La décomposition suivante est souvent
utile
a =a'd ho 0
{s = pig EE 1b’ E Zet pged(a’, b’)
Mini-exercices.
1. Berire la division euclidienne de 111111 par 20xx, ot 20xx est l'année en cours.
2. Montrer qu'un diviseur positif de 10008 et de 10014 appartient nécessairement a {1, 2,3, 6}
3, Calculer pged(560, 133), pged(12 121,789), pgcd(99 999, 1110).
4, Trouver tous les entiers 1 < a < 50 tels que a et 50 soient premiers entre eux. Méme question avec 52.
2. Théoréme de Bézout
2.1, Théoréme de Bézout
‘Théoréme 2 (Théoréme de Bézout).
Soient a,b des entiers. I existe des entiers u,v € Z els que
au + by = pged(a, b)
La preuve découle de Valgorithme d’Euclide. Les entiers u,v ne sont pas uniques. Les entiers u, v sont des
coefficients de Bésout. Ils sobtiennent en « remontant » Valgorithme 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 pged a l'aide de la derniére ligne oi le reste est non nul. Puis on remplace le reste de la
ligne précédente, et ainsi de suite jusqu’a arriver & la premiere ligne.
600 = 124 x 44104. 4 =| 600x6+124% (29)
124 x (-5) + (600-124 x 4) x6
4 sro4sxi4 20 | [4a [ 2AxCs+104x6
104 —(124— 104 x 1) x5
104= 20x54 4 = [ 104-20%5
20 = 4 x54 0 Ainsi pour u = 6 et v =—29 alors 600 x 6 +124 x (29) = 4.
Remarque.
+ Soignez vos calculs et leur présentation. C'est un algorithme : vous devez aboutir au bon résultat! Dans
la partie droite, il faut & chaque ligne bien la reformater. Par exemple 104—(124— 104 x 1) x55 se réécrit
en 124 x (5) + 104 x6 afin de pouvoir remplacer ensuite 104.
+ Noubliez. pas de vérifier vos calculs! C'est rapide et vous serez certains que vos calculs sont exacts. Ici
on vérifie Ala fin que 600 x 6 + 124 x (—29) = 4,
Exemple 9.
Caleulons les coefficients de Bézout correspondant A pged(9945,3003) = 39.
9945 = 3003 x 3+ 936 39 = 9945 x (—16) +3003 x 53.
3003 = 936 x3+195| 739 =
936 = 195 x 4+ 156
195 = 156 x 1+ 39 195-1561
156 = 39 x4+ 0
Avvous de finir les calculs. On obtient 9945 x (—16) + 3003 x 53 = 39.
2.2. Corollaires du théoréme de Bézout
Corollaire 1.
Si dla et d|b alors d| pged(a, b).
Exemple : 4|16 et 4|24 done 4 doit diviser pged(16,24) qui effectivement vaut 8.
Démonstration. Comme dlau et d|bv done dlau + by. Par le théoréme de Bézout dl pged(a, b). a
Corollaire 2.
Soient a, b deux entiers. a et b sont premiers entre eux si et seulement si il existe u,v € Z tels que
aut byv=1
Démonstration. Le sens => est une conséquence du théoréme de Bézout.
Pour le sens ¢ on suppose quil existe u,v tels que au + bv = 1. Comme pged(a, b)la alors pged(a, b)law.
De méme pged(a, b)|bv. Done pgcd(a, b)Jau + by = 1. Done pged(a, b) = 1. a
Remarque.
Si on trouve deux entiers u’,’ tels que au’ + by’ = d, cela n'implique pas que d = pged(a, b). On sait
seulement alors que pged(a, b)|d. Par exemple a= 12, b= 8; 12x 1+8 x 3=36 et pgcd(a,b) = 4.
Corollaire 3 (Lemme de Gauss).
Soient a, b,c €Z.
Si albe et pged(a,b)=1 alors alc
Exemple : si 4|7 xc, et comme 4 et 7 sont premiers entre eux, alors 4[c.
Démonstration. Comme pged(a, b) = 1 alors ilexiste u, v € Z tels que au+ bv = 1. On multiplie cette égalité
par ¢ pour obtenir acu + bev = c. Mais alacu et par hypothase albcv donc a divise acu+ bev=c. 2.3. Equations ax + by =c
Proposition 1.
Considérons Véquation
ax+by =e ®
ott a,b,c €Z.
1. Léquation (F) posséde des solutions (x, y) € 2? si et seulement si pged(a, b)|c.
2. Si pgcd(a, b)|c alors il existe méme une infinité de solutions entiéres et elles sont exactement les (x, ¥) =
(Xo + ak, Yo + BK) aver Xo, Yost, € 2 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. II est bon de refaire toutes les étapes de la
23K 7x (x—x9) $23 x 16 x (¥ Yo) =0
=> Wx-x)=-1607- yo)
Nous avons simplifié par 23 qui est le pged de 161 et 368. (Attention, n’oubliez surtout pas cette
simplification, sinon la suite du raisonnement serait fausse.)
Ainsi 7|16(y — yo), or pged(7, 16) = 1 donc par le lemme de Gauss 7ly — yo. I existe done k € Z tel
que y —yo = 7 x k. Repartant de 'équation (+) : 7(x— x9) = —16(y — yo). On obtient maintenant
Tx = x9) =—16 x7 x k, Droit x — xp = 16k. (Crest le méme k pour x et pour y.) Nous avons done (9) = (x 16k, yo + 7K). Il n'est pas dur de voir que tout couple de cette forme est solution de
Véquation (E). Il reste donc juste a substituer (xp, ¥q) par sa valeur et nous obtenons :
Les solutions entiéres de 161x + 368y = 115 sont les (x, y) = (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
Véquation.
2.4. ppem
Définition 4.
Le ppem(a, b) (plus petit multiple commun) est le plus petit entier > 0 divisible par a et par b.
Par exemple ppem(12, 9) = 36.
Le pgcd et le ppem sont liés par la formule suivante
Proposition 2.
Si a, b sont des entiers (non tous les dewx nuls) alors
pgcd(a, b) x ppem(a, b) = abl
Démonstration. Posons d= pged(a, b) et m = =. Pour simplifier on suppose @ > 0 et b > 0. On écrit
a= da! et b = db’, Alors ab = d?a’b’ et donc m = da’b’. Ainsi m= ab! = a’b est un multiple de a et de b.
Ireste & montrer que c'est le plus petit multiple. Sin est un autre multiple de a et de b alors n = ka = £b done
keda’ = Edb! et ka’ = €b', Or pgcd(a’, b’) = 1 et a’|£b’ donc a’|é. Done a’b|¢b et ainsi m=a'bléb=n. O
Voici un autre résultat concernant le ppem qui se démontre en utilisant la décomposition en facteurs
premiers
Proposition 3.
Si ale et ble alors ppem(a, b)Ie.
serait faux de penser que ab|c. Par exemple 6[36, 9[36 mais 6x9 ne divise pas 36. Par contre ppem(6, 9) =
18 divise bien 36,
Mini-exercices.
1, Calculer les coefficients de Bézout correspondant & pged(560, 133), pged(12.121, 789)
Montrer a Taide d'un corollaire du théoréme de Bézout que pged(a,a-+1)=1.
5 720x + S4y =
3 216x + 92y =8.
2
3, Résoudre les équations : 407x +129y
4, Trouver les couples (a, b) vérifiant pgcd{a, b) = 12 et ppem(a, b) = 360. 3. NOME:
3. Nombres premiers
Les nombres premiers sont -en quelque sorte les briques élémentaires des entiers : tout entier sécrit comme
produit de nombres premiers.
3.1. Une infinité de nombres premiers
Définition 5.
Un nombre premier p est un entier > 2 dont les seuls diviseurs positifs sont 1 et p.
Exemples : 2,3,5,7,11 sont premiers, 4= 2.x 2, 6 = 2x3, 8=2 x4 ne sont pas premiers
Lemme 2.
Tout entier n > 2 admet un diviseur qui est un nombre premier.
Démonstration, Soit 9 Vensemble des diviseurs de n qui sont > 2
@={k>2| kin}.
ensemble @ est non vide (car n € 9), notons alors p = min :
Supposons, par l'absurde, que p ne soit pas un nombre premier alors p admet un diviseurg tel que 1
Vous aimerez peut-être aussi
