Ak (a,p)=1, porom Eulerová veta => aφ(m)≡1(mod m) 0→je súdelitelmá a každým číslom okrom 1
Φ(n)= p-1 ap-1≡1(mod p)
a ≡a(mod p)
ap ≡a(mod p)
(a,p)>1=>(a,p)=p=>p/a=>a≡0(mod p)
a1≡0(mod p)
ap≡a(mod p)
dok. implikáciou 1p≡1(mod p)
zp=(1+1)=1+(p1)+(p2)+...+(pp-1)+1
(pk)= (p-k)! p!k! 1≤K≤1
(pk)≡0(mod p) (p,k)=1
2p≡2(mod p) )p,p-k)=1
ap≡a(mod m)
(a+1)p=ap+(p1)an-1+(p2)ap-2+...+1≡ap+1(mod p)
(a+1)p≡ap+1(mod p)
(a+1)p≡a+1(mod p)
12.Formula pre Eulerovú funkciu
V. nech nєN a n>1 a n=p1α1,pαα2,...,pαkαk – kanonický rozklad. Potom α(n)=m(1-1/p1)(1-1/p2)...(1-1/pk)
dєN (d,n)=1<=> i=1,…,k:pi+d
d≤n N(d)={klema1ak dІn, tak ІN}d|І=n/d
Dôk.rr=d.r1 d.r1{0,d,2d,…,d(n/a-1)}=N(d) ІN(d)І=n/d
Dôk.ІZnІ=n Rn=Zn – (N(p1))υ...υN(pk))
U(n)=ІRnІ=ZnІ-ІN(p1)υ...υN(pk)І=n-ІN(p1)υ...υN(pk)І
Lema2 ІN(p1)υ...υN(pk)І=∑ІN(pk)І - ∑ІN(pi)∩N(pj)І +∑ІN(pi)∩N(pj)∩N(pr)+...+(-1)m+1 ∑ІN(pin)∩...∩N(pim)+...
+(-1)k+1І N(p1)...N(pk)І
Dôk.aєN(pi1...pir)=>aa=>aєN(pi1)∩...∩N(pir)
aєi1)∩...∩N(pir)=>aєN(pi1)∩...∩aєN(pir)=>aaaєN}pi1...pir|
Dôk. vety φ(n)- ІN(p1)υ...υN(pk)І=n-∑ ІN(pi) І+∑ ІN(pi)∩
N(pj)+(-1)m+1∑ ІN(pi1)∩N(pi2)∩...∩N(pim) І+...=n-∑n/pi+∑n/pi1,pi2+∑n/pi1,pi2,pi3+∑n/pi1,...,pim)=n І 1-∑1/pi+∑1/pi1,pi2 –
∑1/pi1,pi2,pi3+ ..