数论

被薄纱了/kk

授课老师：南京大学-朱富海教授

20230710

裴蜀定理

对于给定不全为零的整数的 \(a,b\) 一定存在一对整数 \(x,y\) 满足 \(ax+by=gcd(a,b)\) 。

证明：

1. \(a==0\) \(or\) \(b==0\) 显然成立；
2. 设 \(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\) 。

证明：

1. \(a==0||b==0\) 。。。

中国剩余定理（CRT）

给定 \(m_1,m_2,...,m_k\) 和 \(r_1,r_2,...,r_k\) ，求解：