[PDF] exercices-aritmetiques-corrigespdf
Exercices d'arithmétiques corrigés Exercice N°1 : 1-Etablir que pour n est un entier naturel premier différent de 1 posons d= pgcd (ab) 1-a-on a :
[PDF] Arithmétique Pascal Lainé - Licence de mathématiques Lyon 1
8 La puissance quatrième d'un entier non multiple de 5 est toujours congrue à 1 modulo 5 Allez à : Correction exercice 8 : Exercice 9 : Soit ? ? un
[PDF] Exercices corrigés darithmétique
Diviseurs –Division euclidienne : Exercice 1 : 1) Démontrer que a b si et seulement si pour tout k de ? a (b?ka)
[PDF] Arithmétique dans Z - Exo7 - Exercices de mathématiques
de n par 4 n'est jamais égal à 3 Correction ? Vidéo ? [000267] Exercice 4 Démontrer que le nombre 7n +1 est divisible par 8 si n est impair; dans le
[PDF] Exercices darithmétique - mathuniv-paris13fr
Exercice 3 — Montrer la formule de Legendre vp(n!) = ? k?1 (1) En utilisant l'algorithme d'Euclide trouver les relations de Bezout entre 650 et 66
[PDF] Arithmétique - Xiffr
Montrer que le pgcd de 2n + 4 et 3n + 3 ne peut être que 1 2 3 ou 6 Exercice 9 [ 01199 ] [Correction] Soient d m ? N Donner une condition nécessaire
[PDF] TD darithmétique
Exercice 11 (1) Démontrer que le nombre 7n + 1 est divisible par 8 si n est impair (2) Dans le cas où n est pair donner le reste de la division de 7n + 1 par
[PDF] Arithmétique exercices - Free
L'ensemble des diviseurs de 6 est D = {?6 ; ?3 ; ?2 ; ?1 ; 1 ; 2 ; 3 ; 6} Le but de l'exercice est de montrer qu'il existe un entier naturel n dont
[PDF] arithmetique-dans-z-cours-et-exercices-corrigespdf - AlloSchool
10 sept 2019 · et n? et 12 1 a n+ et 2 3 a n - + Montrer que 19 a 3) d? -3 ;-1 ;3 Exercice 06 : Quelles sont les valeurs de l'entier relatif n
[PDF] Arithmétique exercices - JoseOuinfr
Montrer que pour tout entier n premier avec p np?1 – 1 est divisible par p 2 Bézout 2-a : Bezout-1 1 En utilisant l'algorithme d'Euclide déterminer le
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. 12(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 par13leur 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 nombrekentre1et8, 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 morphismeZ/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.
31Essayons 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+b2)2 ?3(b2)2mod 73
laquelle poss`ede des solutions si et seulement si le symbole de Legendre (373) = 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 enlevant1,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 deLegendre en remarquant que
a+b2k ? 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 b2?(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 deZ9dontla somme appartient `a 4Z9. Remarquons d´ej`a que d"apr`es le principe des tiroirs, ´etant donn´es
29+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+bk2Z9de4sorte que l"on pourra trouveri=javec (si/2) et (sj/2) de somme appartenant `aZ9. Pour
cela il suffit d"avoir au d´epart (29+1)+2.29= 1537<2008 ´el´ements distincts : on commence
par prendrea1+b12Z9, puis ainsi de suite. S"il existei=jtels quesi=sjc"est gagn´e, sinon on r´eapplique ce qui pr´ec`ede `a l"ensemble de 29+ 1 ´el´ements distincts constitu´es des
s i/2.6Le but est de faire des combinaisons pour faire descendre le degr´e; concr`etement appelons
δ(n) ce pgcd. On an3+n2+ 1 = (n2+ 2n?1)(n?1)?(n+ 1) de sorte queδ(n) = (n2+2n?1,n+1). De mˆemen2+2n?1 = (n+1)2?2 et doncδ(n) = (n+1,2) soitδ(n) = 2 sin1 mod 2 etδ(n) = 1 sin0 mod 2.7On proc`ede comme dans l"exercice pr´ec´edent au d´etail pr`es que l"on ne divise plus par un
polynˆome unitaire; appelonsδ(n) le pgcd cherch´e etδ1(n) = (2n3+2n2?12n+4,2n2+5n?3); de mani`ere g´en´erale on aδ1(n) =δ(n) si la multiplicit´e de 2(1)dansn3+n2?6n+ 2 est sup´erieure ou ´egale `a celle dans 2n2+ 5n?3, sinonδ1(n) = 2δ(n) : en particulier sin0 mod 2 alors 2n2+5n?3 est impair et doncδ(n) =δ1(n). De l"´egalit´e 2n3+2n2?12n+4 = n(2n2+ 5n?1)?(3n2+ 9n?4) on en d´eduitδ1(n) = (2n2+ 5n?3,3n2+ 9n?4) = (2n2+ 5n?3,n2+ 4n?1) = (n2+ 4n?1,3n+ 1) par simples soustractions. On introduit `a nouveauδ2(n) = (3n2+ 12n?3,3n+ 1) et comme 3n+ 1 n"est pas divisible par 3, on aδ1(n) =δ2(n) et de l"´egalit´e 3n2+ 12n?3 = (3n+ 1)(n+ 3) + 2n?6, on en d´eduit2(n) = (2n?6,3n+ 1). On introduitδ3(n) = (n?3,3n+ 1) avecδ3(n) =δ2(n) si la
multiplicit´e de 2 dansn?3 est sup´erieure ou ´egale `a celle dans 3n+1 et sinonδ2(n) = 2δ3(n).
On aδ3(n) = (n?3,10) de sorte que
3(n) =10si n3 mod 10
5si n3 mod 5et n0 mod 2
2si n1 mod 2et n3 mod 5
1si n0 mod 2et n3 mod 5
On traite alors les cas un par un :
(a) Siδ3(n) = 1 ou 5 soitn0 mod 2, soit 3n+ 11 mod 2 et doncδ3(n) =δ2(n) =1(n); on a de mˆeme 2n2+ 5n?31 mod 2 soitδ(n) =δ1(n);
(b) siδ3(n) = 2 ou 10 soitn1 mod 2 etn3 mod 5, alors sin3 mod 4 on a 3n+ 12 mod 4 etδ2(n) =δ3(n) =δ1(n); en outre 2n2+ 5n?32 mod 4 et n3+n2?6n+ 20 mod 4 et doncδ(n) =δ1(n). Si on an1 mod 4 alors de mˆeme
3n+10 mod 4 etn?32 mod 4 soitδ1(n) =δ2(n) = 2δ3(n); 2n2+5n?30 mod 4
etn3+n2?6n+ 22 mod 4 de sorte queδ1(n) = 2δ(n);Ainsi on a toujoursδ(n) =δ3(n).
8Une fa¸con agr´eable de faire des calculs est d"´ecrire matriciellement
1 11 0
n =Fn+1Fn F nFn1Le r´esultat d´ecoule alors directement de la multiplication de cette ´egalit´e pournetm. On en
d´eduit alors queFn+mFm=FnFm1Fm=FnFmcar par une r´ecurrence imm´ediate F mFm1= 1. En appliquant l"algorithme d"Euclide (soustractif, i.e. on ne fait pas de division euclidienne mais on soustrait simplement), on obtient le r´esultat.1. i.e. le plus grand entierrtel que 2rdivise le nombre en question
591) On remarque tout d"abord que 650 = 2.325 et 66 = 2.33. On va appliquer l"algorithme
d"Euclide `a 325 et 33 puis on multipliera par deux, ce qui nous permet de gagner quelques lignes de calculs (on n"est pas un ordinateur...)325 = 33.9 + 28 33 = 28 + 5 28 = 5.5 + 3
5 = 3 + 2 3 = 2 + 1
On remonte alors les calculs :
1 = 3?2
1 = 3?(5?3) = 2.3?5
1 = 2.(28?5.5)?5 = 2.28?11.5
1 = 2.28?11.(33?28) = 13.28?11.33
1 = 13.(325?9.33)?11.33 = 13.325?128.33
Finalement la relation de Bezout est 2 = 13.650?128.66, c"est la plus "simple"; on rappelle que les autres sont donn´ees par2 = (13 +k.66)650?(128?k.650)66
pourkZ. (2-i) D"apr`es la relation de Bezout, il existeu,vZtels que 1 =ua+vb, i.e. si on nous rend la monnaie (uouvest forc´ement n´egatif), pouvant payer la somme 1, on peut payer n"importe quelle somme enti`ere. (2-ii) On ´ecritm=ax+byetn=au+bvde la fa¸con la plus simple possible, i.e. 0x,u b?1, de sorte que l"´ecriture est unique; en effet on rappelle quem=a(x?bt) +b(y+at), de sorte qu"il existe un uniquettel que 0x?bt < b. L"´egalit´em+n=ab?a?bdonne alorsab=a(x+u+1)+b(v+y+1) :aetb´etant premier entre eux, "le" th´eor`eme de Gauss nous dit quebdivisex+u+ 1. Or on a 1x+u+ 12b?1, le seul multiple debdans cet intervalle estblui-mˆeme, soitx+u+ 1 =bet doncv+y+ 1 = 0. Les nombresyetv ´etant des entiers, exactement un parmi eux deux est positifou nul, l"autre ´etant strictement n´egatif. En language clair exactement une somme parmimetnest payable sans rendu de monnaie. En remarquant que 0 est payable, alorsab?a?bn"est pas payable. De mˆeme une somme n´egative n"est pas payable de sorte que sim > ab?a?b, la sommemest payable. 3) On ´ecrit 48x+20y+15z= 3(16x+5z)+20y. D"apr`es ce qui pr´ec`ede tout nombre de la forme60 +tavect0 peut s"´ecrire sous la forme 16x+ 5Z. De mˆeme tout nombre de la forme
38 +savecs0, peut s"´ecrire sous la forme 3t+ 20y. Finalement toute somme sup´erieure
ou ´egale `a 218 est payable.´Etudions le cas de 217 : 217 = 20y+ 3u, 217 ?3 mod 20, on en d´eduit que?3(u+ 1) doit ˆetre divisible par 20, soitu= 20k?1 et 220 = 20(y+ 3k) soit11 =y+3kce qui donneu= 19,39,59 et on v´erifie ais´ement qu"aucune de ses possibilit´es ne
s"´ecrit sous la forme 16x+ 5zavecx,ypositifs.4) Soitn >2abc?bc?ac?ab. D"apr`es le th´eor`eme de Bezout, il existe 0x < aavec
nxmodxbcmoda; soityZtel quen=xbc+yade sorte que y a=n?xbc >2abc?bc?ac?ab?(a?1)bc= (bc?b?c)a et doncy> bc?b?c. D"apr`es (b), il existey,z0 tel quey=zb+ycet doncn= xbc+yac+zab. Supposons par l"absurde que 2abc?bc?ac?ab=xbc+yac+zabavecx,y,z0; on aurait alorsa(x+ 1)bcet doncax+ 1 d"apr`es le lemme de Gauss, soitxa?1. De mˆeme6on auraityb?1 etzc?1 si bien que
xbc+yac+zbc3abc?bc?ac?ab >2abc?bc?ac?ab ce qui n"est pas.5) D"apr`es ce qui pr´ec`ede la propri´et´e est vraie pourn= 2,3; on la suppose vraie jusqu"au
rangn?1 et prouvons la au rangn. Soitk > M=a1an n?1?ni=11 ai ; commean est premier aveca1an1, d"apr`es le th´eor`eme de Bezout, il existe 0xn< antel que kxna1an1modan; notonsqn= (k?xna1an1)/ande sorte que N > a 1an n?1?ni=11 ai ?(an?1)a1an1 an=a1an1 n?2?n1 i=11aiD"apr`es l"hypoth`ese de r´ecurrenceN=n1
i=1 j=iajavecxi0 pour touti= 1,,n?1 et donck=ni=1xi j=iaj.Supposons d´esormais queM=ni=1xi
j=iajavecxi0 pour touti= 1,,n. Alors comme dans (d), le lemme de Gauss donne queai(xi+ 1) et doncxiai?1 et finalement que Mn i=1(ai?1) j=ia j> a1an n?1n i=11 ai =M d"o`u la contradiction.10Comme 4 ?3 mod 7 et que 105 est impair, on a 4105 ?3105d"o`u le r´esultat.
11Le sensest ´evident; en ce qui concerne l"autre sens, il suffit de faire un petit tableau
des sommesa2+b2aveca,bZ/3Zpour s"apercevoir quea2+b20 mod 3a,b0 mod 3.12L"entiernest congru au moisMde naissance modulo 13 ce qui le d´etermine parfaitement;
il suffit alors de calculer le jour directement `a partir den?14M.13On anAmod 9; il reste alors `a d´eterminerAexactement ce qui est ais´e puisquek <9
de sorte que l"ordre de grandeur denfixeA.14On rappelle qu"un morphisme d"un groupe cyclique de cardinalndans un groupeGest
compl`etement d´etermin´e par l"imagegd"un g´en´erateur quelconque tellegn= 1G, soitg d"ordre divisantn. Dans le premier cas comme 3 et 4 sont premiers entre eux, les seuls ´el´ements d"ordre divisant 3 dansZ/4Zsont le seul d"ordre 1 `a savoir 0 de sorte que tout morphismeZ/3Z?Z/4Zest nul. DansZ/15Zles ´el´ements d"ordre divisant 12 sont donc d"ordre divisant 1215 = 3 et sont donc 0,5,10, ce qui donne 3 morphismes distincts. D"apr`es les raisonnements ci-dessus, on en d´eduit donc qu"une CNS pour qu"il n"y ait pas de morphisme non nulZ/nZ?Z/mZest doncnm= 1.15Il suffit de remarquer quea3?aest divisible par 2 et 3 et donc 6 divise (a3?a) + (b3?
b) + (c3?c) et donca3+b3+c3a+b+bmod 6.16On rappelle que 700 n"´etant pas premier, 429 est inversibledansZ/700Zsi et seulement si il
quotesdbs_dbs29.pdfusesText_35[PDF] Exercices d 'échauffement et d 'étirement - Travail sécuritaire NB
[PDF] Électrostatique et électrocinétique 1re et 2e années - 2ème édition
[PDF] Equilibres liquide-vapeur des binaires série 1 Exercice 1 Un
[PDF] Exemple de sujet d 'expression orale - CIEP
[PDF] Informatique tronc commun Exercices d 'algorithmique
[PDF] L INFORMATIQUE
[PDF] L INFORMATIQUE
[PDF] L INFORMATIQUE
[PDF] Physique et biophysique PACES UE 3 - Decitre
[PDF] Cartographie
[PDF] pp communication interpersonnelle et groupes - ENSA Paris-Val de
[PDF] Exercices corrigés de Comptabilité générale
[PDF] comptabilité générale de l 'entreprise - Decitre
[PDF] SERIE D EXERCICE N° 1 (Introduction au Génie Logiciel