[PDF] Exercices darithmétique

View - Download Exercices darithmétique

Previous PDF

Next PDF

Universit´e Paris 13 M1 : de l"arithm´etique `a la th´eorie des nombres

Exercices d"arithm´etique

Exercice 1. -Existe-t-il des couples(a,b)N2tels que : -ab(a+b)n"est pas divisible par7et -(a+b)7?a7?b7est divisible par77? Exercice 2. -Dans l"´emission Fort-Boyard, les candidats jouent au jeu suivant : sont dis- pos´es align´eesncraies et les deux joueurs en retirent chacun `a leur tour1,2ou3, le perdant ´etant celui qui retire la derni`ere craie. Trouver une strat´egie gagnante.

Exercice 3. -Montrer la formule de Legendre

v p(n!) = k1n pk=a1+a2p++akpk1) + (a2++akpk2) ++ (ak1+akp) +ak o`un=a0+a1p++akpkest l"´ecriture denen basep. D´eduire que la valuation2-adique du coefficient binomial(b a+b)est ´egale `a la somme+ k=0akbkoua=+ k=0ak2ketb=+ k=0bk2ksont les ´ecritures en base2deaetb; en particulier noter que pour0< k < n,(k n)est pair. Exercice 4. -( Un argument de descente infinie `a la Fermat)Soienta,b >0tels queab+ 1a2+b2; montrer que le quotient est un carr´e parfait. Exercice 5. -Soitun ensemble de2008entiers distincts strictement positifs dont tous les diviseurs premiers sont23. Montrer que l"on peut trouver4´el´ements distincts dedont le produit est la puissance quatri`eme d"un entier. Exercice 6. -Donner en fonction den, le pgcd(n3+n2+ 1,n2+ 2n?1). Exercice 7. -Donner en fonction den, le pgcd(n3+n2?6n+ 2,2n2+ 5n?3).

Exercice 8. -Montrer la relation

F n+m=Fn+1Fm+FnFm1 et d´eduiser-en queFnFm=Fnm. Exercice 9. -Variations sur le th´eor`eme de Bezout : (1) En utilisant l"algorithme d"Euclide, trouver les relations de Bezout entre650et66. (2) On suppose que l"on ne dispose que de pieces de valeursaetbenti`eres avec(a,b) = 1. (i) Quelles sommes peut-on payer si on nous rend la monnaie? (ii) Mˆeme question si on ne peut pas nous rendre la monnaie? (Indication : montrer que sim+n=ab?a?balors exactement une somme parmimetnest payable). (3) Etudier le cas de3pi`eces de valeur15,20et48en montrant que217est la plus grande somme que l"on ne peut pas payer. (4) G´en´eraliser la question pr´ec´edente en montrant quepoura,b,c >0premiers entre eux deux `a deux,2abc?ab?bc?acest le plus grand entier qui ne peut pas s"´ecrire sous la formexbc+yca+zabavecx,y,z0. 1

2(5) Montrer par r´ecurrence surnque sia1,,ansontnentiers strictement positifs premiers

entre eux deux `a deux alors a 1an n?1?n i=11 ai est le plus grand entier qui ne peut pas s"´ecrire sous la formeni=1xi j=iajavecxi0 pour touti= 1,,n.

Exercice 10. -Montrer que7divise3105+ 4105.

Exercice 11. -Montrer l"´equivalence3aet3b3a2+b2. Exercice 12. -Proposer `a vos amis dou´es en calcul mental le jeu suivant : multiplier par

13leur jour de naissance, multiplier par14leur mois de naissance, additionner ces deux

r´esultats pour former un nombrenqu"il vous communique. Comment retrouver les donn´ees cach´ees? Exercice 13. -Un nouveau jeu pour des amis coop´eratifs : choisir un nombrekentre1et

8, puis communiquer le r´esultatn= 10A?9ko`uAest l"ˆage du candidat. Expliquer comment

vous retrouvezA. Exercice 14. -Donner les morphismes de groupeZ/3Z?Z/4Zpuis ceux deZ/12Z? Z/15Z. Trouver une condition n´ecessaire et suffisante surmetnpour que tout morphisme

Z/nZ?Z/nZsoit nul.

Exercice 15. -Montrer l"´equivalence6a+b+c6a3+b3+c3. Exercice 16. -Montrer que429est inversible dansZ/700Zet donner son inverse. Exercice 17. -R´esoudre dansZles congruences suivantes :

1)3x4 mod 7;

2)9x12 mod 21;

3)103x612 mod 676.

Exercice 18. -Donner la congruence modulo17de(1035125)5642. Exercice 19. -Donner la congruence modulo18de1823242puis celle de2222321modulo 20.

Exercice 20. -Montrer quen7nmod 42.

3

1Essayons de factoriserP(x) = (x+ 1)7?x7?1 en regardant ses racines : on remarque

qu"outre 0 et 1, le nombre complexej=e2iπ/3est aussi racine carj+ 1 =?j2de sorte que P(x) est divisible parx(x+ 1)(x2+x+ 1) le quotient ´etant ´egal `ax2+x+ 1 et donc (a+b)7?a7?b7= 7ab(a+b)(a2+ab+b2)2. On est ainsi amen´e `a r´esoudrea2+ab+b20 mod 73qui s"´ecrit encore (a+b

2)2 ?3(b2)2mod 73

laquelle poss`ede des solutions si et seulement si le symbole de Legendre (3

73) = 1 ce que l"on

v´erifie ais´ement en utilisant la loi de r´eciprocit´e quadratique.

2Analysons les derni`eres positions : l"unique ultime position perdante est celle o`u le joueur

a devant lui une unique craie. Ainsi s"il reste entre 2 et 4 craies, la position est gagnante puisqu"il suffit de retirer toutes les craies sauf une. Formulons alors la strat´egie gagnante : une position est perdante (resp. gagnante) si le nombre de craies restantes est (resp. n"est pas) congrue `a 1modulo 4. La preuve de cette affirmation repose sur les points suivants : - si le nombre de craies n"est pas congru `a 1 modulo 4 alors le joueur peut, en enlevant

1,2 ou 3 craies, la ramener `a 1 modulo 4;

- en revanche dans le cas contraire, o`u le nombre de craies est congru `a 1 modulo 4, le joueur en retirant 1,2 ou 3 craies ram`ene la position `a un nombre de craies non congru `a 1 modulo 4. - S"il ne reste qu"une craie alors le joueur a perdu.

3Pour toutk >0, l"ensemble [1,n] contientn/pkmultiples depkde sorte qu"il y a exacte-

mentn/pk ? n/pk+1´el´ementsitels quevp(i) =kce qui donne le r´esultat.

En ce qui concerne la valuation 2-adique de (

b a+belle d´ecoule directement de la formule de

Legendre en remarquant que

a+b

2k ? a2k ? b2k

est non nulle si et seulement siak=bk= 1.

4On raisonne par l"absurde; on prend (a,b) tel que maxa,bsoit minimal aveca2+b2

ab+1=k qui n"est pas un carr´e parfait. Remarquons d´ej`a que sia=balorsa=b=k= 1 ne convient pas. Supposons donc 0< a < bet ´ecrivons l"´egalit´e pr´ec´edente sous la forme b

2?(ka)b+a2?k= 0

de sorte quebest une racine du polynˆomeX2?(ka)X+a2?k, lequel poss`ede une deuxi`eme racinebtelle queb+b=kaet doncbZ. Par ailleurs on a : -bb=a2?ket doncb= (a2?k)/b < a; -b>0 : en effet sib<0 alorsk= (a2+ (b)2)/(ab+ 1)<0 ce qui n"est pas et sib= 0 alorsk=a2ce qui n"est pas non plus.

En r´esum´e le couple (a,b) avec 0< b< aest plus petit que (a,b) v´erifie les mˆemes hypoth`eses

ce qui contredit la minimalit´e de (a,b).

5A tout ´el´ementnde, on associe bijectivement un vecteur (n1,,n9)Z9tel que

n= 2n13n223n9; il s"agit alors de d´emontrer que l"on peut trouver 4 vecteurs deZ9dont

la somme appartient `a 4Z9. Remarquons d´ej`a que d"apr`es le principe des tiroirs, ´etant donn´es

2

9+1 vecteurs deZ9, il en existe 2 dont la somme est dans 2Z9. L"id´ee est alors la suivante :

construire desak,bkdeux `a deux distincts pour 1k29+1 tels quesk=ak+bk2Z9de

4sorte que l"on pourra trouveri=javec (si/2) et (sj/2) de somme appartenant `aZ9. Pour

cela il suffit d"avoir au d´epart (2quotesdbs_dbs2.pdfusesText_2

[PDF] arithmétique dans z exo7

[PDF] exercice arithmétique mpsi corrigé

[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