ac≡bc(mod m) =>m / bc-ac= c/b-a
m/c(b-a) =>m/b-a =>a≡b(mod m)
9.Úpravy a redukovaný zvyškový systém mod m mєN, tak množinu Zm{0,1,...,m-1}nazyvame úplným zvyškom mod m
V1 ak aєZ a mєN tak existuje rєZm, že a≡r(mod m)
Dôk.Veta o delení so zvyškom a=a1.m+r; rєZm
a≡r(mod m)
nech a≡r1(mod m) r1 єZ
r1≡r(mod m) =>r1=r
Ak mєN, tak množinu Rm={rєZm;(r,m)=1} nazyvame redukovaním zvyškovým systémom mod m
V2 Ak mєZ a (0,m)=1(b,m)=1, tak aj (ab,m)=1
Dôk. ax+my=1 x,yєZ
bx1+my1=1 x1,y1єZ
(ax+my).(bx1+my1)=1
abx x1+axmy1+mybx1+m2yy1=1
abx x1+axmy1+my(bx1+my1)=1
x=x.x1 y=axy1+y(bx1+my1)
ak x+my=1
V3 mєN a r1,r2 єRm. Potom existuje r3єže platí r1.r2≡r3(mod m)
Dôk. (r1;m)=1
(r2;m)=1
(r1,r2,m)=1
r1,r2´mg+r3=>(r3;m)=1=>r3єRm
V4 Ak rєRm, tak existuje práve jedno r´єRm, že platí r,ŕ≡1(mod m)
Dôk. (r,m)=1
ar+bm=1
a=m.q+r´ r´єZm
(m.q+r´)r+vm=1
r´.r+mgr+bm=1=>(r´,m)=1=>r´єRm
r´.r-1=-m.q.r-bm≡0(mpd m)
r´.r ≡1(mod m)
r.r´≡1(mod m)
r.r´1≡r.r´(mod m)
r´1≡r´(mod m)
r´inverzný prvok r mod m, ozmr=1/r (mod m)
10. Eulerová funkcia nєN a n>1 a Rn / redukovaný zvyškový systém tak počet jeho zvyškov označujeme φ(n)= ІRmІ- Eulerová funkcia čísla n
φ(1)=1, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(19)=18, φ(30)=8
Eulerová veta nech mєN a n>1. potom pre každé a єN tak ,že (a,m)=1, platí aφ(m)≡1(mod m)
Dôk. nech Rm={a1….ak}; k=φ(m)
(a,m)=1
(aa1;m)=1
(aa2;m)=1
(aak;m)=1
aa1≡aja(mod m) {aj(1);aj(2),...,aj(k)}єRm
aa2≡aj(2)(mod m)
aak≡ajäk)(mod m)
predpokladáme, že aj(n1)≡aj(n2)
aan1≡aj(n1)(mod m)
aan1≡aj(n2)(mod m)
aan1≡aan2(mod m)
an1≡an2(mod m)
an1≡an2=>n1=n2
teda dokázali sme implikásiu:aj(n1)=aj(n2) =>n1=n2
І{aj(1);...;aj(k)}І=k
{aj(1);…;aj(k)}={a1;…ak}

aa1≡aj(1)(mod m)
aa2≡aj(2)(mod m)
aak≡aj(k)(mod m)
(aa1)...(aak)≡aj(1)...aj(k)(mod m)
aka1...ak≡a1...ak (mod m)
k= φ(m) ak≡1(mod m)
aφ(m)≡1(mod m)
11.Fermatová veta Nech p je prvočíslo. Potom pre každé prirodzené číslo a platí: an≡ a(mod p)
Dôk.