Teorema themelore e aritmetikës

## Teorema Fundamentale e Aritmetikës 
-i dhe u publikua ne librin e tij *Disquisitiones Arithmeticae* ne vitin 1801]]
Ne matematike, **Teorema Fundamentale e Aritmetikës**, e njohur ndryshe si **Teorema e Faktorizimit Unik**, thot se secili numër i plotë më i madh se numri 1 mund të reprezentohet në mënyre unike si produkt i fuqive të numrave të thjeshtë. Pra çdo numër *n* nga bashkesia e numrave natyrorë mund të shprehet si më poshtë:\qquad n = p_1^{s_1}\cdot p_1^{s_2}\cdot p_3^{s_3}\cdot \ldots \cdot p_k^{s_k}= \prod_{j=1}^{k} p_j^{s_j}, 
ku  p_i 
-te janë numra të thjeshtë të ndryshëm, për të cilët vlen   p_1, dhe  s_i 
-të janë numra natyrorë.

Nga kjo teoremë mund të nxerrim dy përfundime: secili numër nga bashkesia e numrave natyrorë mund të shprehet si produkt i disa numrave të tjerë dhe se kjo paraqitje edhe unike. 

**Shembuj:**

\qquad 126
 = 2 \cdot 3^2 \cdot 7

\qquad 1200 = 2^4 \cdot 3 \cdot 5^2 

\qquad 4230 = 2 \cdot 3^2 \cdot 5 \cdot 47

Teorema Fundamentale e Aritmetikës është një ndër arsyet kryesore se pse numri 1 nuk konsiderohet numër i thjeshtë. Sepse nëse 1 do të futej në bashkesinë e numrave të thjeshtë atëherë reprezentimi i numrave nuk do të ishte i vetëm (për shembull, 2 = 2 \cdot 1 = 2 \cdot 1 \cdot 1 = \ldots).

### Operacionet aritmetike 
Reprezentimi kanonik i prodhimit, pjestuesit më të madh të përbashkët, dhe shumëfishit më të vogël të përbashkët të dy numrave a 
 dhe b 
 mund të shprehet me anë të paraqitjes kanonike të vet numrave a dhe b:

** \qquad \begin{alignat}{2}
 a\cdot b & = 2^{a_1+b_1}3^{a_2+b_2}5^{a_3+b_3}7^{a_4+b_4}\cdots
   && = \prod p_i^{a_i+b_i},\\
 pmmp(a,b) & = 2^{\min(a_1,b_1)}3^{\min(a_2,b_2)}5^{\min(a_3,b_3)}7^{\min(a_4,b_4)}\cdots
   && = \prod p_i^{\min(a_i,b_i)},\\
 shmvp(a,b) & = 2^{\max(a_1,b_1)}3^{\max(a_2,b_2)}5^{\max(a_3,b_3)}7^{\max(a_4,b_4)}\cdots
   && = \prod p_i^{\max(a_i,b_i)}.
 \end{alignat}**

### Lema e Euklidit 
Nëse p është numër i thjeshtë dhe a, b janë numra nga bashkësia e numrave të plotë, të tillë që   p\mid a \cdot b  , atëherë   p\mid a   ose   p\mid b.

Pohimi i mësipërm njihet si Lema e Euklidit, dhe është çelsi për vërtetimin e Teoremës Fundamentale te Aritmetikës. Këtë lemë ai e publikoi në librin e tij Elementet, libri i VII - të.

**Lemë:** Nëse p, p_1, p_2, \ldots , p_k 
 janë numra të thjeshtë dhe   p\mid p_1 \cdot p_2 \cdot p_3 \ldots \cdot p_k , atëhere p=p_i
 për ndonjë i.

### Teorema e Wilson-it 
Ne algjebër dhe teori të numrave, **Teorema e Wilson-it** thot se një numër natyror  n, i cili është më i madh se 1, është numër i thjeshtë, atëherë dhe vetëm atëherë, nëse prodhimi i të gjithë numrave natyrorë më të vegjël se  n është për një më i vogel se një shumëfish i numrit  n. Pra, nëse  n plotëson barazimin e mëposhtëm:

\qquad (n-1)!\ \equiv\; -1 \pmod n

ku (n - 1)! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot(n - 1). Pra, një numër është i thjeshtë, atëherë dhe vetëm atëherë, kur (n-1)!+1  plotëpjestohet nga n.

**Shembull:** Për n=11
,

\qquad 10! = [(1\cdot10)]\cdot[(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8)]  \equiv [-1]\cdot[1\cdot1\cdot1\cdot1]  \equiv -1 \pmod{11}.

## Funksioni  \varphi i Ojler-it (Euler-it) 
Në teorinë e numrave, funksioni  \varphi(n) i Euler-it, numëron numrat e plotë pozitiv më të vegjël se  n të cilët janë relativisht të thjeshtë në lidhje me  n. Ky funksion shënohet me shkronjën greke  \varphi  (lexohet fi), dhe në disa literatura mund të gjindet i shënuar me shkronjën greke  \phi. Me fjalë të tjera  \varphi(n) është numri i numrave të plote  k, të tillë që  k është në intervalin  1\leq k\leq n, dhe për të cilët vlenë se pjestuesi më i madh i përbashkët i  k dhe  n është 1. Pra,  pmmp(n, k)=1.

Shembull: Për  n=9, kemi:

 \qquad pmmp(9, 1)=1;      pmmp(9, 2)=1;       pmmp(9, 3)=3;      pmmp(9, 4)=1;      pmmp(9, 5)=1;     

 \qquad pmmp(9, 6)=3;      pmmp(9, 7)=1;       pmmp(9, 8)=1;      pmmp(9, 9)=3

Në këtë rast kemi 6 numra të plotë pozitv më të vegjël se 9 të cilët janë relativisht të thjeshtë me 9. Ata numra janë: 1, 2, 4, 5, 7, 8. Pra, përfundojmë se  \varphi(9)=6.

### Formula e prodhimit te Ojler-it (Euler-it) 
Funksioni  \varphi(n) i Euler-it mund të shprehet me anë të formulës:

 \qquad \varphi(n) =n \left(1- \frac{1}{p_1} \right)\left(1- \frac{1}{p_2} \right) \cdots\left(1- \frac{1}{p_r} \right)=n \prod_{p\mid n} \left(1-\frac{1}{p}\right).

një verzion ekuivalent i shprehjes së mësipërme është:

 \qquad \varphi(n) = p_1^{k_1-1}(p_1{-}1)\,p_2^{k_2-1}(p_2{-}1)\cdots p_r^{k_r-1}(p_r{-}1), 

ku  n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} dhe   p_1, p_2,\ldots,p_r
 janë numra të thjeshtë të ndryshëm nga njeri-tjetri të cilët e plotpjestojnë  n.

**Pohim:** Funksioni   \varphi(n) i Euler-it është **funksion multiplikativ**, që nënkupton se nëse   pmmp(n, m)=1, atëherë vlen barazimi  \varphi(n\cdot m)=\varphi(n)\cdot \varphi(m).

**Vërtetimi**: Nga Teorema Fundamentale e Aritmetikës dimë se nëse  n>1, atëherë egziston shprehja unike  n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}
, ku   p_1, p_2, \ldots p_k janë numra të thjeshtë për të cilët vlen  p_1 dhe përçdo  i vlen  k_i\geq1. Duke e përdorur në menyrë të përseritur vetinë multiplikative të funksionit  \varphi, kemi:

 \qquad \begin{array} {rcl}
\varphi(n)&=& \varphi(p_1^{k_1})\, \varphi(p_2^{k_2}) 
\cdots\varphi(p_r^{k_r})\\[.1em]
&=& p_1^{k_1-1} (p_1-1)\, p_2^{k_2-1} (p_2-1) \cdots p_r^{k_r-1}(p_r-1)\\[.1em]
&=& p_1^{k_1} \left(1- \frac{1}{p_1} \right) p_2^{k_2} \left(1- \frac{1}{p_2} \right) \cdots p_r^{k_r}\left(1- \frac{1}{p_r} \right)\\[.1em]
&=& p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \left(1- \frac{1}{p_1} \right) \left(1- \frac{1}{p_2} \right) \cdots \left(1- \frac{1}{p_r} \right)\\[.1em]
&=&n \left(1- \frac{1}{p_1} \right)\left(1- \frac{1}{p_2} \right) \cdots\left(1- \frac{1}{p_r} \right).
\end{array}

Vërtetimi mund të bëhet në menyrë alternative duke përdorur parimin e përfshirjes/mospërfshirjes.

**Shembull:** Për  n=20, kemi:

 \qquad \varphi(20)=\varphi(2^2 5)=20\,(1-\tfrac12)\,(1-\tfrac15)
=20\cdot\tfrac12\cdot\tfrac45=8.

Në mënyrë ekuivakente alternative kemi shprehjen:   \varphi(20) = \varphi(2^2 5^1)= 2^{2-1}(2{-}1)\,5^{1-1}(5{-}1) = 2\cdot 1\cdot 1\cdot 4 = 8. 

Me të vertetë, kemi numrat 1, 3, 7, 9, 11, 13, 17, 19  te cilët janë të plotë pozitiv më të vegjël se 20, dhe të cilët janë relativisht të thjeshtë me numrin 20.

### Teorema e Ojler-it (Euler-it) 
Në teorinë e numrave, **Teorema e Euler-it** (e njohur ndryshe si **Teorema e Fermat-Euler-it**), thot se nëse ** a** dhe  n janë dy numra të plotë pozitiv të cilët janë relativisht të thjeshtë në lidhje me njëri-tjetrin, atëherë  a e ngritur në fuqinë  \varphi(n) është kongruente me 1 modulo  n. Pra:

 \qquad a^{\varphi (n)} \equiv 1 \pmod{n},

ku  \varphi(n) është funksioni i Euler-it.

**Shembull**: Cili është numri më i vogël pozitiv i cili është kongruent me  7^{222} në lidhje me modulin 10?

Vërejmë se 7 është relativisht i thjeshtë në lidhje me numrin 10. Pra, vlen   pmmp(10, 7)=1. Poashtu lehtë mund të shohim se   \varphi(10)=4. Tani, nga **Teorema e Euler-it** kemi:

 \qquad7^4 \equiv 1 \pmod{10};             7^{222} \equiv 7^{4 \times 55 + 2} \equiv (7^4)^{55} \times 7^2 \equiv 1^{55} \times 7^2 \equiv 49 \equiv 9 \pmod{10}.

Pra, përfundojmë se numri më i vogel pozitiv i cili është kongruent me  7^{222} në lidhje me modulin 10 është numri 9.

**Rëndesia dhe përdorimi**: Teorema e Euler-it është një nga shtyllat ndërtuese të kriptosistemit RSA, i cili përdoret për enkriptimin dhe sigurimin e të dhënave të cilat qarkullojnë në internet. Teorema e Euler-it në këtë rast e merr numrin  n që të jetë produkt i dy numrave të mëdhenj të thjeshtë, dhe siguria e sistemit RSA bazohet pikërisht në faktin se faktorizimi i numrave të thjeshtë të tillë është shumë veshtirë të bëhet (madje nga kompjuterët e rëndomt në shumicën e rasteve është i pamundur).

### Teorema e vogël e Fermat-it 
Teorema e vogël e Fermat-it thot se, nëse p është një numër i thjeshtë, atëherë për secilin numër të plotë a, numri a^p-a është një shumëfish i numrit p. Pra, a^p-a=p\cdot k. Teorema e vogël e Fermat-it, e shprehur me anë të modulit: 

\qquad a^p \equiv a \pmod p.

**Shembull**: Për a=2
  dhe  p=7,  

\qquad a^p-a=128-2=126=7\cdot 18 =p\cdot k             , ku k\in \Z (në këtë rast k=18).

Në qoftë se a nuk plotëpjestohet nga p, Teorema e vogël e Fermat-it merr këtë formë: nëse p është një numër i thjeshtë, atëherë për secilin numër të plotë a, numri a^{p-1}-1 është një shumefish i numrit p. E shprehur me anë të modulit:

\qquad a^{p-1} \equiv 1 \pmod p.

**Shembull**: Për a=2
  dhe  p=7,  

\qquad a^{p-1}-1=64-1=63=7\cdot 9 =p\cdot k             , ku k\in \Z (në këtë rast k=9).

Teorema e vogël e Fermat-it është një rast specifik i Teoremës së Euler-it.

## Referime