1. 整除的基本性质

1
a|b  ------>   b=qa
  1. 如果 b|a 且 a|b 则 b=a 或 b=-a
  2. 如果 a|b 且 b|c 则 a|c
  3. 如果 c|a 且 c|b 则 c|ua+vb 其中u ,v是整数

2. 辗转相除法

1
2
3
4
5
y=x*q+r
y=x,x=r
......
y=x*q
x就是最大公因子

3.互素

img