[PDF] MAT210 Logique et mathématiques discrètes : Cours 1

View - Download MAT210 Logique et mathématiques discrètes : Cours 1

Previous PDF

Next PDF

Chapitre 5Entiers, division et congruences

Ce document contient des définitions qui seront présentées en classe, plusieurs théorèmes dont

nous ferons la démonstration et quelques exercices qui seront faits en équipe lors de la cinquième et

sixième semaine de cours. Les pages indiquées entre crochets renvoient au livre obligatoireDiscrete

Mathematics and its applications, septième édition, K. H. Rosen, livre qui comporte de nombreux

exercices importantspourvouspréparezà l"examen. Avantde commencer la présentationthéorique,

nousdiscuteronsde quelquesapplications dumodulo eninformatique(voirdocument pptsurle site Web).

5.1 Division

Définition 5.1[p. 238 D1] Sia?Z,b?Zeta?=0, on dit queadivisebs"il existe un entierctel que b=ac. Notation: a|b?? ?c?Z,ac=b??b a?Z a?|b?? ¬(a|b) Théorème 5.1[p. 238 T1] Soienta,betcdes nombres entiers quelconques, aveca?=0.

1. Sia|beta|calorsa|(b+c).

2. Sia|balorsa|(bc).

3. Sia|betb|calorsa|c.

Exercice 5.1Vrai ou faux? Justifiez en invoquant une définition, un théorème, en donnant une

preuve ou un contre-exemple. (a) 7|10 (b) 5|10 (c) 100|10 (d) 5| -10 (e)?x,x|17→x|85 (f)?x,x|bc→(x|b?x|c) 1

2CHAPITRE 5. ENTIERS, DIVISION ET CONGRUENCES

(g)?x,¬(x|5)→¬(x|45) (h)?x, (x|36?x|100)→x|172 (i)?x, (x|36?x|100)→x|64 (j) Démontrez la partie 3 du théorème 5.1. a|b?b|c→a|c Théorème 5.2[p. 239 T2] Soientaetddes entiers, avecd>0. Il existe une seule paire d"entiersqet rsatisfaisant une seule paire d"entiersqetrsatisfaisant

Par exemple sia=17 etd=3, on a

• L"entierd=3 est appelé lediviseur. • L"entiera=17 est appelé ledividende. • L"entierq=5 est appelé lequotient(notation:q=adivd). • L"entierr=2 est appelé lereste. On dit aussi que 17 est égal à 2modulo3 (notation:r=amodd).

L"algorithme de division, présenté à la page 253, présente une façon de calculer le quotientqet le

resterde la division deapar l"entier positifd. Il s"agit de compter le nombre de fois (q) que l"on peut

soustrairedde|a|tout en conservant un résultat positif (r). Siaest positif, le diviseur estqet le reste

estr. Siaest négatif, on procède à un petit ajustement (r:=d-retq:=-(q+1) ).

5.2 Arithmétiquemodulaire

si et seulement simdivisea-b. Notation a≡b(modm)??m|(a-b) Attention: le symbole≡est aussi utilisé en logique, mais il a ici un sens différent. Remarque: siaest congru àbmodulom, c"est quemdivise (a-b),mais alorsmdivise aussi (b-a), et donc, par définition,best congru àamodulom. On peut donc dire queaetbsont congrus modulom.

Geneviève Savard, ÉTS, 2014

5.2. ARITHMÉTIQUE MODULAIRE3

Exemple 5.1

Les nombres 73 et 23 sont congrus modulo 10 car 10 divise leur différence.

73≡23 (mod 10)??10|(73-23)

Les nombres 17 et 32 sont congrus modulo 5 car 5 divise leur différence.

17≡32 (mod 5)??5|(17-32)

??5|(-15) -15 5?Z ?? -3?Z Les nombres -8 et 7 sont congrus modulo 5 car 5 divise leur différence. -8≡7 (mod 5)??5|(-8-7) ??5|(-15) -15 5?Z ?? -3?Z Théorème 5.3Soientaetbdes entiers etm?Z+. Les énoncés suivants sont équivalents.

1.a≡b(modm)

2.m|(a-b)

3. (amodm)=(bmodm)

4.?k?Z,a=b+km

Exemple 5.2

Les nombresa=73 etb=23 sont congrus modulo 10, ce que l"on note

73≡23 (mod 10)

Ainsi, par le théorème précédent, ils ont le même reste aprèsdivision par 10. En effet:

(73 mod 10)=3 et (23 mod 10).=3. De plus, on peut passer debàaen ajoutant un multiple de 10:

73=23+5·10.

Exemple 5.3

Nous avonsvu à l"exemple précédentque lesnombresa=17 etb=32 sont congrusmodulo 5, ce que l"on note

17≡32 (mod 5).

Geneviève Savard, ÉTS, 2014

4CHAPITRE 5. ENTIERS, DIVISION ET CONGRUENCES

Nous aurions pu arriver à cette conclusion sans calculer leur différence, en utilisant le fait qu"ils ont

le même reste après division par 5. En effet: (17 mod 5)=2 et (32 mod 5)=2. De plus, on peut passer debàaen ajoutant un multiple de 5:

32=17+3·5.

Exercice 5.2Vrai ou faux?

(a) 7≡13 (mod 6) (b)-2≡10 (mod 6) (c) 0≡14 (mod 6) (d) 30≡600 (mod 6) (e) 5

3≡5 (mod 20)

Théorème 5.4[p. 242 T5] Soitm?Z+. Sia1≡r1(modm) eta2≡r2(modm) alors a

1+a2≡r1+r2(modm) eta1·a2≡r1·r2(modm)

On peut donc calculer les modulos dea1eta2, puis les additionner, ou encore additionner d"abord a

1eta2puis calculer le modulo du résultat, et on arrivera à un résultat équivalent modulom. Il en

va de même pour la multiplication. Or, il est beaucoup plus rapide de multiplier de petits nombres.

En arithmétique modulaire, il sera donc préférable de calculer d"abord les restes modulom, puis

d"effectuer leur multiplication. Exercice 5.3Calculezsanscalculatrice. Vérifiez avec la commande mod(a, m) de la TI quicalcule amodm. (a) 44 mod 10 (b)-44 mod 10 (c)-2 mod 11 (d) (-2)2mod 11 (e) (136·882·14+12) mod 5 N. B. Vous n"avezpasà effectuerla multiplication des3 nombres suivie de l"addition de 12 puis à effectuer la division par 5 pour obtenir le modulo. Soyez stratégique! (f) (55·13+8·47) mod 11 (g) 9

2mod 11

(h) 9

4mod 11 N. B. Vous n"avezpasà évaluer 94puis à effectuer la division par 11. Utilisez le

résultat précédent et le théorème. (i) 9

8mod 11

(j) 9

16mod 11

(k) 9

20mod 11Rappel920=916+4=91694

(l) 9

28mod 11 (Au besoin, voir l"algorithmeModular Exponentiationet l"exemple 12 p. 254.)

Geneviève Savard, ÉTS, 2014

5.3. NOMBRES PREMIERS5

5.3 Nombres premiers

Théorème 5.5[Théorème fondamental de l"arithmétique] Tout entier positif supérieur à 1 peut

être écrit de façon unique soit comme un nombre premier, soitcomme un produit de nombres premiers où les facteurs sont écrits en ordre croissant.

Unepreuve parrécurrence est présentée à la page 236. Nous n"avons pasencore étudié ce type de

preuve; nous le ferons en deuxième moitié de trimestre. Exercice 5.4Donnez la décomposition en facteurs premiers de 84 et de 150. Théorème 5.6[T3 p. 260] Il y a une infinité de nombres premiers. Définition 5.4[pp 215 et 217] Soientaetbdes entiers. Le plus grand entierdqui diviseaet qui divisebest appelé leplus grand commun diviseurdeaetb. On le note pgcd(a,b) en français et gcd(a,b) en anglais. N.B. pgcd(0,0) n"est pas défini. Leplus petit commun multipledeaetbest le plus petit entierntel quea|netb|n. On le note ppcm(a,b) en français et lcm(a,b) en anglais. Comment calculer pgcd(a,b) et ppcm(a,b)? Si les décompositions en facteurs premiers des entiersaetbsont connues on peut obtenir rapidement pgcd(a,b) et ppcm(a,b) en prenant les minimums ou les maximums de chacun des exposants, tel qu"indiqué aux exemples 14 et 15 de la

page 266. Quand les décompositions en facteurspremiers ne sont pasdéjà connues, il est plus rapide

d"utiliser l"algorithme d"Euclide pour calculer le plus grand commun diviseur (voir page 266 à 269).

Exemple 5.4

Calculez le plus grand commun diviseur de 96 et 28 en utilisant l"algorithme d"Euclide.

Solution :

Exercice 5.5Calculezàlamainleplusgrandcommundiviseurdeaetb.Vérifiezaveclacommande gcd(a, b) de la TI. (a)a=355473etb=3852112. (b)a=504 etb=480, grâce à l"algorithme d"Euclide. (c)a=80 etb=185, grâce à l"algorithme d"Euclide.

Geneviève Savard, ÉTS, 2014

6CHAPITRE 5. ENTIERS, DIVISION ET CONGRUENCES

Exemple 5.5

Exprimez le plus grand commun diviseur de 96 et 28 comme combinaison linéaire de 96 et 28, c"est-

à-dire trouvez des entierssetttels que

pgcd(96,28)=s·96+t·28

Remarque: le théorème de Bézout stipule qu"il est toujours possible de trouver une telle pairesett

peu importe les entiers choisis.

Solution :

Exercice 5.6Calculez le plus grand commun diviseur de 121 et 33 en utilisant l"algorithme d"Eu- clide. Exprimez ensuite le pgcd comme combinaison linéairede 121 et 33.

Idem pour 55 et 81.

5.4 Inverse modulom

Définition 5.5Soientaetbdes entiers etm?Z+. On dit quebestl"inverse deamodulomsi et seulement si ab≡1 (modm) Théorème 5.7[T1, p. 275] Siaetmsont relativement premiers, i.e. pgdc(a,m)=1, alors l"inverse deamodulomexiste etest unique modulom. Onle notea-1. Il ya unseulnombre entiera-1entre

1 etmtel queaa-1≡1 (modm).

Siaetmne sont pas relativement premiers, i.e. pgdc(a,m)?=1, alorsan"estpasinversible modulo m.

Attention: Rosen note

¯al"inverse dea.

Exemple 5.6

Le nombre 4 est-il inversible modulo 9? Le nombre 3 est-il inversible modulo 9? Le nombre 4 est-il inversible modulo 5?

Geneviève Savard, ÉTS, 2014

5.4. INVERSE MODULOM7

Solution :

Le nombre 4 est-il inversible modulo 9? Oui car pgcd(4,9)=1. Quel est son inverse? 7.

En effet,

4·7≡1 (mod 9)

Nous verrons bientôt un algorithme pour obtenir l"inverse.Pour l"instant, concentrons-nous sur la définition. Le nombre 3 est-il inversible modulo 9? Non, car pgcd(3,9)=3?=1. Le nombre 4 est-il inversible modulo 5? Oui, car pgcd(4,5)=1. Quel est son inverse? Lui-même!

En effet

4·4≡1 (mod 5)

Exercice 5.7À partir de la définition d"inverse modulom, par essais et erreurs pour b) à e).

(a) Vrai ou faux? L"inverse de 55 modulo 81 est 28. (b) Trouvez, s"il existe, l"inverse de 2 modulo 3. (c) Trouvez, s"il existe, l"inverse de 2 modulo 4. (d) Trouvez, s"ils existent, l"inverse des nombres 1 à 4 modulo 5. (e) Vrai ou faux? Les congruences sont toutes modulo 4. ab≡0-→(a≡0?b≡0) (f) Résolvez la congruence suivante. 3x≡4 (mod 5)

Comment calculer l"inverse deamodulom?

Si pgcd(a,m)=1, alors a est inversible modulom. Pour déterminer son inverse, on pourrait tester

toutes les possibilités pourballant de 1 àmjusqu"à ce que la congruence suivante soit vérifiée.

ab≡1 (mod(m)

Pour de grandm, cette façon de faire serait peu efficace. Voici une façon de procéder qui est plus

efficace.

1. Exprimer 1 comme combinaison linéaire deaetmen utilisant les décomposition de l"algo-

rithme d"Euclide.

1=sa+tm

2. Passer modulom:

1≡sa(mod(m)

ainsi, en arithmétique modulom,sest l"inverse dea.

Geneviève Savard, ÉTS, 2014

8CHAPITRE 5. ENTIERS, DIVISION ET CONGRUENCES

5.5 Résolution de congruence

Théorème 5.8[Existence de solution d"une congruence] La congruence ax≡b(modm) • possède une solution unique modulomsiaest inversible modulom, c"est-à-dire si pgcd(a,m)=1 • possède plusieurs solutions modulomsi pgcd(a,m)=u?=1 etu|b L"écart entre chacune des solution sera alors de m u. • ne possède aucune solution si pgcd(a,m)=u?=1 etu?|b

Exemple 5.7

Pour quelles valeurs entières dexla congruence suivante est-elle satisfaite?

55x≡2 (mod 81)

Solution :

Pour résoudre l"équation

55x=2

avecx?R, il suffirait de diviser chaque côté de l"égalité par 55, ou demultiplier par 55-1. On aurait

x=2 55.
Pour résoudre les congruences, on ne peut pas diviser mais onpeut multiplier par l"inverse d"un

nombre s"il existe. Ici, rappelons-nous que 55 est inversible modulo 81 et que son inverse est 28, car

55·28=1540≡1 (mod 81).

55x≡2 (mod 81)

55
-1·(55x)≡55-1·2 (mod 81) (55 -1·55)x≡28·2 (mod 81)

1x≡28·2 (mod 81)

x≡56 (mod 81) Les solutions sont donc tous les nombres congrus à 56 modulo 81: ...,x= -106,x= -25,x=56, x=137,x=218, ... On dit que la congruence possède unesolutionuniquemodulo 81.

Geneviève Savard, ÉTS, 2014

5.5. RÉSOLUTION DE CONGRUENCE9

Exemple 5.8

Pour quelles valeurs entières dexla congruence suivante est-elle satisfaite?

2x≡5 (mod 6)

Solution :

J"aimerais isolerxen divisant par 2, c"est-à-dire en multipliant par l"inverse de 2. Mais pgcd(2,6)=

2?=1 donc 2 n"est pas inversible modulo 6. Pour résoudre la congruence, nous pouvons toujours

tester toutes les valeurs possibles pour x:

2·0≡0 2·1≡2 2·2≡4

2·3≡0 2·4≡2 2·5≡4

La congruence 2x≡5 (mod 6) ne possède doncaucune solution.

Remarque: le théorème 5.8 permet de déduire que la congruence ne possède aucune solution sans

avoir à tester les possibilités. En effet, puisque pgcd(2,6)=2?=1 et 2?|5 la congruence ne possède aucune solution.

Exemple 5.9

Pour quelles valeurs entières dexla congruence suivante est-elle satisfaite?

2x≡4 (mod 6)

Solution :

Ici encore, il est impossible d"isolerxen multipliant par l"inverse de 2. En testant toutes les possibili-

tés, on constate que la congruence possèdeplusieurs solutions:

2·0≡0 2·1≡2 2·2≡4

2·3≡0 2·4≡2 2·5≡4

Les solutions sont

x≡2 (mod 6) oux≡5 (mod 6).

Remarquons que l"écart entre les solutions est de 3, soit le résultat de la division de 6 par le pgcd(6,2).

Ainsi, tous les entiers congrus à 2 ou 5 modulo 6 sont solutions de la congruence 2x≡4 (mod 6):

x=2,x=5,x=8,x=11,x=14,x=17, ... x=-1,x=-4,x=-7,x=-10, ...

Remarque: le théorème 5.8 permet de déduire que la congruence possède plusieurs solutions sans

avoir à tester les possibilités. En effet, puisque pgcd(2,6)=2?=1 et 2|4

la congruence possède plusieurs solutions. L"algorithme d"Euclide permet de les générer (détails en

classe).

Geneviève Savard, ÉTS, 2014

10CHAPITRE 5. ENTIERS, DIVISION ET CONGRUENCES

Exercice 5.8Résolvez les congruences suivantes (trouvez toutes les solutions). (a) 9x≡7 (mod 12) (b) 9x≡6 (mod 12) (c) 4x≡6 (mod 10) (d) 15x≡31 (mod 25) (e) 15x≡31 (mod 24) (f) 42x≡12 (mod 90) Théorème 5.9Petit théorème de Fermat. Soitpun nombre premier. Siaest un entier qui n"est pas divisible parp, alors a p-1≡1(modp).

De plus, quelque soit l"entiera,

a p≡a(modp).

5.6 Cryptographie

Nous utiliserons ce tableau lors du cryptage des messages. abcdefghijklmnopqrstuvwxyz

À suivre...

Geneviève Savard, ÉTS, 2014

quotesdbs_dbs47.pdfusesText_47

[PDF] mathématiques discrètes pdf

[PDF] mathématiques discrètes pour l'informatique

[PDF] Mathématiques Dm 4éme

[PDF] mathématiques dm 5

[PDF] Mathematiques dm n1

[PDF] Mathématiques DM pour le 18/09/2015

[PDF] Mathematiques dur besoins de vous

[PDF] mathématiques ecriture scientifque urgent c pour demin g controle SVP

[PDF] mathématiques en économie

[PDF] mathématiques en économie-gestion pdf

[PDF] mathematiques en factorisation ^^

[PDF] mathematiques en geoétrie cned 3eme

[PDF] Mathématiques en option ES (terminale) Matrices

[PDF] MATHEMATIQUES enquete

[PDF] mathématiques enquete policiere