2. Divizibilitate. Numere prime 3. Congruente speciale 4. Conjecturi din teoria numerelor 5. Aplicații 5.1 Triunghiul lui Pascal, congruențe și… [600519]

CONGRUENTE
MODULO N
SI DIVIZIBILITATE

„Numarul este esența
tuturor lucrurilor”
Pitagora

Profesor
coordonator
Luminita Moise
1.Congruențe modulo n
2. Divizibilitate. Numere prime
3. Congruente speciale
4. Conjecturi din teoria numerelor
5. Aplicații
5.1 Triunghiul lui Pascal,
congruențe și numerele prime
5.2 Probleme

1. Congruențe modulo n
 Noțiuni generale .
 DEFINIȚIE .
 Fie m număr natural și a,b două numere întregi. Spunem că
 a ≡ b(mod m) dacă m divide a -b.

 PROPOZIȚIE
 Fie m număr 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) .
 PROPOZIȚIE . 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 congruențe
(S) x  a1 (mod m1)
 x  a2 (mod m2)
………………………………
 x  as (mod ms)
are soluție unică modulo M= m1 m2… ms.

De ce sunt studiate numerele
prime ?
– sunt numere monolit, cărămizi pe
care se construiește tabloul
numerelor;
– problemele referitoare la ele au
enunțuri ce pot fi înțelese de
amatori, chiar dacă demonstrațiile
necesită tehnici speciale;
– istoria matematicii abundă în
afirmații, probleme cu numere unele
dovedite adevărate, altele false și
unele chiar nerezolvate.
1.Divizibilitate. Numere prime

Divizibilitate în mulțimea
numerelor naturale
Teorema lui Euclid

Teoremă: Mulțimea numerelor prime este
infinită

Demonstrația 1 :
Utilizăm metoda reducerii la absurd .
Dacă ar fi doar un număr finit p1 , p2 , pn de numere
prime, atunci numărul 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
obținut o contradicție.

Șirul numerelor prime mai mici de
5000

Șirul numerelor prime are
goluri de lungime oricât 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 împărțirii 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,
numărul mai mic este scăzut
din cel mai mare, până când
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
 mulțimea {an+b | n ε N*}
 conține o infinitate de numere prime.

CONGRUENȚE SPECIALE .
TEOREMA ( WILSON ).
Dacă p este număr prim, atunci
 ( p −1)!≡ −1(mod p) .

MICA TEOREMA A LUI FERMAT .
Fie p număr prim și a ε Z, p nu divide a .
Atunci, a p−1 ≡1 (mod p) .

O generalizare a teoremei lui Fermat a fost
dată de Euler
Indicatorul lui Euler sau funcția lui Euler se
notează cu φ (n) -unde n este un număr natural
nenul – și
 φ (n) reprezintă numărul de numere mai mici
decât 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
Cuvântul conjectură provine de la latinescul conjectura
= ipoteză, prezumție, opinie bazată pe aparențe
În acord cu Hilbert (autorul termenului de conjectură)
se înțelege prin conjectură acea problemă deschisă
care poate furniza arhitectura unei teorii în matematică
(sau o direcție nouă) sau avansarea unui nou domeniu
EXEMPLU
Ultima conjectură a lui Fermat (cunoscută ca Marea
teoremă a lui Fermat) a fost că ecuația xn+yn=zn
pentru n≥3 nu are soluții în Z \{0}și s -a demonstrat în
1994 de către matematicianul englez Andrew Wiles.

Există o infinitate de numere prime
Mersenne ?
 Înțelegem prin număr prim Mersenne , numărul 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 numărul descoperit in 2008 are
 12 978 189 de cifre (GIMPS, PrimeNet)


Numere perfecte
Există o infinitate de numere perfecte ?
Se înțelege prin număr perfect, un
număr natural egal cu suma divizorilor
săi mai puțin el însuși. 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 , 22 ,23, 24, …, 2p-1, s,2s, 22 s, 23 s, 24 s, …,2p-1s}
Suma divizorilor lui n este:

Sn =1 +2 +22 +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ă totuși 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 număr 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

Aplicații
Să se arate că 23 divide numărul 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 = 3∙3 22 + 5∙5 22 + 15∙15 22
 3∙1 + 5∙1 + 15∙1 (mod 23)  23( mod 23) 
 0 ( mod 23)
Deci n se divide la 23

Aplicații
1.Triunghiul lui Pascal, congruen țe și numerele
prime Triunghiul lui Pascal
 Creăm mereu câte o
nouă linie punând în
extremități 1 și
adunând cele două
numere aflate în
stânga și în dreapta.

Triunghiul lui Pascal modulo p , cu p
num ăr 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. Câmpan – 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/
