数论
被薄纱了/kk
授课老师：南京大学-朱富海教授
20230710
裴蜀定理
对于给定不全为零的整数的 \(a,b\) 一定存在一对整数 \(x,y\) 满足 \(ax+by=gcd(a,b)\) 。
证明：
- \(a==0\) \(or\) \(b==0\) 显然成立；
- 设 \(gcd(a,b)=d\) ， 即求证存在 \(x,y\) 满足 \(ax+by=d\) ，
等式两边同时除 \(d\) ，即求证存在 \(x,y\) 满足 \(a_1x+b_1y=1\) ，其中 \(a=a_1d,b=b_1d\) 。
由带余除法：
$$① a_1 = q_1b_1 + r_1 , 其中 0 < r_1 < b_1$$
$$② b_1 = q_2r_1 + r_2 , 其中 0 < r_2 < r_1$$
$$③ r_1 = q_3r_2 + r_3 , 其中 0 < r_3 < r_2$$
$$......$$
$$④ r_{n-4} = q_{n-2}r_{n-3} + r_{n-2}$$
$$⑤ r_{n-3} = q_{n-1}r_{n-2} + r_{n-1}$$
$$⑥ r_{n-2} = q_nr_{n-1} + r_n$$
$$⑦ r_{n-1} = q_{n+1}r_n + 1$$
故，由⑦和⑥推出 $$r_{n-2}A_{n-2} + r_{n-1})B_{n-1} = 1$$
再结合⑤推出 $$r_{n-3}A_{n-3} + r_{n-2}B_{n-2} = 1$$
再结合④推出 $$r_{n-4}A_{n-4} + r_{n-3}B_{n-3} = 1$$
$$......$$
再结合③推出 $$r_1A_1 + r_2B_2 = 1$$
再结合②推出 $$b_1A_0 + r_1B_0 = 1$$
再结合①推出 $$a_1x + b_1y = 1$$
证毕。
欧几里得引理
对与每个 \(p|ab\) ，一定存在 \(p|a\) \(or\) \(p|b\) 。
证明：
- \(a==0||b==0\) 。。。
中国剩余定理（CRT）
给定 \(m_1,m_2,...,m_k\) 和 \(r_1,r_2,...,r_k\) ，求解：