[PDF] Feuille 5 : Arithmétique n(n + 1)(n + 2)(

View - Download Feuille 5 : Arithmétique

Previous PDF

Next PDF

Universit´eClaudeBernardLyon1UEFondam entauxdesMath´em atiquesI

Semestred'automne2016-2017

Feuille5:Arithm´eti que

Exercice1Montrerquepourtoutn2N:

1.n(n+1)( n+2)( n+3)e std ivisiblep ar24,

2.n(n+1)( n+2)( n+3)( n+4)e std ivisible par120.

Exercice2 D´eterminerlescouplesd'entiersnatu relsdepgc d35etppcm210. Exercice3D´eterminerlescouplesd'entiersnatu relsdepgcd 18etdesomme360.Demˆeme avecpgcd18 etprod uit6480.

Exercice4Calculerlepgcdde48et210,et de81et 237.Danschaque casexpr ime rl'id ent it´ede B´ezout .

Exercice5Calculerparl'algorithmed' Euclid elepgcdde18480et9828.End´eduireune ´ecriturede84 commecombinaison lin´eairede18480et9828. Exercice6Trouvertouteslessolu tionsdessyst`em essuivants dansZ 2 (a)58x+21y=1(b)14x+35y=21( c)637x+595y=29

Exercice7Notonsa=1 111111111etb=123456 789.

1.Cal culerlequotientetlere stedel adivisioneuclidienned eaparb.

2.Cal culerp=pgc d(a,b).

3.D´ eterminerdeuxentiersrelatifsuetvtelsqueau+bv=p.

Exercice9Combien15!admet-ilded ivi seursdansN?

Exercice10D´emontrerque,siaetbsontdesent ierspremi ersentreeux,ilenestd emˆemedesentiers a+betab. Exercice11Soienta,bdesentie rssup´erieursou´egaux`a1. Montrer: 1.(2 a 1)|(2 ab 1); 2.2 p

1pr emier)ppremier;

3.p gcd(2

a 1,2 b 1)=2 pgcd(a,b) 1. Exercice12Montrerquesinestunenti ernatur elsommededeuxcarr´e sd'entiersalorslere stedela divisioneuclidiennede npar4n' est jamais´egal`a3.

Exercice13D´emontrerquelenombre7

n +1estd ivisiblep ar8sinestimpair ;danslecasnpair,donner lerest edesadivisionpar8. Exercice14Trouverlerestedela divisi onpar13dunombre100 1000
Exercice15Trouvertouteslessolut ionsdusyst`emes uivantdansZ: n⌘13(m od19) n⌘6(m od12). 1 Exercice16SoitXl'ensembledesnombrespremiersde laforme4k+3aveck2N.

1.Mon trerqueXn'estpasvide.

2.Mon trerqueleproduitd enombresde laforme 4k+1e ste ncoredecet teforme.

3.On suppose queXestfinieton l'´ecrital orsX={p

1 ,...,p n

Soita=4p

1 p 2 ...p n

1.Mon trerparl'absurdeque aadmetundivis eurpre mierdelaforme4k+3.

4.Mon trerquececiestimpos sibleetd oncqueXestinfini.

Exercice17Soitn2N,n2.

1.Mon trerquen

2 ⌘1(m od8)sinestimpair.

2.Mon trerquen

2 ⌘0(m od8)oun 2 ⌘4(m od8)sinestpair.

3.Soi enta,b,ctroisentiersi mpairs.

i)D´ eterminerlerestemodulo8dea 2 +b 2 +c 2 etcelui de(a+b+c) 2 .End´eduirelerestemodulo

8de 2(ab+bc+ca).

ii)Existe- ilunentierm2Ntelquem 2 =ab+bc+ca?

Exercice18

Soita2Ntelquea

n +1s oit premier.M ontrerquenestdelafor men=2 k pourunent ier k2N.Qu epenserde laconjecture:2 2 n +1e stp remierpour toutentiern2N?

Exercice19

Soitpunnomb repremier.

1.Mon trerque

p i estdivisi bleparppourtouti2J1,p1K.

2.Mon trerparr´ecurencequ epourt outa2N

,l'entiera p aestdivis ibleparp.

Exercice20

1.Mon trerparr´ecurrenceq uepour toutn2Netk2N

ona: 2 2 n+k 1= 2 2 n 1 k1 Y i=0 2 2 n+i +1

2.On poseF

n =2 2 n +1.M ontr erquepourm6=n,F n etF m sontpremi ersentreeux.

3.E nd´edu irequ'ilyauneinfinit´ede nombrespremiers.

Exercice21Donnerlavaleuren basedix desnombressuivan ts:

1.(110101001)

2

2.(110101001)

3

3.(1367)

8

4.(1402)

5

Exercice22

Ecrirelesnombressui vants(donn ´esenbasedix)danslab asecibleindiqu´ee.

1.255e nbas edeux;

2.1907e nbas eseize ;

3.2016e nbas esept;

4.2000e nbas edeuxm ille.

2 Universit´eClaudeBernardLyon1UEFondam entauxdesMath´em atiquesI

Semestred'automne2016-2017

Feuille5:Arithm´eti que

Exercice1Montrerquepourtoutn2N:

1.n(n+1)( n+2)( n+3)e std ivisible par24,

2.n(n+1)( n+2)( n+3)( n+4)e std ivisible par120.

Solution

1.24= 2·3·4.De quatre nombrescons´ecuti fs,unestdivisible par2etunautrepar4,puisqueles

r´esidusmodulo4sont0,1,2et 3.Leurproduitestdoncd ivi siblepar8. Dem ˆem e,d etroisn omb res cons´ecutifs,unestdivisiblepartrois.C omme8et 3sontpremi ersentreeux,leproduitestd ivisib le par24.

2.120 =24·5.Les r´esid usmodulo5decinqnombrescon ´scutifssont0,1,2,3et 4.Il yenadon cunequi

estdivis ibleparcinq.Comme5et24sontprem iersen treeux,leprodu itdecinqnombr esc ons´ec uti fs estdivisi blepar120. Exercice2 D´eterminerlescouplesd'entiersnatu relsdepgc d35etppcm210.

Solution

Soientaetblesdeuxn ombres.Alorsa=35a

0 etb=35b 0 ,pgc d(a 0 ,b 0 )=1eta 0 b 0 210
35
=6=2·3.Alor son acom mesolutionpour( a 0 ,b 0 ):(1,6),(2,3),(3,2)et (6,1).Cequ idonnel essolutions (35,210),(70,105), (105,70)e t(210,35). Exercice3D´eterminerlescouplesd'entiersnatu relsdepgcd 18etdesomme360.Demˆeme avecpgcd18 etpro duit6480.

Solution

1.Soi entaetblesdeuxnom bres.Alorsa=18a

0 etb=18b 0 ,pgc d(a 0 ,b 0 )=1eta 0 +b 0 360
18 =20.I lfau t donc´ecri re20comesommededeuxentie rs premierse ntreeux.Ilsn epeuv entpasˆetredi visiblespar

2ou5, ceq uid onneles solutions( 1,19),(3,17),(7,13)et (9,11)pou r(a

0 ,b 0 )ou( b 0 ,a 0 ),soit( 18,342), (54,306),(126,234)et (162,198)pou r(a,b)ou( b,a).

2.Soi entaetblesdeuxn ombres.Alorsa=18a

0 etb=18 b 0 ,pgc d(a 0 ,b 0 )=1eta 0 b 0 =6480= 18 2

·4·5.

Alorsonacomme solu tion pour(a

0 ,b 0 )ou( b 0 ,a 0 ):(1,20)et (4,5),cequ idonnel essolutions (18,360), (72,90)pou r(a,b)ou( b,a).

Exercice4Calculerlepgcdde48et210,etd e81et237. Danschaquec asexpri mer l'ide nti t´edeB ´ezout.

Solution

1.On a210=48·4+18 ;48= 18·2+12 ;18= 12+6;12= 6·2.Ain sipgcd(210,48)=6.

Onremon te:6=1812=18 (4818·2)=18 ·348=( 21048·4)·348=210 ·348·13.

2.On a237=81·2+75 ;81= 75+6;75= 6·12+3 ;6= 3·2.Ain sipgcd(237,81)=3.

Onremon te:3=756·12=75 (8175)·12= 75·1381·12=( 23781·2)·1381·12=237 ·1381·38.

Exercice5Calculerparl'algorithmed' Euclid elepgcdde18480et9828.End´eduireune ´ecriturede84 commecombinaison lin´eairede18480et9828.

Solution

Ontrav ailleavecdesr´esidusdeval eurabsoluemini male.Ona18480 =9828·21176;9828=1176·8+420;

1176=420 ·384;420=84·5.D oncpgcd(18480,9828)=84. On rem onte:

84=420 ·31176=( 98281176·8)·31176=9828 ·31176·25=9828 ·3(9828·218480)·25=

18480·259828·47.

Exercice6 Trouvertouteslessolu tionsdessyst`em essuivants dansZ 2 (a)58x+21y=1(b)14 x+35y=21( c)637x+595y=29

Solution

1

1.On a58=21·35;21=5·4+1. Donc pgcd (58,21)=1 eti lya unesolu tion.On re mont e:

1=21 5·4=21 (21·358)·4=58 ·421·11.Les solution ssont(x,y)2{(4+21n,1158n):n2Z}.

2.On a35=7·5et 14=7·2.Ain sipgcd(35,14)=7 ;com me7|21il yaune solu tion .Endivisan tpar

7,le syst` emeest´equivalent`a2x+5y=3.Un esol utions ´evidenteest(4,1).Less olutions sontdonc

(x,y)2{(4+5 n,12n):n2Z}.

3.On a637=595+ 42;595 =42·14+7;42=7·6.Don cpgcd(637,595)=7 ;com me7-29il n'yap as

desolut ion.

Exercice7Notonsa=1111 111111etb=123456 789.

1.Cal culerlequotientetlere stedel adivisioneuclidienned eaparb.

2.Cal culerp=pgc d(a,b).

3.D´ eterminerdeuxentiersrelatifsuetvtelsqueau+bv=p.

Solution

1.10bb=1111 101.Donc1111111111 =123456789·9+10.

2.p=pgc d(1111111111,123456789)=pgcd( 123456789 ,10)= 1,pu isq ue123456789estdivisibleni

par2nip ar5.

3.On a1=10·12345679123456789=(1111111111 123456789·9)·12345679123456789

=1111 111111·12345679123456789·111111112.Onadonc u=12 345679etv=

111111112.

Solution

Ondiv isepar45:Lesyst`emees t´equ ival ent `a37 x+23y=1. Ona 37=23·29;23=9·2+5;9=5·21. Doncpgcd(37 ,23)=1 eti lya unesolu tion.On re mont e:

1=5·29=( 239·2)·29=23 ·29·5=23 ·2(23·237)·5= 37·523·8.Les soluti onssont

donc(x,y)2{(5+23n,837n):n2Z}.

Exercice9Combien15!admet-ildedi vi seursdansN?

Solution

Ond´ec ompose15!enfacteurspremiers. Onc onstateai s´ementquesesfacteurs serontexactement2,3,5,7,11,13.

De1`a15, ily a7nombr esp airs.D onc2 appar aˆı taumoins7fois.Ilyaaus si3multiplesde2 2 =4.D onc

2app araˆıt3foisdeplus(aumoin s10f ois).Ilyaau ssi1mu ltiplede2

3 =8.D onc2 apparaˆıt1f oisd eplus

(aumoins 11fois).Iln'y apas demultiplesdep lusgrand espuissanc es de2.Donc 2apparaˆ ıtexactement

11foi s.Onfaitdemˆ emeave c3:ilya5m ultip lesde3,1seulmult iplede3

2 =9,e tpas depuis sancepl us

grande,donc3apparaˆı texacteme nt6 fois.Avecceraisonnement, 5apparaˆıtexactement3fois,7appar aˆı t

exactement2fois,11et13apparaˆıss ent exactement1foi sc hacun.

Donc15!=2

11 ·3 6 ·5 3 ·7 2 ·11·13.Ain si,ilya12·7·4·3·2·2pos sibilit´espourlesdiviseurspositifs.On end´ed uitque15!a4032diviseurspos itifs. Exercice10D´emontrerque,siaetbsontdesent ierspremi ersentreeux,ilenestd emˆemedesentiers a+betab.

Solution

D'abord,onremarqueque siaetbsontpremie rsentreeux,aussia 2 etb 2 lesont . Soitdundivi seurcommundeabetdea+b.Alor sddivisea(a+b)ab=a 2 .Demˆemeddiviseb 2 .D' apr`es laremar quepr´ec´edente,lese ntiersa 2 etb 2 sontpremi ersentreeux.Ainsid=±1,ce quicon clut. Exercice11Soienta,bdesentie rssup´erieursou´egaux`a 1.Montrer: 1.(2 a 1)|(2 ab 1); 2.2 p

1premier)ppremier;

3.pgc d(2

a 1,2 b 1)=2 pgcd(a,b) 1.

Solution

1.(2 ab

1)= (2

a 1)(2 aba +2 ab2a +...+2 a +1). 2

2.Si pn'estpaspremier ,alorsp=abavecaetbdeuxentiers strictementsup´erieu rs`a1.Parlepoint

1,ond ´ed uitque(2

p

1)n' estpaspremier.

3.D' apr`es1.,2

pgcd(a,b)

1|pgcd(2

a 1,2 b

1).D'aut repart,ilexisteu,v2N

designe sdi

´erents

telsqueau+bv=p gcd(a,b).Onsu pposesan spertedeg´en´erali t´equeu<01)|pgcd(2 au 1,2 bv

1).Orp gcd(2

au 1,2 bv

1)=p gcd( 2

au 1,2 bv 2 au pgcd(2 au 1,2 au (2 bv+au

1))=pgcd (2

au 1,2 pgcd(a,b)

1)car 2

au

1es timpair.D onc

pgcd(2 a 1,2 b 1)|2 pgcd(a,b)

1.D' o`uler´esultat.

Exercice12Montrerquesinestunenti ernatur elsommededeuxcarr´e sd'entiersalorslere stedela divisioneuclidiennede npar4n' est jamais´egal`a3.

Solution

Lesr´es idusmodulo4descarr´esdes nombres0,1,2,3son t0et1.

Enuti lisantlapropri´et´e

a⌘b(modn))a k ⌘b k (modn),k2N,(1) ond´ eduitquepourtoutnentiernaturel,n 2 ⌘0ou1 (mo d4) .Ceciimpliqu equele r´esidudetou tnombre naturelquiestsommed edeuxcarr´ eesd'ent iersnepeutjam aisˆet re´egale`a3.

Exercice13D´emontrerquelenombre7

n +1estd ivisiblep ar8sinestimpair; danslecasnpair,donner lerest edesadivisionpar 8.

Solution

7⌘1(m od8))7

n +1⌘(1) n +1( mod 8)⌘

0(m od8)sinestimpair;

2(m od8)sinestpair.

Exercice14Trouverlerestedelad ivisi onpar13dunombre100 1000

Solution

D'abordonnoteque100⌘9(m od13).Onend´ed uitque 100 1000
⌘9 1000
(mod13). Comme13estprem ier et9n'est pasdivisiblepar13,lepeti tth´eor eme deFermatimpliqu eque 9 12 ⌘1(m od13).

Comme1000⌘4(m od12),onobtient

9 1000
⌘9 4 ⌘(4) 4 ⌘(16) 2 ⌘3 2 ⌘9(m od13). Exercice15Trouvertouteslessolu tionsdusyst`eme suivantdans Z: n⌘13(m od19) n⌘6(m od12).

Solution

Unesolut ionparticuli`ere´ev identedusyst`emeestn=6.Com me12et19sontpre mie rsent ree ux,l'ense mble

dessoluti onsestdonn´epar{6+228 k|k2Z}. Exercice16SoitXl'ensembledesnombrespremiersde laforme4k+3aveck2N.

1.Mon trerqueXn'estpasvide.

2.Mon trerqueleproduitd enombresde laforme 4k+1e ste ncoredecet teforme.

3.On suppose queXestfinieton l'´ecrital orsX={p

1 ,...,pquotesdbs_dbs47.pdfusesText_47

[PDF] Montrer que pour tout entier c : =1

[PDF] montrer que q est dénombrable

[PDF] montrer que racine de 3 est irrationnel

[PDF] montrer que racine de n est irrationnel

[PDF] montrer que se sont des rationnels

[PDF] montrer que si x appartient ? l'intervalle

[PDF] montrer que x appartient ? un intervalle

[PDF] montrer que xn 1 axn

[PDF] Montrer que y=

[PDF] MONTRER QUELQUE CHOSE SANS LE MONTRER POUR PEUT ÊTRE MONTRER TOUT AUTRE CHOSE

[PDF] Montrer registre tragique

[PDF] Montrer si le nombre A est un entier ou pas

[PDF] montrer une inégalité avec valeurs absolues

[PDF] montrer une relation d'ordre

[PDF] montrer verbe