請問一題[同餘]

a 是蝦咪？

若取 \(a=M\)，則不論 \(k\) 為何整數， \(ak\equiv0\pmod{M}\)。

若 \(gcd(a,M)=1\)，則存在整數 \(p,q\) 使得 \(ap+Mq=1\Rightarrow ap\equiv1\pmod{M}\)

取 \(p\equiv k\) 且 \(0\leq k<M\)，則 \(ak\equiv1\pmod{M}\) 且 \(0\leq k<M\)。