Teorema Fundamentale e Aritmetikes ^[1] [ Redakto | Redakto nepermjet kodit ]

Ne matematike , Teorema Fundamentale e Aritmetikes , e njohur ndryshe si Teorema e Faktorizimit Unik , thot se secili numer i plote me i madh se numri 1 mund te reprezentohet ne menyre unike si produkt i fuqive te numrave te thjeshte . Pra cdo numer n nga bashkesia e numrave natyrore mund te shprehet si me poshte:

ku ${\displaystyle p_{i}}$-te jane numra te thjeshte te ndryshem, per te cilet vlen ${\displaystyle p_{1}<p_{2}<\cdots <p_{k}}$, dhe ${\displaystyle s_{i}}$-te jane numra natyrore. ^[2]

Nga kjo teoreme mund te nxerrim dy perfundime: secili numer nga bashkesia e numrave natyrore mund te shprehet si produkt i disa numrave te tjere dhe se kjo paraqitje edhe unike.

Shembuj:

${\displaystyle \qquad 126=2\cdot 3^{2}\cdot 7}$

${\displaystyle \qquad 1200=2^{4}\cdot 3\cdot 5^{2}}$

${\displaystyle \qquad 4230=2\cdot 3^{2}\cdot 5\cdot 47}$

Teorema Fundamentale e Aritmetikes eshte nje nder arsyet kryesore se pse numri 1 nuk konsiderohet numer i thjeshte. Sepse nese 1 do te futej ne bashkesine e numrave te thjeshte atehere reprezentimi i numrave nuk do te ishte i vetem (per shembull, ${\displaystyle 2=2\cdot 1=2\cdot 1\cdot 1=\ldots }$).

Operacionet aritmetike [ Redakto | Redakto nepermjet kodit ]

Reprezentimi kanonik i prodhimit, pjestuesit me te madh te perbashket , dhe shumefishit me te vogel te perbashket te dy numrave ${\displaystyle a}$ dhe ${\displaystyle b}$ mund te shprehet me ane te paraqitjes kanonike te vet numrave a dhe b:

${\displaystyle \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 [ Redakto | Redakto nepermjet kodit ]

Nese ${\displaystyle p}$ eshte numer i thjeshte dhe ${\displaystyle a,b}$ jane numra nga bashkesia e numrave te plote, te tille qe ${\displaystyle p\mid a\cdot b}$ , atehere ${\displaystyle p\mid a}$ ose ${\displaystyle p\mid b}$.

Pohimi i mesiperm njihet si Lema e Euklidit, dhe eshte celsi per vertetimin e Teoremes Fundamentale te Aritmetikes. Kete leme ai e publikoi ne librin e tij Elementet , libri i VII - te.

Leme: Nese ${\displaystyle p,p_{1},p_{2},\ldots ,p_{k}}$ jane numra te thjeshte dhe ${\displaystyle p\mid p_{1}\cdot p_{2}\cdot p_{3}\ldots \cdot p_{k}}$ , atehere ${\displaystyle p=p_{i}}$ per ndonje ${\displaystyle i}$.

Teorema e Wilson-it ^[3] [ Redakto | Redakto nepermjet kodit ]

Ne algjeber dhe teori te numrave , Teorema e Wilson-it thot se nje numer natyror ${\displaystyle n}$, i cili eshte me i madh se 1, eshte numer i thjeshte, atehere dhe vetem atehere, nese prodhimi i te gjithe numrave natyrore me te vegjel se ${\displaystyle n}$ eshte per nje me i vogel se nje shumefish i numrit ${\displaystyle n}$. Pra, nese ${\displaystyle n}$ ploteson barazimin e meposhtem:

${\displaystyle \qquad (n-1)!\ \equiv \;-1{\pmod {n}}}$

ku ${\displaystyle (n-1)!=1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)}$. Pra, nje numer eshte i thjeshte, atehere dhe vetem atehere, kur ${\displaystyle (n-1)!+1}$ plotepjestohet nga ${\displaystyle n}$.

Shembull: Per ${\displaystyle n=11}$,

${\displaystyle \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 ${\displaystyle \varphi }$ i Ojler-it (Euler-it) ^[4] [ Redakto | Redakto nepermjet kodit ]

Ne teorine e numrave, funksioni ${\displaystyle \varphi (n)}$ i Euler -it, numeron numrat e plote pozitiv me te vegjel se ${\displaystyle n}$ te cilet jane relativisht te thjeshte ne lidhje me ${\displaystyle n}$. Ky funksion shenohet me shkronjen greke ${\displaystyle \varphi }$ (lexohet fi), dhe ne disa literatura mund te gjindet i shenuar me shkronjen greke ${\displaystyle \phi }$. Me fjale te tjera ${\displaystyle \varphi (n)}$ eshte numri i numrave te plote ${\displaystyle k}$, te tille qe ${\displaystyle k}$ eshte ne intervalin ${\displaystyle 1\leq k\leq n}$, dhe per te cilet vlene se pjestuesi me i madh i perbashket i ${\displaystyle k}$ dhe ${\displaystyle n}$ eshte 1. Pra, ${\displaystyle pmmp(n,k)=1}$.

Shembull: Per ${\displaystyle n=9}$, kemi:

${\displaystyle \qquad pmmp(9,1)=1}$; ${\displaystyle pmmp(9,2)=1}$; ${\displaystyle pmmp(9,3)=3}$; ${\displaystyle pmmp(9,4)=1}$; ${\displaystyle pmmp(9,5)=1}$;

${\displaystyle \qquad pmmp(9,6)=3}$; ${\displaystyle pmmp(9,7)=1}$; ${\displaystyle pmmp(9,8)=1}$; ${\displaystyle pmmp(9,9)=3}$

Ne kete rast kemi 6 numra te plote pozitv me te vegjel se 9 te cilet jane relativisht te thjeshte me 9. Ata numra jane: 1, 2, 4, 5, 7, 8. Pra, perfundojme se ${\displaystyle \varphi (9)=6}$.

Formula e prodhimit te Ojler-it (Euler-it) [ Redakto | Redakto nepermjet kodit ]

Funksioni ${\displaystyle \varphi (n)}$ i Euler-it mund te shprehet me ane te formules:

${\displaystyle \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).}$

nje verzion ekuivalent i shprehjes se mesiperme eshte:

${\displaystyle \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 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$ dhe ${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$ jane numra te thjeshte te ndryshem nga njeri-tjetri te cilet e plotpjestojne ${\displaystyle n}$.

Pohim: Funksioni ${\displaystyle \varphi (n)}$ i Euler-it eshte funksion multiplikativ , qe nenkupton se nese ${\displaystyle pmmp(n,m)=1}$, atehere vlen barazimi ${\displaystyle \varphi (n\cdot m)=\varphi (n)\cdot \varphi (m)}$.

Vertetimi : Nga Teorema Fundamentale e Aritmetikes dime se nese ${\displaystyle n>1}$, atehere egziston shprehja unike ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$, ku ${\displaystyle p_{1},p_{2},\ldots p_{k}}$ jane numra te thjeshte per te cilet vlen ${\displaystyle p_{1}<p_{2}<\cdots <p_{k}}$ dhe percdo ${\displaystyle i}$ vlen ${\displaystyle k_{i}\geq 1}$. Duke e perdorur ne menyre te perseritur vetine multiplikative te funksionit ${\displaystyle \varphi }$, kemi:

${\displaystyle \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}}}$

Vertetimi mund te behet ne menyre alternative duke perdorur parimin e perfshirjes/mosperfshirjes.

Shembull: Per ${\displaystyle n=20}$, kemi:

${\displaystyle \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.}$

Ne menyre ekuivakente alternative kemi shprehjen: ${\displaystyle \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 te vertete, kemi numrat 1, 3, 7, 9, 11, 13, 17, 19 te cilet jane te plote pozitiv me te vegjel se 20, dhe te cilet jane relativisht te thjeshte me numrin 20.

Teorema e Ojler-it (Euler-it) [ Redakto | Redakto nepermjet kodit ]

Ne teorine e numrave, Teorema e Euler-it (e njohur ndryshe si Teorema e Fermat-Euler-it ), thot se nese ${\displaystyle a}$ dhe ${\displaystyle n}$ jane dy numra te plote pozitiv te cilet jane relativisht te thjeshte ne lidhje me njeri-tjetrin, atehere ${\displaystyle a}$ e ngritur ne fuqine ${\displaystyle \varphi (n)}$ eshte kongruente me 1 modulo ${\displaystyle n}$. Pra:

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

ku ${\displaystyle \varphi (n)}$ eshte funksioni i Euler-it.

Shembull : Cili eshte numri me i vogel pozitiv i cili eshte kongruent me ${\displaystyle 7^{222}}$ ne lidhje me modulin 10?

Verejme se 7 eshte relativisht i thjeshte ne lidhje me numrin 10. Pra, vlen ${\displaystyle pmmp(10,7)=1}$. Poashtu lehte mund te shohim se ${\displaystyle \varphi (10)=4}$. Tani, nga Teorema e Euler-it kemi:

${\displaystyle \qquad 7^{4}\equiv 1{\pmod {10}}}$; ${\displaystyle 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, perfundojme se numri me i vogel pozitiv i cili eshte kongruent me ${\displaystyle 7^{222}}$ ne lidhje me modulin 10 eshte numri 9.

Rendesia dhe perdorimi : Teorema e Euler-it eshte nje nga shtyllat ndertuese te kriptosistemit RSA , i cili perdoret per enkriptimin dhe sigurimin e te dhenave te cilat qarkullojne ne internet. Teorema e Euler-it ne kete rast e merr numrin ${\displaystyle n}$ qe te jete produkt i dy numrave te medhenj te thjeshte, dhe siguria e sistemit RSA bazohet pikerisht ne faktin se faktorizimi i numrave te thjeshte te tille eshte shume veshtire te behet (madje nga kompjuteret e rendomt ne shumicen e rasteve eshte i pamundur).

Teorema e vogel e Fermat-it ^[5] [ Redakto | Redakto nepermjet kodit ]

Teorema e vogel e Fermat-it thot se, nese ${\displaystyle p}$ eshte nje numer i thjeshte, atehere per secilin numer te plote ${\displaystyle a}$, numri ${\displaystyle a^{p}-a}$ eshte nje shumefish i numrit ${\displaystyle p}$. Pra, ${\displaystyle a^{p}-a=p\cdot k}$. Teorema e vogel e Fermat-it, e shprehur me ane te modulit:

${\displaystyle \qquad a^{p}\equiv a{\pmod {p}}.}$

Shembull : Per ${\displaystyle a=2}$ dhe ${\displaystyle p=7}$,

${\displaystyle \qquad a^{p}-a=128-2=126=7\cdot 18=p\cdot k}$ , ku ${\displaystyle k\in \mathbb {Z} }$ (ne kete rast ${\displaystyle k=18}$).

Ne qofte se a nuk plotepjestohet nga p, Teorema e vogel e Fermat-it merr kete forme: nese ${\displaystyle p}$ eshte nje numer i thjeshte, atehere per secilin numer te plote ${\displaystyle a}$, numri ${\displaystyle a^{p-1}-1}$ eshte nje shumefish i numrit ${\displaystyle p}$. E shprehur me ane te modulit:

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

Shembull : Per ${\displaystyle a=2}$ dhe ${\displaystyle p=7}$,

${\displaystyle \qquad a^{p-1}-1=64-1=63=7\cdot 9=p\cdot k}$ , ku ${\displaystyle k\in \mathbb {Z} }$ (ne kete rast ${\displaystyle k=9}$).

Teorema e vogel e Fermat-it eshte nje rast specifik i Teoremes se Euler-it.

Referencat [ Redakto | Redakto nepermjet kodit ]