Përdoruesi:G.Kolaj/sandbox

Algoritmi i Euklidit

Artikulli ka të bëjë më gjetjen e plotpjesëtuesit më të madh të përbashkët, ky artikull është nga teoria e numrave.

Algorimit i Euklidit është një forme e gjetjes së p.m.m.p(plotpjesetuesit me të madh të përbashkët). Për dallim nga gjetja e p.m.m.p me faktorizimin e numrave të thjeshtë, algoritmi Euklidit bazohet në pjesëtimin e dy numrave derisa të gjëndet një numër me i vogël. Shembull, supozojmë së kemi p.m.m.p(287, 91), ku kjo mund të shprehet edhe si p.m.m.p(91, 14) si dhe p.m.m.p(14, 7) ku nga këto shohim së plotëpjesëtuesi më i madh i përbashkët është 7 (sepse 7 plotëpjesëton numrin 14 po edhe numrin 7 duke mos lënë asnjë mbetje).

Përmes algoritmit të Euklidit mund të gjenden edhe koeficientat e Bezout. Shembull mund të jetë për 287 dhe 91 është (-6) dhe 19 (saktesisht 267$\times$(-6) dhe 91$\times$19).

Algoritmi i Euklidit ka aplikime të gjëra posaçërisht në Matematika ku përdoret për kriptografi tek krijimi i çelësit publik RSA i cili nevojitet hapi i algoritmit Euklidit.

Procedura e algoritmit të Euklidit

Algoritmi i Euklidit bazohet në reduktimin e dy numrave më të mëdhenj në numra me të vegjël për të gjetur zgjidhjen.

Ai duhet nënshtruar disa hapa.

Algoritmi bazohet nga formula:

$a=b\times q+r$

ku a, b, q dhe r jane elemente të numrave të plotë. Ateherë:

$p.m.m.p(a,b)=p.m.m.p(b,r)$

Shembull:

$p.m.m.p(527,341)$

ku a = 527 dhe b = 341, ateherë nxjerrim multiplikativin e 527 me numrin 341, ku mund të shumëzohet $q_{0}=1$ :

$527=1\times 341+186.$

pastaj nxjerrim multiplikativin e numrit 341 me mbetjen 186, ku mund të shumëzohet $q_{1}=1$:

$341=1\times 186+155.$

ku fitohet mbetja $r_{2}=155$, pastaj nxjerrim multiplikativin e numrit 186 me mbetjen 155, ku mund të shumëzohet $q_{2}=1$:

$186=1\times 155+31.$

ku fitohet mbetja $r_{3}=31$, pastaj nxjerrim multiplikativin e numrit 155 me mbetjen 31, ku mund të shumëzohet $q_{3}=5$:

$155=5\times 31+0.$

algoritmi i Euklidit përfundon kur mbetja është 0, ateherë mund të konkludojmë se p.m.m.p(527, 341) = p.m.m.p(341, 186) = p.m.m.p(186, 155) = p.m.m.p(155, 31) = 31.