Teorema e Eulerit

Teorema e Eulerit, ndryshe Teorema Euler-Fermat, ka marrë emrin për nder të Leonhard Euler dhe Pierre de Fermat. Teorema në fjalë është :

$a^{\varphi (n)}\equiv 1\,(\mathrm {mod} \,n)$

Ku PMP(a,n)= 1, ndryshe thuhet që a dhe n janë relativisht të thjeshtë, si dhe φ(n) është Funksioni i Eulerit φ. Funksioni i Eulerit φ(n) tregon numrin e numrave më të vegjël se n dhe që janë relativisht të thjeshtë me të.

Për një numër të thjeshtë p vlen φ(p) = p-1.

Shembull

Cila është shifra e fundit e numrit 7²²², ose cili numër është 7²²² moduli 10 ?

Sëpari ne shohim që pmp(7,10) = 1 dhe që φ(10) = 4. Pra përdorim Teoremën e Eulerit

$7^{\,4}\,\equiv 1\,(\mathrm {mod} \,10)$

nga ku kemi :

$7^{222}=7^{\,4\cdot 55+2}=(7^{\,4})^{55}\cdot 7^{2}\equiv 1^{55}\cdot 7^{2}=49\equiv 9\,(\mathrm {mod} \,10).$

Në përgjithësi vlen :

$a^{b}\equiv a^{b\,\mathrm {mod} \,\varphi (n)}\,(\mathrm {mod} \,n)\qquad a,b,n\in \mathbb {N} \wedge \mathrm {ggT} (a,n)=1$

Përdorimi

Funksioni i Eulerit praktikisht përdoret në kriptologji, informatikë etj. Për më tepër shikoni rreth sistemit RSA.

Literaturë

• Harald Scheid: Zahlentheorie, Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6
• Zahlenthoerie nach einer Vorlesung von Prof. Heinz Mitsch, Wintersemester 2006