UNIVERSITE d'ORLEANS SCL1 MA02 Departement de mathematiques

Publié par

Niveau: Supérieur, Licence, Bac+1
UNIVERSITE d'ORLEANS SCL1 MA02 Departement de mathematiques 2008-9 Arithmetique : Corrige Feuille 4 (Congruences ). Exercice 1. Calculons le reste de 78 divise par 6 i.e on cherche 0 ≤ x < 6 tel que 78 ? x [6]. Modulo 6, on a : 78 ? (72)4 ? (49)4 ? (6? 8 + 1)4 ? (1)4 ? 1. Le reste est donc 1. Calculons le reste de 315 divise par 11. Modulo 11, on a 315 ? (33)5 = (27)5 ? (2? 11 + 5)5 ? 55 ? (52)2 ? 5 ? (25)2 ? 5 ? (2? 11 + 3)2 ? 5 ? 32 ? 5 ? 9? 5 ? 45 ? 4? 11 + 1 ? 1. Le reste est donc 1. (On n'a pas besoin de calculer explicitement la puissance). Exercice 2. Montrons que 2x + 9y ? 0 [8] implique 10x ? 3y ? 0 [8]. On a (modulo 8) 2x ? ?9y donc 5? 2x ? ?5? 9y ? ?45y ? (?6? 8 + 3)y ? 3y. Ainsi 10x ? 3y et donc 10x? 3y ? 0 [8].

  • q1 pour q1 ?

  • divise

  • x? x0

  • divise q2

  • equation

  • derniere equation dans le language de la congruence


Publié le : mardi 29 mai 2012
Lecture(s) : 25
Tags :
Source : univ-orleans.fr
Nombre de pages : 4
Voir plus Voir moins
´ ´ UNIVERSITE d’ORLEANS De´partementdemathe´matiques
Arithm´etique:Corrige´Feuille4(Congruences).
SCL1 MA02 2008-9
8 Exercice 1.7idiv´sreseetedoncherchepar6i.e0eaClsnoluclx <6 tel que 8 7x6, on a :[6]. Modulo 8 24 44 4 7(7 )(49)(6×8 + 1)(1)1. Le reste est donc 1. 15 Calculonslerestede3divise´par11.Modulo11,ona 15 35 55 52 22 2 3= (27)(3 )(2×11 + 5)5(5 )×5(25)×5(2×11 + 3)×5 2 3×59×5454×11 + 11. Le reste est donc 1.(On n’a pas besoin de calculer explicitement la puissance). Exercice 2.Montrons que 2x+ 9y0 [8] implique 10x3y0 [8].On a (modulo 8) 2x≡ −9ydonc 5×2x≡ −5×9y≡ −45y(6×8 + 3)y3y. Ainsi10x3yet donc 10x3y0 [8]. Exercice 3.Trouvrons tous les entiersytels que 2yOn calcule5 [7].pgcd(2,7) = 1. Ainsi 2 et 7 sont premiers entre eux et que 7 = 3×2+1. Ainsi(1)×7+(3)×Ce2 = 1. qui donne (3)×2On pose1 [7].x0=3 alors 2×x0En multipliant par1 [7]. 5: 2×(5x0)ed5e2trapnoitre`ilucinsAi].[7lusoneiuy5 [7] esty0= 5x0=15. Pour trouver toutes les solutions de 2yulitnoaptrcilu`inretranchelaso[5o,]7ere y0ainsi 2(yy0)55(ise2d7vi`t:aviuae´uquieq.C7]0[yy02). Puisque et 7 sont premiers entre eux, on a par le lemme de Gauss, que 7 divise (yy0il) i.e. existekZtel queyy0= 7kconclut que. Ony=y0+ 7k=15 + 7kaveckZ. R´eciproquement,onve´riequetoutyde la formey=15 + 7kaveckZeire´v aussi 2yL’ensemble des solutions5 [7].See´ts`lagaS={−15 + 7k, kZ}. Exercice 4.Trouvons tous les entiersytels que 3yOn calcule12 [33].pgcd(3,33) = 3 1233 3.L´equation3yuqe´uavi21]33[t`ay[ ](Voir cours) i.e.yAinsi4 [11]. 3 33 y= 11k+ 4aveckZ. L’ensembledes solutionsS`lae´agetsS={11k+ 4, kZ}. Exercice 5.Trouvons tous les entiersxtels que ( x3 [11] x5 [7]. Oncommenceparchercherunesolutionparticuli`erex0t`emuuistys´.eOsnsoeu`darred lam´ethodeducoursa`lalettre.Onapgcd(11,7) = 1.Par Bezout, 1 = (2)×11 + (3)×7. Onposex0= (2)×5×11+3×(3)×7=(A47iba`lpnenettnoitele3carelte 5:voircours).Onve´riratoujoursexplicitementquex0enosulitnoaptrciuli`ere.tues En effet, on a modulo 11,x03×[(3)×7]3[12×11]33×(2)×113. Et modulo 7, on a : 1
2 x0(2)×5×115[1(3)×755×(3)×7]5. On a que ( xx03 [11] xx05 [7]. Ainsipardi´erence, ( xx00 [11] xx00 [7]. Ainsixx0Puisque 11 et 7 sont premiers entre eux alorsest multiple de 11 et 7. xx0est multiple de 11×`u.Do7=77x=x0+ 77k= 47+ 77kpour unkZ. Re´ciproquement,touslesxde la formex= 47+ 77kpour unkZsont solutions. L’ensemble des solutions estS={47 + 77k, kZ}. Exercice 6.a) Montrons que 223 est un nombre premier.Il suffit de voir si les nom-bres premiers3225 = 15 (i.e.,5,7,11,qtneeuacefemilv´Onierives22.31)3id non. Donc223 est premier. 1998 1998 b)Calculons1998modulo223.Onnecalcule´evidemmentpas1998explicite-p1 ment. Onutilise le corollaire de Fermat pour toutxN,x1 [p] pourppremier etxnon divisible parp. 222 Onende´duit19981 [223].On effectue la division euclidienne de 1998 par 222, 1998 2229 9 on a 1988 = 9×222. Ainsimodulo 223, on a 1998((1998) )(1)1. Exercice 7.Trouver tous les entiersxtels que ( x≡ −1 [8] x7 [13]. Exercice 8.On a 455 = 5a) Factorisons 455 en produit de nombres premiers.×91 = 5×7×13. n b) SoientaetnMontrons que l’on ades entiers naturels.a1 [455] si et seulement n nn sia1 [5],a1 [7] eta1 [13]. n nn Supposons quea1 [455] i.e.a1 est multiple de 455 alorsa1 est multiple n n de5,de7etde13dapr`esa).Re´ciproquement,supposonsa1 [5],a1 [7] et n nn a1 [13] i.e.aAlors1 est multiple de 5, de 7 et de 13.a1 = 5q1pourq1N. n Puisque 7 divisea1 i.e.5q1et que 5 et 7 sont premiers entre eux alors par le lemme n de Gauss, 7 diviseq1i.e.q1= 7q2avecq2N. Donca1 = 5×7×q2. Puisque13 n est premier avec 5×7 et que 13 divisea1 alors par le lemme de Gauss, 13 diviseq2 n n i.e.q2= 13q3avecq3N. Ainsia1 = 5×7×13q3= 455q3. Donca1 est bien n multiple de 455 i.e.a1 [455]. 12 c) Soitaun entier tel quepgcd(a,455) = 1.Montrons que l’on aaCeci1 [455]. 12 1212 este´quivalenta`montrerquea1 [5],a1 [7] eta1 [13] (avecn= 12).
3 Puisquepgcd(a,455) = 1 impliquepgcd(a,5) = 1,pgcd(a,7) = 1 etpgcd(a,13) = 1. 4 124 36 Par le corollaire de Fermat,a1 [5] donca(a)1 [5] eta1 [7] donc 12 62 12 a(a)puis1 [7].ar´esnelet.ulta31.][1dinoeCuq Exercice 9.Soientpun nombre premier etaun entier positif non multiple dep. k a) Montrons qu’il existe un plus petit entier positifktel quea1 [parp]D.esl´e p1` corollaire de Fermata1 [p]. L’ensemblede`Nerv´anita1 [p] n’est pas vide puisqu’il contientpelixnoicntsue1esneteC.ntseelbmetdevionedr´nomi k plus petit entierk1 tel quea1 [p]. SoitnN. Notonsrle reste de la division euclidienne denpark. n b) Montrons que l’on aa1 [p] si et seulement sinest multiple dek. Supposons n nk qr rk quea1 [p]. Avecn=qk+r, on obtienta(a)aa[p] cara1 [p]. r Ainsi 0r < kve´irea1 [p]. doncr= 0 sinon 1rserait plus petit quek( contradiction).
4 42 22 c) Soitp= 5 etaosne´ir4=V.equa4(16 )(15 + 1)11 [5]. k1 2 Cherchons le plus petit entierktel que 41 [5].On a 44 [5] et 415 + 11 [5] ainsikNotons que= 2.k <(p1) ici. 2 Exercice 10.a) SoitaZque. Montronsaoctsurgn,0a`4uo1dumo8.loe On aax[8] pour 0x <8. Onfait la liste des cas: 2 Siaalors0; [8]a0; [8]. 2 Siaalors1; [8]a1; [8]. 2 Sia2; [8]alorsa4; [8]. 2 Siaalors3; [8]a91; [8]. 2 Siaalors4; [8]a160; [8]. 2 Sia5; [8]alorsa2524 + 11; [8]. 2 Sia6; [8]alorsa3632 + 44; [8]. 2 Sia7; [8]alorsa4948 + 11; [8].
2 2 2 b) SoitnMontrons queun entier positif.a+b+c6= 8n1, pour tousa, b, cZ. 2 2 2 Oninterpre´tecettederni`eree´quationdanslelanguagedelacongruence:a+b+c 2 2 2 nestpascongru`a1 modulo 8 ou encorea+b+ctsecsapngrona8u`1 = 7 modulo 8.
2 Onconside`retouslescasposssibles(27cas)enconside´ranta1ua`o0gnurcoste 2 2 ou 4 modulo 8 etbongrestca0u`1ooumou4lodute8c0ou1ou4tsegnoca`ur modulo 8. 2 22 22 2 Par exemple,aa4u`gron,sectbe1a`urgncostetc`a1angruinsioctsea+b+c estcongru`a4+1+4=9i.e.a`1modulo8.(Lesautrescassontlaisse´sa`faire). Exercice 11.On teste les di-a) Factorisons 1729 en produit de nombres premiers. viseurs premiers41= 71729. 1729×13×19.
4 n b) SoientaetnMontrons que l’on ades entiers positifs.a1 [1729] si et seulement n nn sia1 [7],a1 [13] eta1 [19]. Lapreuveestanalogue`acelledelexo.8.Largumentprincipalestlefaitqueles nombres 7,13,19 sont des nombrers premiers. 1728 c) Soitaun entier positif tel quepgcd(a,an.1=)9271tronemD´oelquera1[1729].Lapreuveestanalogue`acelledelexo.8. Exercice 12.Trouvons tous les entiersxtels que ( 7x5 [19] 3x1 [11]. Solutions:Lesyst`emee´quivaut`a ( 3×7x3×5 [3×19] 7×3x7×1 [7×11]. i.e.( 21x15 [57] 21x7 [77]. On posey= 21xonetesr´dou ( y15 [57] y7 [77]. Onappliquelam´ethodeducours(voiraussilexercice7).Onapgcd(57,77) = 1 car par Bezout 1 = (20)×77 + (27)×.Uns57re`eucilraitoipnlotuy0= (20)×15×77 + (27)×7×gnoitulolare´ne´etiono`uo27(Attente)7L.sapnalec5175321=ysatisfait ( yy00 [57] yy00 [77]. qui´equivaut`a yy00 [57×77] 0 car57et77sontpremiersentreeux.Do`ulensembledesolutionsSpoury, 0 S={y= 12327 + 4389k, kZ}itulosedelbmesnelitdu´endne.OonsSpourx, S={x= 587 + 209k, kZ}(carx=y/21). 4
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.