Mica teorema a lui Fermat.

Daca p este un numar prim si a este un numar natural atunci ap ? a(mod p).
Mai mult daca ? (p ? a) (p nu il divide pe a ) exista exponenti mai mici d astfel incat ad-1 ?0 (mod p) si
d? (p-1) (d divide pe p-1).
Mica teorema a lui Fermat arata ca daca p este un numar prim nu exista o baza a ? p , unde (a,p)=1, astfel incat ap-1 -1 are un rest modulo p diferit de 0. Daca o asemenea baza ar exista , p ar fi un numar compus . Cu toate acestea negasirea unui rest modulo p nenul in mica teorema a lui Fermat nu implica faptul ca p este prim.
Un numar cu proprietatea ca satisface mica teorema a lui Fermat , pentru o baza netriviala si care se stie ca este un numar compus se numeste probabil prim.
Mica teorema a lui Fermat poate fi un criteriu pentru a verifica daca un numar este prim.

Tabel cu cele mai mici numere pseudoprime p pentru primele 100 de baze a.

a p a p A p A p a P
2 341 22 69 42 205 62 63 82 91
3 91 23 33 43 77 63 341 83 105
4 15 24 25 44 45 64 65 84 85
5 124 25 28 45 76 65 112 85 129
6 35 26 27 46 133 66 91 86 87
7 25 27 65 47 65 67 85 87 91
8 9 28 45 48 49 68 69 88 91
9 28 29 35 49 66 69 85 89 99
10 33 30 49 50 51 70 169 90 91
11 15 31 49 51 65 71 105 91 115
12 65 32 33 52 85 72 85 92 93
13 21 33 85 53 65 73 111 93 301
14 15 34 35 54 55 74 75 94 95
15 341 35 51 55 63 75 91 95 141
16 51 36 91 56 57 76 77 96 133
17 45 37 45 57 65 77 247 97 105
18 25 38 39 58 133 78 341 98 99
19 45 39 95 59 87 79 91 99 145
20 21 40 91 60 341 80 81 100 153
21 55 41 105 61 91 81 85

Un numar natural compus n?? se numeste Fermat pseudoprim relativ la baza a daca acesta verifica relatia an ? a mod n.
Se mai poate spune ca numerele pseudoprime satisfac Mica Teorema a lui Fermat , unde n este un numar prim.
Daca p este un numar prim si a este un numar natural atunci ap ? a(mod)p.
Pentru orice a numar natural , unde a?2 exista o infinitate de numere Fermat pseudoprime relative la acea baza.
Numerele lui Carmichael sunt numere pseudoprime relative la orice baza, se mai numesc si absolute pseudoprime.
Urmatorul tabel contine numarul de numere pseudoprime Fermat (psf), pseudoprime Euler-Jacobi (ejpsp), puternice pseudoprime (psp), si numere Carmichael (NC) , care sun mai mici decat puterile lui 10 , incepand cu 1, pana la 13.
Un numar este pseudoprim Euler-Jacobi relativ la o baza a daca (a,n)=1 , unde raportul (a/n) satisface conditia (a/n) ? a (n-1)/2 (mod n).
Un numar este puternic pseudoprim relative la baza a daca n-1 = d?2s (d numar impar) , astfel incat ad ? 1 (mod n) sau ad?2^r ? -1 (mod n) , unde r = 0,1,…,s-1.

10n psf ejpsp psp NC
101 0 0 0 0
102 0 0 0 0
103 3 1 0 1
104 22 12 5 7
105 78 36 16 16
106 245 114 46 43
107 750 375 162 105
108 2057 1071 488 255
109 5597 2939 1282 646
1010 14884 7706 3291 1547
1011 38975 20417 8607 3605
1012 101629 53332 22407 8241
1013 264239 124882 58892 19279

Un numar natural n se numeste numar Carmichael daca n este un numar pseudoprim care satisface mica teorema a lui Fermat ( an-1 – 1 ? 0 (mod n) ) pentru fiecare a care satisface conditia (a,n)=1, cu 1?a?n.
Numerele Carmichael nu pot fi determinate afland numerele pseudoprime folosind mica teorema a lui Fermat (ele sunt pseudoprime la orice baza). Totusi daca (a,n)?1, congruenta micii teoreme a lui Fermat este cateodata nenula, astfel ca un numar Carmichael se poate identifica fiind un numar pseudoprim.
Numerele lui Carmichael satisfac de asemenea si criteriul lui Korselt (n divide an – a pentru orice numar intreg a daca n nu este patrat perfect si (p-1) ?n?p -1 pentru orice divisor p al lui n).
Orice solutie a problemei totient a lui Lehmer trebuie sa fie un numar Carmichael.
Se pune intrebarea daca exista numere compuse n astfel incat ?(n)?(n-1) , unde ?(n) este functia totient. Nu se cunosc asemenea numere.Totusi un astfel de numar ar trebui sa fie un numar Carmichael deoarece pentru fiecare element b dintre intregii (mod n) , ord(b,n)??(n)?n-1 , deci bn-1 ? 1 (mod n) si astfel n este un numar Carmichael. In 1932 , Lehmer arata ca numarul n trebuie sa fie impar sis a nu fie patrat perfect si ca numarul factorilor primi distincti d(n) ai lui n trebuie sa satisfaca relatia d(n)?7. Aceasta s-a extins la d(n)?11.
Cele mai mici numere Carmichael avand 3,4,… factori sunt : 561 = 2?11?17, 41041 = 7?11?13?41, 825265 , 321197185,…
Numerele lui Carmichael au cel putin trei factori primi .Pentru numerele Carmichael cu exact trei factori primi , odata cu specificarea unuia din factorii primi , exista doar un numar finit de numere Carmichael care pot fi construite. Pentru numere Carmichael cu k factori primi exista un numar finit de numere cu cel putin k-2 factori din cei specificati.
Numerele de forma (6k+1)(12k+1)(18k+1) sunt numere Carmichael daca fiecare dintre factori este prim (Korselt).
Se poate vedea acest lucru deoarece N ? (6k+1)(12k+1)(18k+1) = 1296k3 + 396k2 + 36k + 1, N-1 este un multiplu al lui 36k , si cel mai mic multiplu comun dintre 6k , 12k , si 18k este 36k , deci aN-1 ? 1 modulo fiecare din numerele prime 6k+1 , 12k+1 si 18k+1, deci si aN-1 ? 1 modulo produsulor acestora. Primele cateva astfel de numere Carmichael corespund lui
k = 1,6,35,45,51,55,56,…, si sunt 1729 , 294409 , 56052361 ,118901521, …
Fie C(n) numarul numerelor Carmichael maimici decat un numar dat n. Atunci pentru orice n suficient de mare C(n)?n2/7 (Alford,1994) , ceea ce demonstreza ca exista un numar infinit de numere Carmichael .S-a dovedit si existenta unei limite superioare
C(n) ? n exp(- (ln n ln ln ln n)/(ln ln n))
(R.G.E.Pinch).
Numerele Carmichael au urmatoarele proprietati:
1. Daca un numar prim p divide numarul Carmichael n , atunci n ? 1 (mod p – 1) implica
n ? p (mod p(p-1)).
2. Orice numar Carmichael nu este patrat perfect.
3. Un numar pseudoprim n care nu este patrat perfect este un numar Carmichael daca acesta divide numitorul numarului lui Bernoulli Bn-1.
(numerele lui Bernoulli Bn sunt o serie de numere rationale cu semn care pot fi definite de formula
x/(ex -1 ) = ? Bnxn/n! , de la 0 la ? )

Cele mai cunoscute numere Carmichael avand un numar dat de factori sunt prezentate in urmatorul tabel :

Factori Numar Descoperitor
3 10200 Dubner
4 2467 Caldwell si Dubner
5 1015 Caldwell si Dubner
6 827 Caldwell si Dubner

Conditia Carmichael :
Un numar n satisface conditia Carmichael daca (p-1) | (n/p – 1) pentru toti divizorii primi p ai lui n. Aceasta este echivalenta cu urmatoarea conditie : (p-1) | (n-1) pentru fiecare divisor prim p al lui n.

Emilia Tereanu
U.B.B Info. Gr. 226
emi_dia2000@yahoo.com