CONGRUENTE

MODULO N

SI DIVIZIBILITATE

Numarul este esena tuturor lucrurilor

Pitagora

Profesor

coordonator

Luminita Moise 1.Congruene modulo n 2. Divizibilitate. Numere prime

3. Congruente speciale

4. Conjecturi din teoria numerelor

5. Aplicaii 5.1 Triunghiul lui Pascal,

congruene i numerele prime 5.2 Probleme

1. Congruene modulo n

Noiuni generale. DEFINIIE.

Fie m numr natural i a,b dou numere ntregi. Spunem c

a b(mod m) dac m divide a-b.

PROPOZIIE

Fie m numr natural i a,b,c ntregi cu

a b(mod m) . Atunci

1) a + c b + c (mod m)

2) a - c b - c (mod m)

3) ac bc (mod m) .

PROPOZIIE. Dac a b (mod m) i c d ( mod m) , atunci:

1) a c b d (mod m)

2) ac bd (mod m)

TEOREMA

(LEMA CHINEZEASCA A RESTURILOR )

Fie s numere naturale

m1 ,m2 ,...,m s astfel c pentru orice i j

( mi ,mj )=1.

Atunci sistemul de congruene

(S) x a1 (mod m1)

x a2 (mod m2)

....................................

x as (mod ms)

are soluie unic modulo M= m1 m2... ms.

De ce sunt studiate numerele prime ? - sunt numere monolit, crmizi pe care se construiete tabloul numerelor; - problemele referitoare la ele au enunuri ce pot fi nelese de amatori, chiar dac demonstraiile necesit tehnici speciale; - istoria matematicii abund n afirmaii, probleme cu numere unele dovedite adevrate, altele false i unele chiar nerezolvate.

1.Divizibilitate. Numere prime

Divizibilitate n mulimea

numerelor naturale

Teorema lui Euclid

Teorem: Mulimea numerelor prime este infinit

Demonstraia 1 : Utilizm metoda reducerii la absurd . Dac ar fi doar un numr finit p1 , p2 , pn de numere

prime, atunci numrul m = 1+p1 p2 pn nu se divide la niciunul din numerele pi , i =1,n. Deci este prim sau are un divizor prim diferit de numerele date. Am obinut o contradicie.

irul numerelor prime mai mici de

5000

irul numerelor prime are

goluri de lungime orict de

mare.

(n+1)! + 2 se divide la 2;

(n+1)! + 3 se divide la 3;

(n+1)! + 4 se divide la 4;

..................

(n+1)! + (n+1) se divide la n+1

Tabloul numerelor prime

Spirala numerelor prime

Spirala numerelor prime

Teorema numerelor prime

ALGORITMUL LUI EUCLID

Proprietate:

Fie a i b doua numere naturale , a b , atunci a) ( a,b) = (b,a-b)

b) Dac r este restul mpririi lui a la b atunci (a,b) = (b.r)

Exemplu. Avem (1547; 560) = 7, deoarece:

1547 = 2 560 + 427 560 = 1 427 + 133 427 = 3 133 + 28 133 = 4 28 + 21 28 = 1 21 + 7 21 = 3 7

(252 , 105) = (105,147) = = (105,42) = = (42,63) = = (42,21) = = (21,21) = 21 Un segment reprezinta numarul 21 La fiecare pas, numrul mai mic este sczut din cel mai mare, pn cnd unul dintre numere ajunge s fie zero

TEOREMA

Fie a; b N i d = (a; b). Atunci exista u; v din Z astfel ncat

d = au + bv

Exemplu.

Stim deja c (1547; 560) = 7. Atunci: 7 = 28- 1 21 = 28 - 1 (133 - 4 28) = = 5 28 - 1 133 = = 5 (427 - 3 133) - 1 133 = 5 427 - 16 133 = = 5 427 - 16 (560 - 1 427) = 21 427 - 16 560 = = 21 (1547 - 2 560) - 16 560 = 21 1547 - 58

560.

Consecin si

TEOREMA lui Dirichlet

Fie a; b N. Atunci (a; b) = 1 dac i numai dac exista u; v Z astfel ncat

1 = au + bv.

TEOREMA. (Dirichlet) Dac a, b N*

iar (a, b)=1, atunci

mulimea {an+b | n N*}

conine o infinitate de numere prime.

CONGRUENE SPECIALE.

TEOREMA ( WILSON ).

Dac p este numr prim, atunci

( p 1)! 1(mod p) .

MICA TEOREMA A LUI FERMAT.

Fie p numr prim i a Z, p nu divide a . Atunci, a p1 1 (mod p) .

O generalizare a teoremei lui Fermat a fost

dat de Euler

Indicatorul lui Euler sau funcia lui Euler se

noteaz cu (n) -unde n este un numr natural nenul - i

(n) reprezint numrul de numere mai mici dect n i prime cu acesta.

TEOREMA LUI EULER.

Fie a Z, n N* cu (a,n)=1.

Atunci, a (n) 1 (mod n) .

4. Conjecturi din teoria numerelor

Cuvntul conjectur provine de la latinescul conjectura = ipotez, prezumie, opinie bazat pe aparene

n acord cu Hilbert (autorul termenului de conjectur) se nelege prin conjectur acea problem deschis care poate furniza arhitectura unei teorii n matematic (sau o direcie nou) sau avansarea unui nou domeniu

EXEMPLU

Ultima conjectur a lui Fermat (cunoscut ca Marea teorem a lui Fermat) a fost c ecuaia xn+yn=zn pentru n3 nu are soluii n Z \{0}i s-a demonstrat n 1994 de ctre matematicianul englez Andrew Wiles.

Exist o infinitate de numere prime

Mersenne ? nelegem prin numr prim Mersenne, numrul prim de

forma:

2 p-1

Dintre ultimile numere descoperite sunt

M44 : 232.582.657 - 1.

a fost descoperit in 6 sept 2006 si are 9.808.358 de cifre.

M47 =2 42 643 801-1, are 12 837 064 cifre si a fost

descoperit in 2009

M46 = 243 112 609- 1 numrul descoperit in 2008 are

12 978 189 de cifre (GIMPS, PrimeNet)

Numere perfecte

Exist o infinitate de numere perfecte ?

Se nelege prin numr perfect, un numr natural egal cu suma divizorilor si mai puin el nsui. Deci suma divizorilor sai naturali este 2n

De exemplu: 6 = 1+2+3;

28 = 1+2+4+7+14;

Olimpiada de matematica , faza pe municipiu Bucuresti , 24 aprilie 2010

Un numar natural n se numeste perfect daca suma divizorilor sai naturali este 2n Demonstrati ca numerele 6, 28, si 496 sunt numere perfecte (Pitagora) Daca p este numar prim si 2p-1 este tot numar prim, demonstrati ca numarul n=2p-1(2p-1) este numar perfect (Euclid)

n=2p-1(2p-1)= 2p-1s Multimea divizorilor lui n este: Dn={1 ,2 , 2

2 ,23, 24, , 2p-1, s,2s, 22 s, 23 s, 24 s, ,2p-1s} Suma divizorilor lui n este: Sn =1 +2 +2

2 +23+ 24+ + 2p-1+ s+2s+ 22 s+ 23 s+24 s+ +2p-1s = =( 1 +2 +22 +23+ 24+ + 2p-1) +s ( 1 +2 +22 +23+ 24+ + 2p-1)= =(2p-1) +s(2p-1)= (2p-1)(1+s) =(2p-1)(1+2p-1)= (2p-1) 2p)= (2p-1) 2p-12=2n

Exist totui o infinitate de numere prime Fermat ?

Exist o infinitate de numere

prime gemene ? Numerele prime p, q se zic gemene,

dac |p - q| = 2. De exemplu (3;5); (5;7); (17;19); (29;31)

Conjectura lui Goldbach

orice numr par > 6 este suma a dou numere prime. De exemplu:

12 = 5 +7, 18 = 5 + 13 = 7 + 11

n anul 2000, editura Faber&Faber a oferit un

premiu de 1 000 000 de dolari pentru

rezolvarea conjecturii lui Goldbach

Aplicaii

S se arate c 23 divide numrul n= 3 23+ 5 23 + 15 23

Rezolvare

Se aplic Mica teorem a lui Fermat: ap-1 1 (mod p),

daca p numar prim si a nu se divide la p

pentru p=23

n=323+ 523 + 1523 = 33 22 + 55 22 + 1515 22

31 + 51 + 151 (mod 23) 23( mod 23) 0 ( mod 23)

Deci n se divide la 23

Aplicaii 1.Triunghiul lui Pascal, congruene i numerele

prime Triunghiul lui Pascal

Crem mereu cte o nou linie punnd n extremiti 1 i adunnd cele dou numere aflate n

stnga i n dreapta.

Triunghiul lui Pascal modulo p , cu p

numr prim

4. Bibliografie

[1] D.L.Moise , B. Bogdan, D.Druta, Algoritmi, numere si fractali, editura Printech, 2007

[2] Michael F.Barnsley Fractals every where, Second Edition, Academic Press Professional, 1993.

[3] Florica T. Cmpan Vechi i nou n matematic [4] Luminita Dominica Moise - Portofoliul clasei a VI a editura Printech, 2008 [5] Matematica de ieri i azi Conflict sau continuitate, editura Printech, 2007 [6] Matematica de ieri i de azi Probleme vechi n actualitate , editura

Printech,2008

http://primes.utm.edu/mersenne/

http://www.youtube.com/watch?v=PtsrAw1LR3E

http://ro.wikipedia.org/wiki/Indicatorul_lui_Euler

http://fractali.webs.com/