Congruences 2 Chapitre B
Contents
1. D terminer le chiffre manquant d un billet non falsifi de num ro U49834 782406 PGCD 5 Chapitre B P CD 1 PGCD 1 1 Cours D finition 3 Soit a b 0 0 un couple d entiers naturels pgcd a b est le plus grand diviseur com mun de a et b Dans la suite de ce chapitre on note D a l ensemble des diviseurs strictement positifs de a et D a b l ensemble des diviseurs strictement positifs de a et b Cette notation n est pas universelle et doit tre red finie si elle est utilis e dans une copie Th or me 6 Soit a b 0 0 un couple d entiers naturels 1 pgcd a b pgcd b a 2 pgcd a 0 a 3 bla pgcd a b b D monstration 1 Vz ED a b x lt maz a b donc D a b est fini or 1 D a b donc D a b est fini et non vide donc D a b poss de un plus grand l ment qui est pgcd a b or D a b D a N D b D b N D a D b a donc pgcd a b pgcd b a 2 D 0 N donc D a 0 D a N D 0 D a NN D a donc pgcd a 0 a 3 bla D b c D a D a b D a N D b D b pgcd a b b Lemme 1 Soit a b N Soit r le reste de la division euclidienne de a par b pgcd a b pgcd b r D monstration Soit a bq r la division euclidienne de a par b Montrons que D b r C D a b Soit d D b r de D b r et a bq r donc d E D a d D b r donc d 1 0 a donc d D a N D b donc d D a b Mon2. MATRICES CARREES INVERSIBLES 19 20 MATRICES ET ETUDES ASYMPTOTIQUES Chapitre F Matrices et tudes asymptotiques 1 SUITES R CURRENTES ET MATRICES 1 1 Cours ugo 5 vo 2 Yn gt 0 unr1 1 Tun 0 6un 3 Yn gt 0 Uni1 5Un 0 lun 1 cessifs de ces suites l aide du calcul matriciel Exemple 22 Soit deux suites d finies par Calculer les termes suc ugo 11 Exemple 23 Soit une suite d finie par ui 2 Calculer les termes successifs Yn gt 0 Un 2 3un 1 0 Eur de cette suite l aide du calcul matriciel Th or me 25 Soit une suite de matrices colonnes Xn telle que pour tout entier n gt 0 Xn11 AX Alors pour tout n gt 0 Xn A Xo D monstration Par r currence Remarque 17 Il y a un th or me analogue avec des matrices lignes 2 CONVERGENCE ET ETAT STABLE 2 1 Cours Remarque 18 Tout ce qui est dit jusqu la fin de ce chapitre peut tre transpos au cas des matrices lignes D finition 15 On dit que la suite de matrices colonnes X de taille p est convergente ssi les suites form es par les coefficients sont convergentes La limite de cette suite est alors la matrice colonne form e par les p limites obtenues Dans tous les autres cas on dit que la suite est divergente Th or me 26 Si une suite de matrices colonnes Xn v
3. matrices M et N carr es ou colonnes de tailen AxM N amp M AHxN D monstration 3 3 Exemple 19 Soit M i 6 et N 6 R soudre MX X N Th or me 22 Soit A une matrice inversible Pour tout r el k 0 la matrice kA est inversible et sa matrice inverse est FAE D monstration Remarque 16 V rifier que vous savez d terminer l inverse d une matrice avec votre calculatrice Si 4 10 2 _ 1 0 5 E A alors vous devez trouver A7 P 5 2 18 MATRICES CARREES INVERSIBLES a b Th or me 23 Soit M M est inversible ssi ad bc 0 D monstration Voir l Activit 1 2 Travailler son cours Exercice 5 Soit A et B des matrices inversibles Quelle est l inverse de A x B 2 APPLICATIONS 2 1 Cours Th or me 24 Soit AU V l criture matricielle d un syst me lin aire e Si la matrice A est inversible le syst me a une unique solution gale Al e Sinon le syst me a soit une infinit de solutions soit pas de solution D monstration Voir l Activit pour la justification du deuxi me point Exemple 20 Soit A 1 2 4 B 2 6 5 C 4 0 3 Montrer que ces 3 points d finissent un plan et d ter miner une quation de ce plan Exemple 21 Soit 4 o e D ta 9 P C 0 V rifier que A P x D x P En d duire l expression de A
4. 1 amp Ju v Z ua vb 1 D monstration L identit de B zout justifie le sens direct Montrons la r ciproque Supposons que ua vb 1 pgcd a b divise a et b donc divise ua vb donc divise 1 Donc pgcd a b 1 1 x2 1x3 1 Remarque 7 Il wy a pas unicit de u et v non plus Exemple a 2 et b 3 A x 2 3x3 1 Exemple 6 Soit n N Montrer que 2n 1 et 9n 4 sont premiers entre eux Exemple 7 Soit n N D terminer pgcd 2n 1 2n 3 2 2 Travailler son cours Exercice 3 Montrer que pgcd 5004 2002 2 sans utiliser l algorithme d Euclide 3 TH OR ME DE GAUSS 3 1 Cours a bc pgcd a b 1 ae Th or me 13 de Gauss Soit a b c N D monstration albc donc N bc ka pgcd a b 1 donc d apr s le th or me de B zout Ju v Z ua vb 1 donc cau cvb c or bc ka donc cau kav c donc uc kv a c donc ajc alc Corollaire 1 Soit a b c N bje gt ablc pgcd a b 1 8 PGCD D monstration Supposons les hypoth ses du th or me Ik k N c ka k b donc a k b or pgcd a b 1 donc d apr s le th or me de Gauss gl donc Jk N k k a or c k b donc c k ab donc ablc Exemple 8 Montrer que le produit de trois entiers naturels cons cutifs est divisible par 6 Exemple 9 Montrer que le produit de 4 entiers naturels c
5. A et Xn Xo A dans le cas d tats modelis s par une matrice ligne e Yn N Xn41 AX et Xn A Xo dans le cas d tats modelis s par une matrice colonne 16 MATRICES ET VOLUTION DE PROCESSUS 2 2 Travailler son cours Exercice 4 Ecrire la matrice de transition associ e au graphe ci contre chaque pas on passe d un sommet un autre par une ar te issue de ce sommet choisie de fa on quiprobable Les tats sont repr sent s par des matrices colonnes MATRICES CARREES INVERSIBLES 17 Chapitre E Matrices carr es inversibles 1 MATRICE INVERSE 1 1 Cours D finition 13 On appelle matrice unit de taille ou d ordre n la matrice 7 dont tous les coefficients sont nuls except s ceux de la diagonale issue du coin en haut gauche qui valent tous 1 Th or me 19 Pour toute matrice carr e A de taille n A X In In x A A Remarque 15 Par convention pour toute matrice carr e A de taille n A In D finition 14 Soit une matrice carr e de taille n A est inversible s il existe une matrice B telle que Ax B Bx A n On dit alors que B est l inverse de A et on note B A Th or me 20 Pour montrer que est inversible il suffit de montrer que A x B 1 ou Bx A hn D monstration On admet ce th or me Th or me 21 Soit 4 une matrice inversible de taille n Pour toutes matrices M et N carr es ou lignes de taille n M x A N amp M N x At Pour toutes
6. MATH MATIQUES SP CIALIT F HUMBERT TABLE DES MATI RES Chapitre A Congruences Chapitre B PGCD Chapitre C Nombres premiers Chapitre D Matrices et volution de processus Chapitre E Matrices carr es inversibles Chapitre F Matrices et tudes asymptotiques 11 14 17 20 2 CONGRUENCES Chapitre A Congruences 1 DIVISIBILIT 1 1 Cours D finition 1 Pour tous entiers relatifs m et n m divise n ssi il existe un entier relatif k tel que n km Notation 1 On note mjn Remarque 1 Tout entier relatif est un diviseur de 0 Th or me 1 Vp q r Z pla gt plr qlr Th or me 2 Si p divise m et n alors p divise toute combinaison lin aire coefficients entiers de m et n 2 DIVISION EUCLIDIENNE 2 1 Cours Axiome 1 Tout ensemble non vide d entiers naturels admet un plus petit l ment n mq r Th or me 3 Vn Z Vm N la E Z ren Erem q est le quotient et r le reste de cette division euclidienne Exemple 1 328 17 x 19 5 q 19 r 5 Exemple 2 328 17 x 20 12 q 20 r 12 D monstration Soit E k N km gt n Existence lorsque n gt 0 gt 1 Si donc n 1 m gt n donce n 1 E donc E donc E admet un plus petit l ment ko Soit q ko 1 et r n qm qm r n ko 1 m lt n lt kom donc 0 lt n ko 1 m lt m donc 0 lt n qm lt m donc 0 lt r lt m Existence lorsqu
7. e E L ensemble des solutions de E est NOMBRES PREMIERS 11 Chapitre C Nombres premiers 1 D FINITION 1 1 Cours D finition 5 Un nombre naturel est premier s il poss de exactement deux diviseurs positifs 1 et lui m me Remarque 8 Est ce que 0 est premier Est ce que 1 est premier 2 D COMPOSITION EN PRODUIT DE FACTEURS PREMIERS 2 1 Cours Lemme 2 Soit n un entier naturel non premier Son plus petit diviseur diff rent de 1 est premier D monstration Soit E l ensemble des diviseurs de n priv de 1 et de lui m me Comme n n est pas premier cet ensemble est non vide donc il admet un plus petit l ment p Supposons que p n est pas premier p poss de donc un diviseur p diff rent de 1 et de lui m me donc 1 lt p lt p plp et pin donc p In pln et 1 lt p donc p est dans E or p lt p donc p n est pas le plus petit l m nt de E CONTRADICTION On a montr par l absurde que p est premier Lemme 3 Si p est premier avec a et avec b alors p est premier avec ab D monstration Soit p premier avec a et b D apr s le th or me de B zout il existe les relatifs u v w v tels que up va 1 et up Yb 1 donc 1 up va u p v b uu p uv b vv a p vv ab donc d apr s le th or me de B zout p est premier avec ab Remarque 9 Ce lemme se g n ralise par r currence un nombre quelconque de facteurs Th or me 14 Tout entier natur
8. e ce sont des nombres premiers on a n cessairement p q or les d compositions de d part taient distinctes donc les deux d compositions suivantes sont distinstes P2 X X Pr q1 X X qi 1 X qi 1 qs ce qui contredit l hypoth se de r currence On a montr P par l absurde Conclusion On a montr par r currence que la d composition en facteurs premiers est unique Exemple 12 En utilisant la d composition en facteurs premiers d terminer le pgcd et le ppcm de 13734 et 91260 Lemme 4 Soit p un nombre premier et a et b deux entiers naturels Si pjab alors pja ou p b D monstration Remarque 10 Ce lemme se g n ralise par r currence un nombre quelconque de facteurs Th or me 15 Soit p x x pr la d composition d un entier naturel n en facteurs premiers Les diviseurs d de n sont de la forme d ph x x pr o les Bi v rifient 0 lt bi lt ai D monstration Les nombres de la forme de la forme pj x x per o les 8 v rifient 0 lt 6 oz sont clairement des diviseurs de n R ciproquement soit d un diviseur de n Tout facteur premier de d divise n donc d apr s le lemme divise l un des p donc est gal p On en d duit en regroupant les facteurs que d peut s crire sous la forme d pf x x Pr Il reste montrer que pour tous les i 0 lt B lt qai Si ce n tait pas le cas pour un don
9. e n lt 0 On se ram ne au cas pr c dent en effectuant la division euclidienne de n par m n qm r et 0 lt r lt m n mq r g 1 m m r Si r 0 la premi re expression est la division euclidienne cherch e sinon c est la deuxi me Dans ce dernier cas on v rifie la condition sur le reste 0 lt 7 lt m donc m lt r lt 0 donc0 lt m r lt m Existence lorsque n 0 n mx0 0et0 lt 0 lt m Unicit Supposons qu il existe deux divisions euclidiennes diff rentes n mxgq r mxq r g dm r r lt a donc m lt r r lt m or rest divisible par m donc r r 0 or 1 donc q g 0 Absurde Remarque 2 Plus de d nominateurs en Sp cialit CONGRUENCES 3 2 2 Travailler son cours Exercice 1 On note q et r le quotient et le reste de la division euclidienne de a par b Vrai Faux 1 2 3 4 Le reste de la division euclidienne de 2a par b est 2r Le quotient de la division euclidienne de 2a par b est 2q 1 2 3 Le reste de la division euclidienne de a par q est r 4 Le reste de la division euclidienne de a par b est b r 3 CONGRUENCES 3 1 Cours D finition 2 Soit n N Soit a b Z a et b sont congruents modulo n ssi a b est divisible par n Notation 2 Elles sont nombreuses a b n a b mod n a b n a b mod n Th or me 4 Pour tous entiers relatifs a et b et tout entier naturel n non nul a b n ssia etb
10. el sup rieur ou gal 2 se d compose en produit de facteurs premiers Cette d composition est unique l ordre pr s des facteurs On note alors n pf X p3 X X pr o pr P2 Pr sont des nombres premiers distincts et 1 2 a sont des entiers naturels non nuls D monstration Existence Si n est premier la propri t est tablie Sinon Soit p le plus petit diviseur de n diff rent de 1 Ce nombre existe et est premier d apr s le premier lemme Soit n E N lt N Si n est premier la propri t est tablie Sinon on r p te le processus en d finissant p2 n2 etc On cr e ainsi une suite d entiers n naturels strictement d croissante Cette suite est n cessairement finie et son dernier terme est premier En regroupant les facteurs on obtient n pt x po x x par Unicit Soit P La d composition est unique pour tout entier naturel inf rieur ou gal n Initialisation P est vident H r dit Soit n 1 un entier tel que P _1 12 NOMBRES PREMIERS Supposons que n admette deux d compositions distinctes en produit de facteurs premiers n p X P2 X X Dr 41 X Q2 X X qs Si p tait premier avec tous les q alors d apr s le deuxi me lemme p serait premier avec q X q2 X X qs mais c est impossible car p divise q X q2 X X qs On a donc montr par l absurde qu il existe un 1 tel que p n est pas premier avec qi Comm
11. entit de B zout Va b N Ju v Z ua vb pgcd a b D monstration Soit E ma nb N m n Z a E donc E donc E contient un plus petit lement qu on appelle d donc Ju b Z d ua vb Montrons que pgcd a b lt d pgcd a b divise toute combinaison lin aire de a et b donc il divise d donc pgcd a b lt d Montrons que d lt pgcd a b Soit a dq r la division euclidienne de a par d r lt d r a dq a ua vb q a 1 uq bvq qui est une combinaison lin aire coefficients entiers de a et b Si r n tait pas nul on aurait trouv un l ment de E plus petit que d donc r 0 donc d a On montrerait de m me que d b d a et d b donc d pgcd a b donc d lt pgcd G b On a montr que pgcd a b lt d et d lt pgcd a b donc d pgcd a b donc ua vb pgcd a b Remarque 5 ATTENTION Si ua vb g g n est pas forc ment le pgcd o b Contre exemple 1x1 1x1 2 mais 2 pgcd 1 1 oe FE A an ef 2x18 1 x30 6 Remarque 6 Il n y a pas unicit de u et v Exemple a 18 et b 30 pgcd 18 30 6 3 x 18 2 x 30 6 Exemple 5 D terminer deux entiers relatifs u et v tels que u x 99 v x 75 pgcd 99 75 On d termine le pgcd avec l algorithme d Euclide puis en l exploitant on exprime tous les restes en fonction de 99 et 75 PGCD 7 Th or me 12 Th or me de B zout Va b N pgcd o b
12. es coefficients frationnaires MATH mode FRAC CASIO pr c der leur nom de MAT pour les coefficients fractionnaires F lt gt D 2 EVOLUTION DE PROCESSUS 2 1 Cours D finition 10 Si les tats possibles d un processus sont num rot s de 1 n on peut les repr senter par une matrice ligne ou une matrice colonne de dimension n Le ki me coefficient repr sente la proportion d individus dans l tat k ou la probabilit qu un individu soit dans l tat k D finition 11 On appelle matrice de transition une matrice carr e n X n d finie ainsi Le coefficient la ligne i et la colonne j donne e la probabilit de transition de l tat ia l tat j dans le cas d tats modelis s par une matrice ligne e la probabilit de transition de l tat j l tat i dans le cas d tats modelis s par une matrice colonne Remarque 14 Si les tats sont modelis s par une matrice ligne la somme des coefficients d une ligne de la matrice de transition vaut 1 Si les tats sont modelis s par une matrice colonne la somme des coefficients d une colonne de la matrice de transition vaut 1 D finition 12 Lorsqu il s agit de probabilit s on parle de marche al atoire Dans ce cas la matrice de l tat apr s n transitions est appel e tat de la marche al atoire apr s n pas Th or me 18 Soit une marche al atoire de matrice de transition et de matrice de l tat apr s n pas Xn e VEN Xn41 Xn
13. et q Cij Aij D finition 9 Si est une matrice p x q et B une matrice q x r on d finit la matrice C x B comme q la matrice p x r telle que pour tout entier entre 1 et p et tout entier k entre 1 et r Cik D dz j 1 Remarque 12 Les seuls cas v ritablement au programme sont e p q r e p q et r 1 e p l et q r Exemple 15 p q r 3 k w 2200 7D iM Re LO OB 4 0 0 222 Exemple 16 pq 3 r 1 1 0 2 3 1 15 0 112 4 0 0 1 Exemple 17 p 1 q r 3 1 0 2 3 2 1 1 1 5 0 4 0 0 Th or me 17 Soit A B C des matrices carr es de m me taille Soit k e7 des r els 1 A B B A MATRICES ET VOLUTION DE PROCESSUS 15 2 A B C A B C 3 k k A KkA Kk A 4 k A B kA kB 5 amp k A 4 6 kA B A kB k A x B 7 AxB xC Ax BxC 8 xX B C AxB AXxC 9 A B xC AxC BxC 2 3 4 5 6 7 8 4 9 Remarque 13 En g n ral A x B B x A Notation 3 A x A A A x A x A A etc Exemple 18 Utilisation de la calculatrice noter ici votre mode d emploi 1 3 2 4 475 0 B 4 0 6 5 1 6 5 A 2B A x B On cr e d abord les matrices en entrant leurs coefficients TI mode matrice mode EDIT nb de lignes nb de colonnes CASIO RUNMAT mode matrice F3 gt MAT nb de lignes nb de colonnes On effectue les calculs en rappelant les matrices par leur nom TI s lectionner leur nom dans le mode matrice pour l
14. ial Xo de cette marche al atoire elle converge vers un tat stable unique X i tel que X MX eta b 1 2 MATRICES ET TUDES ASYMPTOTIQUES D monstration comportant des questions ne participant pas directement la d monstration mais int res santes Commencer par donner le graphe probabiliste associ Soit Xn Ge Pourquoi a t on an bn 1 D terminer tous les tats stables X el Comment peut on restreindre les limites envisageables Le faire D terminer une relation entre an l et a Soit la suite d finie par Un an aa Montrer que cette suite est une suite g om trique qui converge vers 0 MATRICES ET TUDES ASYMPTOTIQUES 23 En d duire que g et b sont convergentes et d terminer leurs limites V rifier que ces limites ne d pendent pas de X5
15. n on en d duirait que p divise un nombre dont la d composition en facteurs premiers ne contient pas p ce qui est impossible d apr s ce qu on vient de montrer Exemple 13 D terminer le nombre de diviseurs de 13000 NOMBRES PREMIERS 14 MATRICES ET VOLUTION DE PROCESSUS Chapitre D Matrices et volution de processus 1 MATRICES 1 1 Cours D finition 6 Soit p et q deux entiers naturels non nuls On appelle matrice p lignes et q colonnes un tableau de nombres r els p lignes et q colonnes Pour la matrice A ces nombres appel s coeficients de la matrice sont not s a o est le num ro de la ligne et 7 celui de la colonne Q11 e 12 1 Qpa Remarque 11 Si p q on parle de matrice carr e Si p 1 on parle de matrice ligne Si q 1 on parle de matrice colonne Exemple 14 Les coordonn es des points sont des matrices ligne Les coordonn es des vecteurs sont des matrices colonnes Th or me 16 Deux matrices sont gales ssi elles ont les m mes dimensions et leurs coefficients sont gaux D finition 7 Si A et B sont deux matrices p x q on d finit la matrice C A B comme la matrice p x q telle que pour tout entier entre 1 et p et tout entier j entre 1 et q Cij Qij bij D finition 8 Si A est une matrice p x q et un r el on d finit la matrice C AA comme la matrice p x q telle que pour tout entier entre 1 et p et tout entier j entre 1
16. ons cutifs est divisible par 24 Exemple 10 Arthur sait qu il a entre 300 et 400 jetons S il fait des tas de 17 jetons il lui en reste 9 S il fait des tas de 5 jetons il lui en reste 3 On cherche combien Arthur a de jetons 1 Ecrire un algorithme permettant de d terminer tous les nombres de jetons possibles que poss de Arthur L algorithme calculera le nombre de divisions euclidiennes qu il effectue Ne pas finasser l ordinateur est rapide n 9 17 n 3 5 o 2 a Trouver des relatifs u et v tels que 17u 5v 1 La question pos e se traduit par 1 2 b En d duire une solution no de S 2 c Quelle est la forme g n rale des solutions de S PGCD 3 Quel est le nombre de jetons d Arthur Exemple 11 R soudre dans Z l quation 22x 138y 102 E La calculatrice nous donne pgcd 22 138 Cela permet de simplifier quation E amp Cherchons une solution particuli re de cette quation Cette solution permet de supprimer le second membre de l quation Supposons que x y est une solution de E ne L 1 donc d apr s le th or me de Gauss donc Jk Z Exprimons x et y en fonction de 10 PGCD On a montr que si x y est solution de E alors Jk Z Z R ciproquement v rifions que tous les couples x y de cette forme sont solution d
17. ont m me reste pour la division euclidienne par n D monstration Soit les divisions euclidiennes de a et b par n a nq r et b ng r a b n q g r 7r 0O lt r lt n i donc 2 lt lt Supposons que a b n a b n donc a b est divisible par n or r r a b n q q donc r r est divisible par n or n lt r r lt n donc r 7r 0 R ciproquement supposons que r r a b n q q donc nja b donc a b n Th or me 5 Soit n N k N Soit a a r r Z tels que 1 1 a a r r jn 2 a a r 7r jn 3 axa rxr jn t Remarque 3 ATTENTION k k n wimplique pas a a n Contre exemple a 2 n 3 k 1 4 Remarque 4 D sormais on traduira tout en termes de congruence divisibilit division euclidienne et on appliquera le th or me pr c dent en le mimant correctement Exemple 3 D terminer le reste de la division euclidienne de 25 x 2 par 7 4 CONGRUENCES 3 2 Travailler son cours Exercice 2 Les mains dans le dos 1 Un billet de 10 a pour num ro U09884536547 En rempla ant la lettre par son rang dans l alphabet on obtient un nombre 12 ou 13 chiffres ce nombre doit avoir 8 comme reste de la division euclidienne par 9 Peut on affirmer que c est un faux 2 V rifier qu un de vos billets n est pas un faux 3
18. rifiant une relation de r currence du type Xn 1 AX B est convergente alors sa limite X v rifie X AX B D monstration MATRICES ET TUDES ASYMPTOTIQUES 21 Remarque 19 Si une suite est d finie par une relation de recurrence de ce type et si 16equation X AX B a une solution la suite n est pas forc ment convergente Contre exemple Xo G 4 5 Remarque 20 Si 16quation X AX B n a pas de solution la suite Xn ne peut pas converger Remarque 21 Si l quation X AX B a une infinit de solutions d autres conditions li es la limite permettent parfois de restreindre les limites envisageables 3 APPLICATION AUX MARCHES AL ATOIRES 3 1 Cours D finition 16 On dit qu une marche al atoire est convergente si la suite des tats est convergente D finition 17 Si la suite des tats v rifie une relation du type X 11 AX B une suite constante v rifiant X AX B est appel e tat stable de la marche al atoire Remarque 22 Une marche al atoire peut tre convergente ou divergente selon l tat initial Xo S il y a convergence ce ne peut tre que vers un tat stable Exemple 24 Etudier la convergence de la marche al atoire d finie par A G a B 9 Xo z Th or me 27 Soit p q 0 1 Soit la marche al atoire de matrice de transition M p 1 9 Quel que soit l tat init
19. trons que D a b C D b r Soit d D a b d gi et r a bq donc d D r d D a b donc d D b de Dr On a montr que D a b D b r donc pgcd a b pgcd b r DE DU done de D b n D r donc d 5 Exemple 4 D terminer le pgcd de 364 et 247 en utilisant l algorithme d Euclide 6 PGCD Th or me 7 Cet algorithme s arr te toujours et produit bien ce qu il pr tend D monstration sur un exemple Th or me 8 Les diviseurs communs de a et b sont les diviseurs de pgcd a b D monstration D apr s la d monstration pr c dent D a b est gal l ensemble des diviseurs du dernier reste non nul dans l algorithme d Eulide c a d l ensemble des diviseurs de pgcd a b Th or me 9 Soit a b 0 0 un couple d entiers naturels Soit k N pgcd ka kb k x pgcd a b D monstration sur un exemple On r crit l algorithme d Euclide en multipliant tout par k 2 TH OR ME DE B ZOUT 2 1 Cours D finition 4 Deux entiers naturels non nuls a et b sont premiers entre eux ssi pgcd a b 1 Th or me 10 et sont premiers entre eux a b pgcd a b pgcd a b D monstration pgcd a b pgcd pgcd a b cites P9Cd a Den pgcd a 6 xpgcd Di nan or pgcd a b 0 donc pgcd 1 a b pgcd a b pgcd a b Th or me 11 Id
Download Pdf Manuals
Related Search