前置芝士
欧几里得算法
欧几里得算法又称辗转相除法，用于计算两个正整数的最大公约数。
定理： \(gcd(a,b)=gcd(b,a\) \(mod\) \(b)\) \((\) 设 \(a>b\) 且 \(r=a\) \(mod\) \(b,r\) 不为 \(0)\)
证明1：
设 \(a=kb+r\) \((a,b,k,r\) 皆为正整数，且 \(r<b)\)，则 \(r=a\) \(mod\) \(b\)。
假设 \(d\) 是 \(a,b\) 的一个公约数，记作 \(d|a,d|b\)。
而 \(r=a-kb\)，两边同时除以 \(d\)，\(r/d=a/d-kb/d=m\)，由等式右边可知 \(m\) 为整数，因此 \(d|r\)。
因此d也是b,a mod b的公约数。
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。
进而d|a。因此d也是a,b的公约数。
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
乘法逆元的定义
对于两个数 \(a\)，\(p\)，若 \(gcd(a,p)=1\) 则一定存在另一个数 \(b\)，使得 \(ab≡1(mod\) \(p)\)，并称此时的 \(b\) 为 \(a\) 关于 \(1\) 模 \(p\) 的乘法逆元。我们记此时的 \(b\) 为 \(inv(a)\) 或 \(a^{-1}\)。