頭盔:本人學識唔深，有咩錯講出黎聽，廢事教錯其他膠登仔

modulus
其實係一個講餘數既題目
舉個小學雞都識既例子先
31/7 =4......3
即係講緊31除7餘4啦，咁用mod既方式寫，我地就會寫成:
31=3 (mod 7)

easy
下面係幾條規矩:
a=b mod n
c=d mod n
咁a+c=b+d mod n
a*c=b*c mod n
但係要記住加減可以掉轉，但係乘除就唔得 (唔信自己試下 )
如果想除佢既，假設:
a=b mod n
a*c = 1 mod n
咁我地就搵到要點樣"除"a:只要乘多個c上去就得

stage 2:
一個質數，有乜咁特別?就係每個質數p都係得1同自己做因數(factor)
又係小學雞都識
換言之，由2到p-1,入面全部數都係同p互質既，無一個數可以整除p
我地係呢度define一個function:
phi(n) = number of integers coprime with n from 1 to n-1 inclusive,where for 1, we consider it coprime with all n.
呢個就係euler tortient function
咁就有一個問題喇:咁同質數有乜撚關係啊屌?
我地由依度好容易睇到既就係:
phi(p)=p-1 for all primes.

stage 3: fermat's little theorem費馬小定理
for all primes p, a^(p-1) = 1 (mod p)
咁你又問喇:屌，咁撚複雜既，又up乜鳩啊?
其實呢，個定理就講緊for 全部質數p, a coprime with p,a既p-1次方除p餘1
如果各位膠登仔夠精神既話，其實唔洗我講都應該明點解 大家可以先試下寫低a,a*2,a*3...,a*(p-1)
我地將呢個set入面每個element mod p就會得到一個1 to p-1 inclusive既set
點解呢?引用上面條rule,assume ac=1 mod p:
將入面每個element 乘以c再mod,我地就會得到1到p-1

再用一次multiplication rule乘晒入面既野:
a^(p-1) *(p-1)! = (p-1)! (mod p)
呢個時候就可以約左兩邊既(p-1)!佢
我地就得到費馬小定理

講住咁多先，有心情再打euclidean algorithm, definition of groups and rings, discrete log problem and rsa