Transcription of Arithmétique dans Z - Exo7
1 Exo7 Arithm tique dansZ1 Divisibilit , division euclidienneExercice 1 Sachant que l on a 96842=256 375+842, d terminer, sans faire la division , le reste de la division du nombre96842 par chacun des nombres 256 et o [000251]Exercice 2 Montrer que n N:n(n+1)(n+2)(n+3)est divisible par 24,n(n+1)(n+2)(n+3)(n+4)est divisible par o [000257]Exercice 3 Montrer que sinest un entier naturel somme de deux carr s d entiers alors le reste de la division euclidiennedenpar 4 n est jamais gal o [000267]Exercice 4D montrer que le nombre 7n+1 est divisible par 8 sinest impair ; dans le casnpair, donner le reste de sadivision par o [000254]Exercice 5 Trouver le reste de la division par 13 du nombre o [000250]Exercice 61.
2 Montrer que le reste de la division euclidienne par 8 du carr de tout nombre impair est Montrer de m me que tout nombre pair v rifiex2=0(mod 8)oux2=4(mod 8).3. Soienta,b,ctrois entiers impairs. D terminer le reste modulo 8 dea2+b2+c2et celui de 2(ab+bc+ca).4. En d duire que ces deux nombres ne sont pas des carr s puis queab+bc+canon o [000285]12 pgcd, ppcm, algorithme d EuclideExercice 7 Calculer le pgcd des nombres suivants :1. 126, 390, 720, 180, 606, o [000290]Exercice 8D terminer les couples d entiers naturels de pgcd 18 et de somme 360.
3 De m me avec pgcd 18 et produit o [000292]Exercice 9 Calculer par l algorithme d Euclide : pgcd(18480,9828). En d duire une criture de 84 comme combinaisonlin aire de 18480 et o [000296]Exercice 10 Notonsa=1 111 111 111 etb=123 456 Calculer le quotient et le reste de la division euclidienne Calculerp=pgcd(a,b).3. D terminer deux entiers relatifsuetvtels queau+bv= o [000303]Exercice 11R soudre dansZ: 1665x+1035y= o [000305]3 Nombres premiers, nombres premiers entre euxExercice 12 Combien 15! admet-il de diviseurs ?IndicationHCorrectionHVid o [000249]Exercice 13D montrer que, siaetbsont des entiers premiers entre eux, il en est de m me des entiersa+ o [000337]Exercice 14 Soienta,bdes entiers sup rieurs ou gaux 1.
4 Montrer :1.(2a 1)|(2ab 1);2. 2p 1 premier ppremier ;3. pgcd(2a 1,2b 1) =2pgcd(a,b) o [000336]Exercice 152 Soita Ntel quean+1 soit premier, montrer que k N,n= penser de la conjecture : n N,22n+1est premier ?IndicationHCorrectionHVid o [000349]Exercice 16 Soitpun nombre Montrer que i N,0<i<pon a :Cipest divisible Montrer par r curence que : ppremier, a N ,on aap aest divisible o [000339]Exercice 171. Montrer par r currence que n N, k>1 on a :22n+k 1=(22n 1) k 1 i=0(22n+i+1).2. On poseFn=22n+1. Montrer que pourm6=n,FnetFmsont premiers entre En d duire qu il y a une infinit de nombres o [000341]Exercice 18 SoitXl ensemble des nombres premiers de la forme 4k+3 aveck Montrer queXest non Montrer que le produit de nombres de la forme 4k+1 est encore de cette On suppose queXest fini et on l crit alorsX={p1.}
5 ,pn}.Soita= 1. Montrer par l absurde queaadmet un diviseur premier de la forme 4k+ Montrer que ceci est impossible et donc queXest o [000348]3 Indication pour l exercice 1 NAttention le reste d une division euclidienne est plus petit que le quotient !Indication pour l exercice 4 NUtiliser les modulos (ici modulo 8), un entier est divisible par 8 si et seulement si il est quivalent 0 modulo8. Ici vous pouvez commencer par calculer 7n(mod 8).Indication pour l exercice 5 NIl faut travailler modulo 13, tout d abord r duire 100 modulo 13.
6 Se souvenir que sia b(mod 13)alorsak bk(mod 13). Enfin calculer ce que cela donne pour les exposantsk=1,2,3,..en essayant de trouverune r gle g n pour l exercice 6N1. criren=2p+ criren=2pet discuter selon quepest pair ou Utiliser la premi re Par l absurde supposer que cela s crive comme un carr , par exemplea2+b2+c2=n2puis discuterselon quenest pair ou pour l exercice 11 NCommencer par simplifier l quation ! Ensuite trouver une solution particuli re(x0,y0) l aide de l algorithmed Euclide par exemple. Ensuite trouver un expression pour une solution g n pour l exercice 12 NIl ne faut surtout pas chercher calculer 15!
7 =1 2 3 4 15, mais profiter du fait qu il est d j presque factoris .Indication pour l exercice 13 NRaisonner par l absurde et utiliser le lemme de pour l exercice 14 NPour 1. utiliser l galit xb 1= (x 1)(xb 1+ +x+1).Pour 2. raisonner par contraposition et utiliser la question question 3. est difficile ! Supposera>b. Commencer par montrer que pgcd(2a 1,2b 1) =pgcd(2a 2b,2b 1) =pgcd(2a b 1,2b 1). Cela vour permettra de comparer l agorithme d Euclide pour le calcul depgcd(a,b)avec l algorithme d Euclide pour le calcul de pgcd(2a 1,2b 1).
8 Indication pour l exercice 15 NRaisonner par contraposition (ou par l absurde) : supposer quenn est pas de la forme 2k, alorsnadmet unfacteur irr ductiblep>2. Utiliser aussixp+1= (x+1)(1 x+x2 x3+..+xp 1)avecxbien pour l exercice 16N1. crireCip=p(p 1)(p 2)..(p (i+1))i!4et utiliser le lemme de Gauss ou le lemme d Raisonner avec les modulos, c est- -dire prouverap a(modp).Indication pour l exercice 17N1. Il faut tre tr s soigneux :nest fix une fois pour toute, la r currence se fait surk> Utiliser la question pr c dente avecm=n+ Par l absurde, supposer qu il y a seulementNnombres premiers, consid rerN+1 nombres du le principe du tiroir :si vous avez N+1chaussettes rang es dans N tiroirs alors il existe(au moins) un tiroir contenant (plus de) deux de l exercice 1 NLa seule chose voir est que pour une division euclidienne le reste doit tre plus petit que le quotient.
9 Donc lesdivisions euclidiennes s crivent : 96842=256 378+74 et 96842=258 375+ de l exercice 2 NIl suffit de constater que pour 4 nombres cons cutifs il y a n cessairement : un multiple de 2, un multiplede 3, un multiple de 4 (distinct du mutliple de 2). Donc le produit de 4 nombres cons cutifs est divisible par2 3 4= de l exercice 3 NEcriren=p2+q2et tudier le reste de la division euclidienne denpar 4 en distinguant les diff rents cas deparit de l exercice 4 NRaisonnons modulo 8 :7 1(mod 8).Donc7n+1 ( 1)n+1(mod 8).Le reste de la division euclidienne de 7n+1 par 8 est donc( 1)n+1 donc Sinest impair alors 7n+1 estdivisible par 8.
10 Et sinest pair 7n+1 n est pas divisible par de l exercice 5 NIl sagit de calculer 1001000modulo 13. Tout d abord 100 9(mod 13)donc 1001000 91000(mod 13). Or92 81 3(mod 13), 93 1(mod 13), Or 94 9(mod 13), 95 3(mod 13). Donc 1001000 91000 +1 (93) 9(mod 13).Correction de l exercice 6N1. Soitnun nombre impair, alors il s critn=2p+1 avecp N. Maintenantn2= (2p+1)2=4p2+4p+1=4p(p+1)+1. Doncn2 1(mod 8).2. Sinest pair alors il existep Ntel quen=2p. Etn2=4p2. Sipest pair alorsp2est pair et doncn2=4p2est divisible par 8, doncn2 0(mod 8).
