Teorema themelore e aritmetikës

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ë:

Teorema e faktorizimit unik u vertetua nga Gauss-i dhe u publikua ne librin e tij Disquisitiones Arithmeticae ne vitin 1801

$$\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}<p_{2}<\cdots <p_{k}$, 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{alignedat}{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{alignedat}}$

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\cdot 10)]\cdot [(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)]\equiv [-1]\cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1{\pmod {11}}.$

Funksioni $\varphi$ i Ojler-it (Euler-it)

Pikturë e Leonhard Euler -it, matematicient, fizicient, astronon, inxhinier nga Zvicrra

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}<p_{2}<\cdots <p_{k}$ dhe përçdo $i$ vlen $k_{i}\geq 1$. 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-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=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:

$\qquad 7^{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

Pierre de Fermat, autori i Teoremës së vogël të 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 \mathbb {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 \mathbb {Z}$ (në këtë rast $k=9$).

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