UNIVERSITÉ dORLÉANS SCL1 MA02 Département de PDF

UNIVERSITÉ dORLÉANS SCL1 MA02 Département de

Arithmétique : Corrigé Feuille 4 (Congruences ). Exercice 1. Calculons le reste de 78 divisé par 6 i.e on cherche 0 ≤ x < 6 tel que. 78 ≡ x [6]. Modulo 6

M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2

Corrigé du DS n. ◦. 2. Exercice 1. Résoudre le système de congruences :.. x ≡ 1 mod 3 x ≡ 2 mod 11 x ≡ 51 mod 61. Solution. L'algorithme d

Exercices congruences.pdf

Exercices sur les congruences. Corrigé. Exercice 1. 1). 2). 3). Exercice 2. N. 0. 1. 2. 3. 4.

Exercices à savoir faire

Résoudre dans Z les systèmes de congruence suivants. (1). {︃. ≡ 3 (mod 12) Peut-on le corriger ? 3. Montrer que l'on peut détecter un chiffre inexact ou ...

DIVISIBILITE et CONGRUENCE – Feuille dexercices

Les corrigés des exercices seront à retrouver sur le Padlet Terminales Maths 2) Dans le système de numération en base 10 déterminer

Congruences et théorème chinois des restes

Cherchons à résoudre le système de congruences suivant :.. x ≡ 1 (mod 3) x ≡ 2 (mod 5) x ≡ 3 (mod 7). On pose M = 3 × 5 × 7 = 105. M1 = 105/3

Congruence

Exercice 4. On dit que a mod n est inversible si il existe b mod n tel que ab ≡ 1 mod n. 1. Trouver tous les éléments inversibles modulo 5 6

CONGRUENCES DANS Z – Exercices corrigés

Exercice 1 : Trouver le reste de la division euclidienne de 1952 par 7. Cela revient à chercher la classe de congruence de 1952 modulo 7.

CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

(d) Laissée comme exercice. (e) a − a = kn b − b = ln =⇒ ab − a b = ab système de représentants modulo p contenant 0. Alors pour chaque k parmi 1 ...

Mathématiques : du lycée aux CPGE scientifiques

exercice de niveau moyen 3 un exercice assez difficile

M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2

Exercice 1. Résoudre le système de congruences : équivaut donc à la congruence x ? a mod (3×11) avec a = 1×(?1×11)+2×(4×3) = 13. Le système se réduit ...

UNIVERSITÉ dORLÉANS SCL1 MA02 Département de

Arithmétique : Corrigé Feuille 4 (Congruences ). Exercice 1. Exercice 8. a) Factorisons 455 en produit de nombres premiers. On a 455 = 5×91 =.

Feuille 1 : Arithmétique élémentaire et congruences

Indication : on pourra traduire le problème comme un système de congruences et utiliser le théorème des restes chinois. Exercice 12 a et b sont premiers entre

Exercices congruences.pdf

Exercices sur les congruences. Exercice 1 Exercice 2. Compléter la table de congruence suivante modulo 5 ... Corrigé. Exercice 1.

Congruences et théorème chinois des restes

Résolution des équations sur les congruences. Supposons que l'on cherche à résoudre : Cherchons à résoudre le système de congruences suivant :.

Exercices corrigés arithmétique

Exercices corrigés d'arithmétique. Diviseurs –Division euclidienne : Exercice 1 : le premier et les deux derniers systèmes n'ont pas de solutions.

Congruence

Exercice 4. On dit que a mod n est inversible si il existe b mod n tel que ab ? 1 mod n. 1. Trouver tous les éléments inversibles modulo 5 6

Mathématiques pour

1.4 Congruences. 11. TD – Le codage affine. 13. Exercices corrigés 3.4 Résolution de systèmes à l'aide de matrices. 77. Exercices corrigés.

Congruences - Arithmétique Spé Maths terminale S : Exercices

Spé Maths terminale S : Exercices. Corrigés en vidéo avec le cours sur jaicompris.com. Apprendre `a calculer avec les congruences.

Exercices darithmétique

— Résoudre dans Z les congruences suivantes : 1) 3x ? 4 mod 7;. 2) 9x ? 12 mod 21;. 3) 103x ? 612 mod 676. Exercice 18. — Donner la congruence modulo 17 de (

Exercices - Congruences - bigmaths / mathématiques pour le

TS 1 Exercices Exercices - Congruences Exercice 1 Soient a b et n trois entiers naturels tels que a b[n] 1 Si a 0[n] alors ab b 0[n] donc ab 0[n] 2 4 9 = 36 = 6 6 donc 4 9 0[6] 3 Faux le preuve dans la question pr ec edente Exercice 2 Recopier et completer le tableau ci-dessous qui donne modulo 6 le produits des entiers de 0 a 5

UNIVERSIT

´E d"ORL´EANSSCL1 MA02

D´epartement de math´ematiques2008-9Arithm´etique : Corrig´e Feuille 4 (Congruences ). 7

8≡x[6]. Modulo 6, on a :

8≡(72)4≡(49)4≡(6×8 + 1)4≡(1)4≡1.

Le reste est donc 1.

Calculons le reste de 3

15divis´e par 11. Modulo 11, on a

15≡(33)5= (27)5≡(2×11 + 5)5≡55≡(52)2×5≡(25)2×5≡(2×11 + 3)2×5

≡32×5≡9×5≡45≡4×11 + 1≡1. Le reste est donc 1. (On n"a pas besoin de calculer explicitement la puissance). Exercice 2.Montrons que 2x+ 9y≡0 [8] implique 10x-3y≡0 [8]. On a (modulo

8) 2x≡ -9ydonc 5×2x≡ -5×9y≡ -45y≡(-6×8+3)y≡3y. Ainsi 10x≡3yet

donc 10x-3y≡0 [8]. Exercice 3.Trouvrons tous les entiersytels que 2y≡5 [7]. On calculepgcd(2,7) = 1. Ainsi 2 et 7 sont premiers entre eux et que 7 = 3×2+1. Ainsi (1)×7+(-3)×2 = 1. Ce qui donne (-3)×2≡1 [7]. On posex0=-3 alors 2×x0≡1 [7]. En multipliant par

5: 2×(5x0)≡5 [7]. Ainsi une solution particuli`ere de 2y≡5 [7] esty0= 5x0=-15.

Pour trouver toutes les solutions de 2y≡5 [7], on "retranche" la solution particuli`ere y

0ainsi 2(y-y0)≡5-5≡0 [7]. Ce qui ´equivaut `a: 7 divise 2(y-y0). Puisque 2

et 7 sont premiers entre eux, on a par le lemme de Gauss, que 7 divise (y-y0) i.e. il existek?Ztel quey-y0= 7k. On conclut quey=y0+ 7k=-15 + 7kaveck?Z. R´eciproquement, on v´erifie que toutyde la formey=-15 + 7kaveck?Zv´erifie aussi 2y≡5 [7]. L"ensemble des solutionsSest ´egal `aS={-15 + 7k,k?Z}. Exercice 4.Trouvons tous les entiersytels que 3y≡12 [33]. On calculepgcd(3,33) =

3. L"´equation 3y≡12 [33] ´equivaut `a33

y≡123 [333 ] (Voir cours) i.e.y≡4 [11]. Ainsi y= 11k+ 4 aveck?Z. L"ensemble des solutionsSest ´egal `aS={11k+ 4,k?Z}.

Exercice 5.Trouvons tous les entiersxtels que?

x≡3 [11] x≡5 [7]. On commence par chercher une solution particuli`erex0du syst`eme `a r´esoudre. On suit la m´ethode du cours `a la lettre. On apgcd(11,7) = 1. Par Bezout, 1 = (2)×11 + (-3)×7. On posex0= (2)×5×11+3×(-3)×7 = 47 (Attention `a bien placer le 3 et le

5: voir cours). On v´erifira toujours explicitement quex0est une solution particuli`ere.

En effet, on a modulo 11,x0≡3×[(-3)×7]≡3[1-2×11]≡3-3×(2)×11≡3.

Et modulo 7, on a :

1 2 x

On a que

x≡x0≡3 [11] x≡x0≡5 [7].

Ainsi par diff´erence,

x-x0≡0 [11] x-x0≡0 [7]. Ainsix-x0est multiple de 11 et 7. Puisque 11 et 7 sont premiers entre eux alors x-x0est multiple de 11×7 = 77. D"o`ux=x0+ 77k= 47 + 77kpour unk?Z. R´eciproquement, tous lesxde la formex= 47 + 77kpour unk?Zsont solutions.

L"ensemble des solutions estS={47 + 77k,k?Z}.

Exercice 6.a) Montrons que 223 est un nombre premier. Il suffit de voir si les nom- non. Donc 223 est premier. b) Calculons 1998

1998modulo 223. On ne calcule ´evidemment pas 19981998explicite-

ment. On utilise le corollaire de Fermat pour toutx?N,xp-1≡1 [p] pourppremier etxnon divisible parp.

On en d´eduit 1998

222≡1 [223]. On effectue la division euclidienne de 1998 par 222,

on a 1988 = 9×222. Ainsi modulo 223, on a 19981998≡((1998)222)9≡(1)9≡1.

Exercice 7.Trouver tous les entiersxtels que?

x≡ -1 [8] x≡7 [13]. Exercice 8.a) Factorisons 455 en produit de nombres premiers. On a 455 = 5×91 =

5×7×13.

b) Soientaetndes entiers naturels. Montrons que l"on aan≡1 [455] si et seulement sian≡1 [5],an≡1 [7] etan≡1 [13]. Supposons quean≡1 [455] i.e.an-1 est multiple de 455 alorsan-1 est multiple de 5, de 7 et de 13 d"apr`es a). R´eciproquement, supposonsan≡1 [5],an≡1 [7] et a n≡1 [13] i.e.an-1 est multiple de 5, de 7 et de 13. Alorsan-1 = 5q1pourq1?N. Puisque 7 divisean-1 i.e. 5q1et que 5 et 7 sont premiers entre eux alors par le lemme de Gauss, 7 diviseq1i.e.q1= 7q2avecq2?N. Doncan-1 = 5×7×q2. Puisque 13 est premier avec 5×7 et que 13 divisean-1 alors par le lemme de Gauss, 13 diviseq2 i.e.q2= 13q3avecq3?N. Ainsian-1 = 5×7×13q3= 455q3. Doncan-1 est bien multiple de 455 i.e.an≡1 [455]. c) Soitaun entier tel quepgcd(a,455) = 1. Montrons que l"on aa12≡1 [455]. Ceci est ´equivalent `a montrer quea12≡1 [5],a12≡1 [7] eta12≡1 [13] (avecn= 12). 3 Puisquepgcd(a,455) = 1 impliquepgcd(a,5) = 1,pgcd(a,7) = 1 etpgcd(a,13) = 1. Par le corollaire de Fermat,a4≡1 [5] donca12≡(a4)3≡1 [5] eta6≡1 [7] donc a

12≡(a6)2≡1 [7]. puisa12≡1 [13]. Ce qui donne le r´esultat.

Exercice 9.Soientpun nombre premier etaun entier positif non multiple dep. a) Montrons qu"il existe un plus petit entier positifktel queak≡1 [p]. D"apr´es le corollaire de Fermatap1≡1 [p]. L"ensemble de??N?v´erifianta?≡1 [p] n"est pas vide puisqu"il contientp-1. Cet ensemble est non vide et minor´e donc il existe un plus petit entierk≥1 tel queak≡1 [p]. Soitn?N. Notonsrle reste de la division euclidienne denpark. b) Montrons que l"on aan≡1 [p] si et seulement sinest multiple dek. Supposons quean≡1 [p]. Avecn=qk+r, on obtientan≡(ak)qar≡ar[p] carak≡1 [p]. contradiction). c) Soitp= 5 eta= 4. V´erifions quea4≡44≡(162)≡(15 + 1)2≡12≡1 [5]. Cherchons le plus petit entierktel que 4k≡1 [5]. On a 41≡4 [5] et 42≡15+1≡1 [5] ainsik= 2. Notons quek <(p-1) ici. Exercice 10.a) Soita?Z. Montrons quea2est congru `a 0, 1 ou 4 modulo 8.

Sia≡0;[8] alorsa2≡0;[8].

Sia≡1;[8] alorsa2≡1;[8].

Sia≡2;[8] alorsa2≡4;[8].

Sia≡3;[8] alorsa2≡9≡1;[8].

Sia≡4;[8] alorsa2≡16≡0;[8].

Sia≡5;[8] alorsa2≡25≡24 + 1≡1;[8]. Sia≡6;[8] alorsa2≡36≡32 + 4≡4;[8]. Sia≡7;[8] alorsa2≡49≡48 + 1≡1;[8]. b) Soitnun entier positif. Montrons quea2+b2+c2?= 8n-1, pour tousa,b,c?Z. On interpr´ete cette derni`ere ´equation dans le language de la congruence:a2+b2+c2 n"est pas congru `a-1 modulo 8 ou encorea2+b2+c2n"est pas congru `a 8-1 = 7 modulo 8. On consid`ere tous les cas posssibles (27 cas) en consid´eranta2est congru `a 0 ou 1 ou 4 modulo 8 etb2est congru `a 0 ou 1 ou 4 modulo 8 etc2est congru `a 0 ou 1 ou 4 modulo 8. Par exemple,a2est congru `a 4,b2est congru `a 1 etc2est congru `a 1 ainsia2+b2+c2 est congru `a 4 + 1 + 4 = 9 i.e. `a 1 modulo 8. (Les autres cas sont laiss´es `a faire). Exercice 11.a) Factorisons 1729 en produit de nombres premiers. On teste les di- 4 b) Soientaetndes entiers positifs. Montrons que l"on aan≡1 [1729] si et seulement sian≡1 [7],an≡1 [13] etan≡1 [19]. La preuve est analogue `a celle de l"exo. 8. L"argument principal est le fait que les nombres 7,13,19 sont des nombrers premiers. c) Soitaun entier positif tel quepgcd(a,1729) = 1. D´emontrer que l"on aa1728≡

1 [1729]. La preuve est analogue `a celle de l"exo. 8.

Exercice 12.Trouvons tous les entiersxtels que?

7x≡5 [19]

3x≡1 [11].

Solutions: Le syst`eme ´equivaut `a

3×7x≡3×5 [3×19]

7×3x≡7×1 [7×11].

i.e.

21x≡15 [57]

21x≡7 [77].

On posey= 21xet on r´esoud?

y≡15 [57] y≡7 [77]. On applique la m´ethode du cours (voir aussi l"exercice 7). On apgcd(57,77) = 1 car par Bezout 1 = (20)×77+(-27)×57. Un solution particuli`erey0= (20)×15×77+ (-27)×7×57 = 12327 (Attention o`u on place 15 et 7). La solution g´en´eraleysatisfait? y-y0≡0 [57] y-y0≡0 [77]. qui ´equivaut `a y-y0≡0 [57×77] car 57 et 77 sont premiers entre eux. D"o`u l"ensemble de solutionsS?poury, S ?={y= 12327 + 4389k,k?Z}. On en d´eduit l"ensemble de solutionsSpourx,

S={x= 587 + 209k,k?Z}(carx=y/21).

quotesdbs_dbs8.pdfusesText_14

[PDF] UNIVERSITÉ dORLÉANS SCL1 MA02 Département de