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^{\phi (n)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}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{m}\mathrm{o}\mathrm{d}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{m}\mathrm{o}\mathrm{d}10).$

Në përgjithësi vlen :

$a^b\equiv a^{b\mathrm{m}\mathrm{o}\mathrm{d}\phi (n)}(\mathrm{m}\mathrm{o}\mathrm{d}n)a,b,n\in \mathbb{N}\wedge \mathrm{g}\mathrm{g}\mathrm{T}(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