laborator13-teorianumerelor

MATEMATIC DISCRET __________________________________________________ Laborator Nr. 13

1

TEORIA NUMERELOR

Problema nr. 1 Un numr este perfect dac este egal cu suma divizorilor si, n afara lui nsui.

Exemplu: 6 = 1+2+3 sau 28 = 1+2+4+7+14. Explicai de ce ( )122 k1k este numr perfect dac ( )12k este numr prim.

Problema nr. 2 S se demonstreze urmtoarea teorem: Teorem: Dac cmmdc(a,b) = 1, atunci cmmdc(a+b, a-b) =1 sau 2. Problema nr. 3 Dac a i b sunt dou numere ntregi atunci cmmdc al celor dou numere are

urmtoarea proprietate (printre altele): cmmdc(a,b) = cmmdc(b, a mod b)

unde a mod b este restul mpririi numrului a la b. Aplicarea repetat a acestei proprieti att timp ct obinem un rest diferit de zero constituie algoritmul lui Euclid de determinare a cmmdc. Folosind proprietatea indicat mai sus s se calculeze cmmdc(1147, 899) Problema nr. 4 Algoritmul lui Euclid ne permite calcularea valorii celui mai mare divizor comun a dou numere a i b. Ne intereseaz i combinaia liniar corespunztore. Pentru determinarea acesteia vom face apel la algoritmul extins al lui Euclid. Teorema mpririi afirm c: oricare ar fi dou numere ntregi a i b, exist o pereche unic (q0, r0) de numere ntregi asociat numerelor a i b astfel nct: a=q0b+r0 r0=a q0b q0 se numete ctul, iar r0 este restul mpririi lui a la b. Se observ c putem exprima restul mpririi ca o combinaie liniar a numerelor considerate (a i b). Aplicm algoritmul lui Euclid de determinare a cmmdc i obinem n continuare: b = q1r0 + r1 r1 = b q1r0 = = b q1(a q0b) = = -q1a + (1+q1q0)b Se observ c i acest al doilea rest a putut fi exprimat ca o combinaie liniar a celor dou numere luate n discuie. Procedeul se continu pn se obine un rest egal cu zero. Cmmdc este atunci ultimul rest nenul pentru care putem determina i combinaia liniar corespunztoare a numerelor iniiale. Exemplu: S se calculeze cmmdc i combinaia liniar corespunztoare pentru numerele 259 i 70. Se noteaz x = a = 259 i y = b = 70. Se construiete urmtorul tabel:

x y x mod y = x - qb

259 70 49 = 259 3 70


2

70 49 21 =70 1 49 = 70 1(259370) = =-1259 + 470

49 21 7 =49-221 = (1259-370)2(-1259+470) = =3259 - 1170

21 7 0

Putem scrie cmmdc(259, 70) = 7 = 3259 - 1170 Constatm c acest algoritm ne permite calcularea combinaiei liniare ntregi asociate celui mai mare divizor comun. Aplicaii ale algoritmului extins al lui Euclid. Rezolvarea unei clase de ecuaii diofantice. Putem folosi acest algoritm la rezolvarea ecuaiilor diofantice liniare. Acestea sunt ecuaii de forma: ax + by = c (1) Ecuaiile de acest tip au soluii numai dac c este un multiplu al cmmdc al numerelor a i b. Deducem de aici o condiie de existen a soluiilor ecuaiei (1). De exemplu, ecuaia 259x + 70y = 7 are ca soluii valorile x = 3 i y = -11, adic tocmai coeficienii combinaiei liniare corespunztoare cmmdc(259, 70). n cazul general, dac cmmdc(a,b) = d, atunci rezolvarea ecuaiei diofantice (1) are mai multe etape:

a) Verificarea existenei soluiei ecuaiei b) determinarea soluiei ecuaiei

ax + by = d (2)

c) o soluie a ecuaiei (2) este se noteaz cu d0x i d0y

d) o soluie a ecuaiei (1) este atunci

dc

xx d00 = dc

yy d00 = (3) e) ecuaia (1) nu are o singur soluie, ci o mulime de soluii. Mulimea soluiilor

ecuaiei (1) este dat de relaiile:

tdb

xx 0 +=

tda

yy 0 = unde t este un numr ntreg. S gseasc soluiile ecuaiilor

a) 23x+29y=7 b) 3456x+246y=73 c) 436x-393y=5

Problema nr. 5 n buctrie nu exist ceas, dar tiu c:


3

a) robinetul picur o dat la 54 s dup ce l-am nchis. b) prjitorul de pine d o felie de pine prjit la fiecare 84 s. Trebuie s prjesc un ou exact 141 secunde. Mi-am propus s pun prjitorul n

priz i s nchid robinetul exact n acelai timp. Voi ncepe prjitul oului cnd din robinet picur pictura D i s nchei prjitul cnd prjitorul arunc felia P. Care sunt valorile lui D i P necesare pentru ca acest plan s funcioneze?

Problema nr. 6 n grdin am un lac. n interiorul lacului sunt n pietre aranjate n cerc. O

broasc st pe una din pietre. Oricum ar sri broasca, ea aterizeaz la k pietre mai departe, n sensul acelor de ceasornic, de piatra pe care se afl (0


4

n general, invers multiplicativ exist pentru fiecare numr real (cu excepia

numrul 0). De exemplu, inversul multiplicativ al lui 3 este 31

pentru c:

13331

3 1 == Pe de alt parte, n mulimea numerelor ntregi nu exist invers multiplicativ. De exemplu, 11 nu poate fi nmulit cu un alt numr ntreg astfel nct rezultatul s fie egal cu 1. Totui, invers multiplicativ exist atunci cnd lucrm modulo un numr prim (cnd folosim relaia de congruen corespunztoare unui numr prim). De exemplu, dac lucrm modulo 5, atunci 3 este un invers multiplicativ al lui 7 pentru c:

( )5mod137 Observaie: toate numerele congruente cu 3 modulo 5 sunt de asemenea invers multiplicativ pentru 7. De exemplu: ( ))5mod187 . Singura excepie sunt acele numere care sunt congruente cu 0 modulo 5 (adic multiplii lui 5) care nu au invers multiplicativ aa cum 0 nu are invers n mulimea numerelor reale. Lemma 1. Dac p este numr prim i k nu este un multiplu al lui p, atunci k are un invers multiplicativ modulo p. Demonstraie. deoarece p este numr prim, el are numai doi divizori: 1 i p. Pentru c k nu este un multiplu al lui p, trebuie s avem cmmdc(p,k) = 1. De aici rezult c exist o combinaie liniar de p i k egal cu 1:

1=+ tksp Rearanjnd termenii vom avea:

tksp = 1 Rezult c ( )tkp 1| (din definiia divizibilitii) i astfel

( )ptk mod1 prin definiia congruenei. Astfel, t este inversul multiplicativ al lui k. Simplificare

Tot n mulimea numerelor reale putem simplifica termenii ntr-o nmulire. Cu alte cuvinte, dac tim c kmkm 21 = atunci putem simplifica prin k i concluziona c

21 mm = (n condiiile n care 0k ). n general simplificarea nu este valid n aritmetica modular. De exemplu,

( )6mod3432 dar simplificarea cu 3 conduce la concluzia fals c ( )6mod42 . Faptul c termenii multiplicativi nu pot fi simplificai este cea mai semnificativ diferen ntre congruen i egalitatea obinuit. Totui, aceast diferen dispare dac lucrm cu o relaie de congruen modulo p, n care p este numr prim i, n acest caz, simplificarea este valid. Lemma 2. Fie p un numr prim i k un numr care nu este multiplu al lui p. Atunci

( )pbkak mod implic ( )pba mod . Demonstraiei. Multiplicm ambii termeni ai congruenei cu inversul multiplicativ

1k . Corolar. Presupunem c p este un numr prim i k nu este multiplu al lui p. Atunci secvena:


5

( )( ) ( )( ) ( )( )pkrempkrempkrem ,1,,,2,,1 K este o permutare a secvenei:

( )1,,2,1 pK Demonstraie. Secvena de resturi conine 1p numere. Pentru c ki nu este

divizibil cu p pentru i = 1, 2, ..., p 1, toate aceste resturi sunt din mulimea {1, 2, ..., p-1} prin definiia restului mpririi. Mai mult, toate resturile sunt diferite: nu exist dou numere din aceast mulime care s fie congruente modulo p i aplicnd Lemma 2 ( ( ) ( )pjipkjki modmod ). Astfel, secvena de resturi trebuie s conin toate numerele de la 1 la p-1 ntr-o ordine oarecare.

Exemplu, p = 5 i k = 3. Atunci secvena: ( )( ) ( )( ) ( )( ) ( )( )44 344 2144 344 2144 344 2144 344 21

2413

5,34,5,33,5,32,5,31==== remremremrem

este o permutare a secvenei 1, 2, 3, 4.

Mica teorem a lui Fermat O alt cale de a determina inversul multiplicativ al unui numr ntreg pornete de

la mica teorem a lui Fermat. Fie p un numr prim i k un numr care nu este multiplu al lui p. Atunci:

( )pk p mod11 Putem acum determina inversul multiplicativ folosind mica teorem a lui Fermat. Presupunem c p este un numr prim i considerm un numr k care nu este multiplu al numrului p . Atunci, prin mica teorem a lui Fermat, putem scrie:

( )pkk p mod12 Astfel 2pk trebuie s fie inversul multiplicativ al lui k . De exemplu, presupunem c dorim s calculm inversul multiplicativ al lui 6 modulo 17. Trebuie s calculm pentru aceasta ( )17,615rem i vom folosi proprietile relaiei de congruen modulo 17 astfel (toate congruenele de mai jos sunt considerate a fi modulo 17):

( )( )

36241666666

16466

4266

2366

24815

2248

2224

2

Deci, ( )17mod3615 , adic ( ) 317,615 =rem . Deci 3 este inversul multiplicativ al lui 6 modulo 17 ntruct

( )17mod163 n general, dac lucrm cu relaia de congruen modulo p, unde p este un numr prim, gsirea unui invers multiplicativ ncercnd fiecare valoare ntre 1 i p-1 necesit aproape p operaii. Cu toate acestea, abordarea de mai sus cere numai ( )plog2 operaii. n cazul n care se cunosc att mesajul original (m), ct i mesajul criptat, folosind a doua variant a codului Turing, (m*) n care: - la codare avem

( )pmkm mod* - la decodare avem: ( )pkmremm ,1* =


6

Dac avem ambele mesaje la dispoziie se poate calcula: ( ) ( ) ( ) ( )pkpkmpmkmpmkremmmm pppp modmodmod, 122*2

Astfel se poate determin valoarea lui k i se poate decripta orice mesaj. RSA (MIT 1977) Destinatarul are att o cheie secret, pe care o pstreaz la el, ct i o cheie public pe care o distribuie ct mai mult posibil. Transmitorul cripteaz mesajul folosind cheia public, apoi se decripteaz mesajul folosind cheia privat. RSA nu lucreaz modulo un numr prim, ci modulo produsul a dou numere foarte mari. Definiie. Dou numere ntregi a i b sunt prime ntre ele (relativ prime) dac i numai dac au cel mai mare divizor comun al lor egal cu 1 (cmmdc(a,b) = 1). Rezultatele descrise n Lemma 1 i Lemma 2 (care lucreaz cu numere prime) pot fi extinse i pentru numere prime ntre ele. Lemma 3. Fie n un ntreg pozitiv. Dac numrul k este prim cu n, atunci exist un ntreg 1k astfel nct:

( )nkk mod11 Corolar. Fie n un ntreg pozitiv i k un numr prim cu n. Dac

( )nbkak mod atunci

( )nba mod

laborator13-teorianumerelor

Documents