[PDF] Quelques exercices originaux darithmétique.

View - Download Quelques exercices originaux darithmétique.

Previous PDF

Next PDF

Quelques exercices originaux d"arithmétique.

G.Huvent

26 juillet 2004

Pour tous les exercices, on suppose disposer d"une calculatrice réalisant la recherche du pgcd, des couples de

Bézout et donnant la factorisation en nombres premiers d"unentier.

1Avec la calculette

Exercice 1 (Olympiades Hong-Kong 1999)

Soitaun nombre de trois chiffres. Le nombre de6chiffres obtenu en plaçant derrière504les trois chiffres de

aest divisible par7,9et11.Trouvera Solution.On sait que504000 +aest divisible par7,9et11.Puisque7et9divise504 = 23327,et que

7?9 = 1,on peut affirmer que7×9 = 63divisea.

Avec la calculette, on examine les restes des nombres de la forme504000 + 63koùkest compris entre0et15

(car63×16 = 1008et63×15 = 945) On constate quek= 8est la seule valeur possible. En conclusion a= 63×8 = 504

2Nombres premiers

Exercice 2 (Olympiades Hong-Kong 1998)

Soitcun nombre premier tel que11c+ 1soit le carré d"un entier. Déterminerc. 1

G.Huvent-Irem de Lille2

Solution.On suppose que11c+1 =a

2??11c= (a-1)(a+ 1). Puisque11est premier on peut affirmer

que11divisea-1ou bien11divisea+ 1.

1er cas :Si11divisea-1alorsa= 1 + 11koùk?N. Mais alors

11c= (a-1)(a+ 1) =?11c= 11k(2 + 11k)

=?c=k(2 + 11k) On en déduit quekdivisec,puisquecest premier on ak= 1ouk=c. Sik= 1 =?c= 13qui convient (11×13 + 1 = 144 = 12 2)

Sik=calorsc=c(2 + 11c) =?2 + 11c= 1impossible

2ième cas :Si11divisea+ 1,on obtient alors

11c= (a-1)(a+ 1) =?c=k(11k-2)

Sik= 1alorsc= 9qui n"est pas premier ( pourtant11×9 + 1 = 100 = 10 2)

Sik=calors1 = 11c-2impossible.

La seule solution est donc

c= 13

Exercice 3 (Olympiades Hong-Kong 1998)

Le nombre191peut s"écrire comme différence des carrés deaetb.Quelle est la valeur maximale poura?

Solution.On écrit191 =a2-b2= (a-b)(a+b). Puisque191est premier, on a

1er cas :191divisea-b=?b=a-191koùk?Z. On remplace pour obtenir

191 = 191k(2a-191k) =?k(2a-191k) = 1

on en déduit quekdivise1donck= 1ouk=-1. Sik= 1on obtient2a= 192 =?a= 96. Sik=-1,on obtienta=-95.

2ième cas :191divisea+b=?b= 191k-a,oùk?Z. On obtient alors

1 =k(2a-191k)

on retrouve les mêmes solutions ( ce qui est normal car si(a,b)est solution alors(a,-b)aussi. On se ramène

au cas précédent en remplaçantbpar-b)

Conclusion

a= 96

Exercice 4 (Olympiades Hong-Kong 1999)

Trouver le plus grand entier naturelntel que les restes de la division euclidienne de81849,106392et124374

soient égaux.

G.Huvent-Irem de Lille3

Solution.Les conditions s"écrivent

81849 =n×q

1+r(1)

106392 =n×q

2+r(2)

124374 =n×q

3+r(3)

On combine ces équations

(2)-(1) : 24543 =n(q 2-q1) (3)-(1) : 42525 =n(q 3-q1) (3)-(2) : 17982 =n(q 3-q2) Soitpun facteur premier denetαson exposant dans la décomposition den. On sait quep

αdivisendonc

aussi24543,42525et17982. Il divise donc également24543?42525 = 3

5(17982 = 2×35×37). Ainsin= 3p

81849 = 336×3

5+ 201

106392 = 437×3

5+ 201

124374 = 511×3

5+ 201

3Algorithme d"Euclide, pgcd, ppcm

Exercice 5 (Une formule pour calculer le pgcd)

Soientaetbdeux entiers positifs, montrer que

a?b=a+b-ab+ 2 b-1? k=1 E? kab? Cette formule a été trouvée par Marcelo Polezzi en 1997. Solution.Posonsd=a?b, a=da?etb=db?, alorsa?,b?sont des entiers positifs premiers entre eux.

Lorsquekdécrit{0,···,m-1}, ka

b=ka b?est un entier si et seulement sib?divisek. Ceci se produit exactement E?b-1 b? =E? d-1 b? =d-1fois. Or E ka b? +E? a-kab? ?a-1sika b/?N asika b?N ainsi b-1? k=1 E? ka b? +E? a-kab?? = (a-1)(b-1) + (d-1) =ab-a-b-d

G.Huvent-Irem de Lille4

Pour conclure, on a

2 b-1? k=1 E? kab? b-1? k=1 E? kab? b-1? k=1 E? (b-k)ab? b-1? k=1 E? kab? b-1? k=1 E? a-kab? =ab-a-b-d d"où le résultat.

Exercice 6

Montrer que les fractions12n+ 1

30n+ 2et21n+ 414n+ 3

sont irréductibles Solution.On s"inspire d"Euclide. Soita= 30n+ 2etb= 12n+ 1. Alors a?b= (a-2b)?b = 6n?b = 6n?(b-2×6n) = 6n?1 = 1 de même (21n+ 4)?(14n+ 3) = (7n+ 1)?(14n+ 3) = (7n+ 1)?1 = 1

4Reste des divisions

Exercice 7

On divise2003parn, le reste est égal à8.On divise alors3002parn, le reste obtenu est27. Que vautn?

Solution.On a?2003 =an+ 8

3002 =bn+ 27???1995 =an

2975 =bn

Ainsindivise1995et2975donc divise aussi1995?2975 = 35. Comme les restes doivent être inférieurs àn,

on en déduit quen≥28et donc quen= 35.

G.Huvent-Irem de Lille5

Exercice 8 (Olympiades Hong-Kong 2001)

L"entierna6chiffres et s"écritn=x1527y. On sait quenest un multiple de4et que si on le divise par11,

le reste est égal à5.Trouvern. Solution.On an= 100000x+ 15270 +y. On regarde modulo4,on obtient alors n= 2 +y(4)

On regarde alors modulo11,on obtient

n= 10x+ 2 +y= 5 (11)

Poury= 2il vient

10x-1 = 0 (11)

multipliant par10,ce qui donne100x= 10 (11) =?x= 10 (11)car100 = 1 (11).On a utilisé le fait que10

est inversible dans(Z/11Z)

Poury= 4il vient

10x+ 3 = 0 (11)

100x= 80 = 3 (11) =?x= 3 (11))

En conclusion

n= 315276

5Bézout

Exercice 9

nest un entier à6chiffres tel que lorsque l"on échange les trois premiers chiffres avec les trois derniers, le

résultat obtenu est6n+ 21.Trouvern.

G.Huvent-Irem de Lille6

Solution.Ecrivonsn= 1000A+BavecAetBayant3chiffres. Par hypothèse,

1000B+A= 6(1000A+B) +C??994B-5999A=C

Puisque(994,5999) = 7,on doit résoudre142B-857A= 3.

On cherche par division euclidienne un couple de Bézout pour(142,857)et l"on trouve57×857-344×142 = 1.

On a alors142(B+ 3×344)-857(A-3×57) = 0doncB=-1032 + 857ketA= 142k-171. On sait que AetBont trois chiffres, on trouve alorsk= 2comme unique solution etn= 113682

Exercice 10

L"entierna4chiffres et s"écritn=a4b4,si on échangeaetbon obtient l"entierp. Sachant que le reste de la division depparnest égal à2,trouvern.

Solution.On an= 1000a+ 10b+ 404,

On sait qu"il existeqtel quep=nq+ 2

q×n+ 2-b4a4 =q×(1000a+ 10b+ 404) + 2-1000b+ 10a+ 404 = 10(100q-1)a+ 10(q-100)b+ 2(202q-201) = 0 Il faut donc que10divise2(202q-201),i.e.5divise202q-201. Modulo5,on a202c-201 = 2q-1 (5),c

est compris entre1et9,2×1-1 = 1,2×2-1 = 3,2×3-1 = 5,2×4-1 = 7,2×5-1 = 9,2×6-1 = 11,

2×7-1 = 13,2×8-1 = 17et enfin2×9-1 = 17. La seule possibilité estq= 3 (on peut aussi écrire que

2q-1 = 5k??2q-5k= 1et se ramener à Bézout)

On obtient avecq= 3,

2990a-970b=-810??97b-299a= 81

On résout par Euclide

a= 2 + 97k,b= 7 + 299k

La seule solution est alors

n= 2474

Exercice 11

Demandez à un élève de multiplier le jour et le mois de sa date d"anniversaire par31et12respectivement puis

d"ajouter les deux produits. Il vous donne le résultat et, ohmiracle, vous lui donnez sa date d"anniversaire.

Expliquez et donnez ma date d"anniversaire si le résultat que j"ai trouvé est308. Solution.Il s"agit de résoudre31j+ 12m=xoùxest donné. Puisque31?12 = 1,avec Bézout, on a

7×31-18×12 = 1

G.Huvent-Irem de Lille7

On a alors

(7x)×31-(18x)×12 =x

Par soustraction

31×(j-7x) + 12×(m+ 18x) = 0

31?12 = 1

donc(m+ 18x) = 31ket(j-7x) =-12k m= 31k-18x j= 7x-12k La donnée est "l"entierxcompris entre31 + 12 = 43et31

2+ 122= 1105, les inconnues sontmetjtels que

Mais12 + 18x

31-1 + 18x31=1131<1

Il n"existe donc qu"une seule valeur dek, qui est1 + 18x

31si1 + 18x31?NetE?1 + 18x31?

+ 1sinon.

En fait, puisquex= 12m+ 31j,1 + 18x

31= 18j+216m+ 131,c"est un entier si et seulement si216m+ 1est

divisible par31.Avec216 = 6×31 + 30,on a1 + 18x

31?Nsi et seulement si30m+ 131?N. , ce qui n"est

possible que pourm= 1.

Par exemple avecx= 308, k=E?1 + 18×308

31?
+1 =E?554531? +1 = 179, m= 31×179-18×308 = 5et j= 7×308-12×179 = 8. Remarque :Il y a plus simple, en effetx= 12m(31)et pourm= 1,...,12,les 12 restes sont deux à deuxquotesdbs_dbs23.pdfusesText_29

[PDF] algebre 2 structures polynômes et fractions rationnelles

[PDF] cours arithmétique

[PDF] arithmétique dans z cours mpsi

[PDF] suite arithmétique

[PDF] exercice code barre terminale s

[PDF] exercices d arithmétique corrigés

[PDF] arithmétique exercices corrigés pdf

[PDF] exo7 arithmétique

[PDF] rencontre arles 2017

[PDF] programme arles 2017

[PDF] luma arles

[PDF] forum d'arles

[PDF] arles monuments romains

[PDF] arelate

[PDF] qui a fondé arles