[PDF] Exercice 1 (3 points) Solution de lexercice 1 Exercice 2 (2 points

View - Download Exercice 1 (3 points) Solution de lexercice 1 Exercice 2 (2 points

Previous PDF

Next PDF

Licence 1 - Mathématiques & Prépa IngénieursAlgèbre et Arithmétique 1

Université Rennes 12015-2016

Examen terminal du mercredi 6 janvier 2016

Durée : 2 h

Les documents de cours, calculatrices et téléphone portables ne sont pas autorisés.

Le sujet comporte SIX exercices.

Le barème est donné à titre indicatif.

Toutes les réponses doivent être justifiées.

Exercice 1(3 points)1.Montrer que dans un ensemble de cardinal 10, deux sous-ensembles de cardinal 7 ont une

intersection non vide. 2. Dessiner (si possible) trois ensemblesA,BetCavec cinq éléments chacun et dont la réunion A[B[Ca neuf éléments et l"intersectionA\B\Caucun.

3.SoientA,BetCtrois sous-ensembles d"un ensembleEtels queA[B=B\C.

Montrer queABC.

Solution de l"exercice 11.

SoientEun ensemble de cardinal 10 etAetBdeux sous-ensembles deEde cardinal 7. On a card(A[B) = cardA+ cardBcard(A\B) = 14card(A\B) OrA[BEdonccard(A[B)6cardE= 10. On en déduit quecard(A\B) = 14card(A[

B)>1410 = 4. DoncA\Best non vide.

2. Par exemple,E=N,A=f1;2;3;4;5g,B=f4;5;6;7;8getC=f1;2;3;6;9g. AlorsA[B[C= f1;2;3;4;5;6;7;8;9ga pour cardinal 9 etA\B\C=;. 3. Soitx2A. Alorsx2A[B. OrA[B=B\Cdoncx2B\CB. On a montré queAB. De même, soitx2B. Alorsx2A[B. OrA[B=B\Cdoncx2B\CC. On a montré queBC. Exercice 2(2 points)Trouver le reste de la division euclidienne de22285555par 11.

Solution de l"exercice 2

On remarque que2222est divisible par 11 donc22286 (mod11). On en déduit que22285555

65555(mod11). Or 11 est un nombre premier et 6 est premier avec 11, donc, d"après le théorème

de Fermat,6101 (mod 11). On a a alors65555= 610555+5= (610)5556565(mod 11). Or65= 62626 = 36366336 (mod11)96 (mod11)54 (mod11) 1 (mod 11). On en déduit que le reste de la division euclidienne de22285555par 11 est 10.

Exercice 3(3 points)SoientEetFdeux ensembles.

1.En utilisant les quantificateurs, donner la définition d"une fonction injective deEdansF.

2.Montrer que la fonctionf:Rn f3g !Rdéfinie parf(x) =x+ 17x3est injective.

3.Calculer l"imagef(Rn f3g). La fonctionfest-elle surjective?

Solution de l"exercice 3

1.La fonctionfest injective deEdansFsi une des propriétés suivantes est vérifiée :

8x2E;8x02E;f(x) =f(x0) =)x=x0

8(x;x0)2A2;[x6=x0=)f(x)6=f(x0)]

2.Soientxetx0deux éléments deRn f3gtels quef(x) =f(x0). On a alorsx+ 17x3=x0+ 17x

03, soit en faisant le produit en croix(x+ 17)(x03) = (x0+ 17)(x3). En développant les facteurs, on obtientx=x0. Donc la fonctionfest injective deRn f3gdansR. 3. On af(x) = 120x3, la fonctionfest donc strictement croissante sur chacun des inter- valles] 1;3[et]3;+1[. Orlimx!+1f(x) =limx!1f(x) = 1,limx!3f(x) = +1et limx!3+f(x) =1. On en déduit quef(Rn f3g) =Rn f1g: La fonctionfn"est donc pas surjective car 1 n"a pas d"antécédent parf. Exercice 4(2 points)Résoudre surZl"équation55n9 (mod 72).

Solution de l"exercice 4

Les décompositions en produit de facteurs premiers de 55 et 72 sont55 = 511et72 = 2332donc les entiers 55 et 72 sont premiers entre eux. On en déduit que 55 admet un inverse modulo 72.

L"algorithme d"Euclide s"écrit :

72 = 155 + 17

55 = 317 + 4

17 = 44 + 1

(Ce qui permet également de montrer que 55 et 72 sont premiers entre eux).

En remontant l"algorithme d"Euclide (on peut aussi utiliser l"algorithme d"Euclide étendu), on obtient

1 = 1744

= 174(55317) = 1317455 = 13(7255)455 = 13721755 On en déduit que17551 (mod 72)donc17est un inverse de 55 modulo 72.

Alors, pour tout entiern:

55n9 (mod72)si, et seulement si,1755n 179 (mod72). Cette dernière égalité se

réécritn 153 9 (mod72), donc les solutions sont les entiers de la forme9 + 72k, pour k2Z. Remarque : l"équivalence entre les deux équations aux congruences55n9 (mod72)et1755n

179 (mod 72)vient du fait qu"on retrouve la première en multipliant la seconde par55.

Exercice 5(6 points)1.Soientpun nombre premier eta2Z. Montrer quepgcd(a;p) = 1si, et seulement si,pne divise pasa.

2.Soit(a;b;c)2Z3.

Montrer que, sipgcd(a;b) = 1etpgcd(a;c) = 1, alorspgcd(a;bc) = 1.

La réciproque est-elle vraie? Justifier.

3.À l"aide d"une récurrence soigneusement écrite, montrer que

8(a;b)2Z2;(pgcd(a;b) = 1 =) 8n2N;pgcd(a;bn) = 1):

4. Montrer que, pour tout entier naturelnnon nul, on apgcd(2;4n+7n) =pgcd(7;4n+7n) = 1. On pourra utiliser les première et troisième questions.

5.Pour tout entier naturelnnon nul, déterminer la valeur explicite depgcd(56;4n+ 7n).

Solution de l"exercice 51.p

est premier et, par définition,pgcd(a;p)est un diviseur dep. On en déduit quepgcd(a;p) vaut1oup. Alors,pgcd(a;p) =psi, et seulement, sipdivisea. Ainsi,pgcd(a;p) = 1si, et seulement si,pgcd(a;p)6=p, ce qui est équivalent à :pne divise pasa.

2.On va montrer quepgcd(a;b) = 1etpgcd(a;c) = 1si, et seulement si,pgcd(a;bc) = 1. Il y

a deux méthodes pour répondre à la question : on peut utiliser le théorème de Bézout, ou

raisonner sur les facteurs premiers des pgcd qui entrent en jeux. Avec les combinaisons de Bézout: Supposonspgcd(a;b) = 1etpgcd(a;c) = 1, et soient u;v;u0;v0des entiers tels queau+bv= 1etau0+cv0= 1(ils existent d"après le théorème de Bézout). Alors, en multipliant ces égalités, on a(au+bv)(au0+cv0) = 1, soit : a(auu0+ucv0+bvu0) +bc(vv0) = 1 ce qui montre queaetbcsont premiers entre eux, toujours par le théorème de Bézout. Réciproquement, siaetbcsont premiers entre eux, on a des entiersuetvtels queau+bcv= 1.

Cette identité de Bézout fournit une identité de Bézout entreaetb, ainsi qu"entreaetc, ce

qui montrepgcd(a;b) = 1etpgcd(a;c) = 1. Avec les facteur premiers: On va montrer la contraposée de la première implication : supposons pgcd(a;bc)6= 1, et considérons un facteur premierpdepgcd(a;bc), ce qui est possible car tout entier naturel strictement plus grand que1admet un diviseur premier. Alors,pdivisebc. Mais, par le lemme d"Euclide, sipdivisebc, alorspdiviseboupdivisec. Maispdivisant aussia, on en déduit quepdivisepgcd(a;b), ou quepdivisepgcd(a;c). Dans tous les cas, l"assertion "pgcd(a;b) = 1etpgcd(a;c) = 1" est fausse, car l"un de deux pgcd à un diviseur premier, d"où le résultat. Réciproquement, supposonspgcd(a;bc) = 1.pgcd(a;b)etpgcd(a;c)sont des diviseurs de pgcd(a;bc) = 1car tous deux divisentaetbc, doncpgcd(a;b) = 1etpgcd(a;c) = 1.

3.Soientaetbdeux entiers premiers entre eux. Montrons par récurrence sur l"entiern, que :

8n2N;pgcd(a;bn) = 1

La propriété dépendant de l"entiernintervenant dans la récurrence, est donc (Hn) :pgcd(a;bn) =

1. Initialisation : Au rang0, l"énoncé à montrer est :pgcd(a;b0) = 1. Maisb0= 1, donc il faut montrerpgcd(a;1) = 1ce qui est vrai pour tout entiera. Hérédité : Soitnun entier naturel, supposons quepgcd(a;bn) = 1(Hn) et montrons que aetbn+1sont premiers entre eux (Hn+1). On sait quepgcd(a;b) = 1(par hypothèse) et

pgcd(a;bn) = 1(par hypothèse de récurrence). D"après la question précédente, on en déduit

quepgcd(a;bbn) = 1, i.e. quepgcd(a;bn+1) = 1, ce qui est bien la propriété voulue au rang n+ 1.

La propriété est héréditaire, donc par le principe de récurrence, on a bien montré que :

8n2N;pgcd(a;bn) = 1

4. Soitnun entier strictement positif. L"entier2étant premier donc,pour montrer quepgcd(2;4n+

7n) = 1, il suffit, d"après la question1, de montrer que2ne divise pas4n+ 7n(et de même

pour7). On constate que2divise4n(nétant non nul, on peut écrire4n= 2(2:4n1)), et que2 ne divise pas7n. En effet,2et7sont premiers entre eux (car732 = 1, ou encore car deux

nombres premiers distincts sont premiers entre eux), donc d"après la question précédente,2et

7nsont aussi premiers entre eux. Raisonnons maintenant par l"absurde : si2divisait4n+ 7n,

puisque2divise aussi4n, on aurait que2divise la différence4n+ 7n4n= 7n, mais on déjà prouvé le contraire, d"où une contradiction. On prouve ainsi que2et4n+ 7nsont premiers entre eux. Le raisonnement est le même pour7:7divise7n, mais pas4n. Si par l"absurde,7n"était pas premier avec4n+7n, alors par la question1,7diviserait4n+7n, donc aussi4n+7n7n= 4n, ce qui est une contradiction. 5. D"après la question4,4n+ 7nest premier avec2et7, donc aussi avec23= 8(question3). Mais alors,4n+ 7nétant premier avec8et7, la question1montre que4n+ 7nest premier avec87 = 56, ce qui répond à la question :pgcd(56;4n+ 7n) = 1.

Tourner la page S.V.P.

Exercice 6(6 points)Soientnun entier naturel etEun ensemble fini ànéléments. On noteXl"ensemble des couples(A;B)composés de deux parties deEtelles queAB. L"objet de l"exercice est de montrer que card(X) = 3n.

1.Donner le cardinal de l"ensembleP(E)des sous-ensembles deE. (On ne demande pas de

justification.)

2.Dans cette question seulement, on supposen= 2etE=f1;2g. DéterminerX.

3.Énoncer la formule du binôme de Newton pour deux réelsxety.

4.Soitj2 f0;:::;ng, on noteXjl"ensemble des paires(A;B)2Xtelles que card(B) =j.

Montrer quefXjg06j6nest une partition deX.

5.On veut choisir(A;B)2Xj.

Combien de choix possibles y a-t-il pourB?

Une foisBchoisie, combien de choix possibles y a-t-il pourA?

6.En déduire le cardinal deXj, puis celui deX.

Solution de l"exercice 61.Sicard(E) =n, alorscard(P(E)) = 2n.

3.Soitxetydeux réels etnun entier naturel alors

(x+y)n=nX p=0 n p x pynp=nX p=0 n p x npyp 4. Soientj2 f0;:::;ngetBun sous-ensemble deEavecjéléments. CommeBB, on a (B;B)2Xj. DoncXjest non vide. Soienti2 f0;:::;ngetj2 f0;:::;ngtels quei6=j. Supposons queXi\Xjsoit non vide. Il existe alors(A;B)2Xi\Xj. On a donc, à la fois,card(B) =ietcard(B) =j. Ori6=j.

Absurde doncXi\Xj=;.

On a[jXjX. Soit(A;B)2X.Best un ensemble fini car inclus dansE. Posonsi=card(B), alors06i6n. On a montré que(A;B)Xi. On a donc[jXj=XetfXjg06j6nest une partition deX. 5.B est un sous-ensemble àjéléments d"un ensemble ànéléments. Il y a doncn jchoix pourB. Une foisBchoisie, l"ensembleAest choisi comme étant un sous-ensemble deB. Or un ensemble dejéléments a2jsous-ensembles.

6.L"ensembleXja donc2jn

jéléments. CommefXjg06j6nest une partition deX, on a cardX=nX j=0cardXj=nX j=02 jn j Si on faitx= 2ety= 1dans la formule du binôme, on en déduit quecardX= 3n.quotesdbs_dbs45.pdfusesText_45

[PDF] algorithme deuclide calculatrice PDF Cours,Exercices ,Examens

[PDF] algorithme deuclide en arabe PDF Cours,Exercices ,Examens

[PDF] algorithme d'euclide polynomes PDF Cours,Exercices ,Examens

[PDF] algorithme d'euclide tableau PDF Cours,Exercices ,Examens

[PDF] algorithme d'un portail automatique PDF Cours,Exercices ,Examens

[PDF] Algorithme dans un contexte matriciel (spé maths terminale) 1ère Mathématiques

[PDF] Algorithme de 1 ère 1ère Mathématiques

[PDF] Algorithme de 1ère ES 1ère Mathématiques

[PDF] Algorithme de biochimie 1ère Physique

[PDF] algorithme de bresenham cercle PDF Cours,Exercices ,Examens

[PDF] algorithme de bresenham en c PDF Cours,Exercices ,Examens

[PDF] algorithme de bresenham en java PDF Cours,Exercices ,Examens

[PDF] Algorithme de calcul de moyenne,variance et écart type 1ère Mathématiques

[PDF] algorithme de calcul, écrire lalgorithme dun calcul correspondant 3ème Mathématiques

[PDF] algorithme de chiffrement des PDF Cours,Exercices ,Examens