数论基础知识
/*
引理:

若a | b
-->
存在一整数k满足b = k * a



若存在一整数k满足b = k * a
-->
a | b



若gcd(a, b) = c
-->
c | a && c | b

*/

重点:
/*

1.如果 a | b 且b | c，那么a | c
证:
a | b && b | c
-->
b = k1 * a && c = k2 * b
-->
c = k1 * k2 * b
-->
b | c 毕 !



2.a | b且a | c等价于对任意的x，y，有a | (b * x + c * y)
证:
a | b && a | c
-->
b = k1 * a && c =k2 * a 代入方程
-->
k1 * a * x + k2 * a * y 有公因子a
-->
a | (b * x + c * y) 毕 !



3.设 m != 0，那么a | b等价于(m * a) | (m * b)
证:
a | b
-->
b = k1 * a && m != 0
-->
m * b = m * k1 * a 有公因子m * a
-->
(m * a) | (m * b) 毕 !



4.设整数x和y满足：a * x + b * y = 1，且a | n，b | n，那么(a * b) | n
证:
a | n && b | n && 性质3
-->
a * b | n * b && b * a | n * a && 性质2
-->
(a * b) | (a * n * x + b * n * y) && a * x + b * y = 1
-->
(a * b) | n 毕 !



5.若b = q * d + c，那么d | b的充要条件是d | c
证:
必要性:
d | b
-->
b = k1 * d && b = q * d + c
-->
(k1 - q) * d = c c有公因子d
-->
d | c
充分性:
d | c
-->
c = k1 * d && b = q * d + c
-->
b = q * d + k1 * d
-->
d | b 毕 !



6.对于二元一次不定方程a * x + b * y = c ，a * b != 0 ,有整数解的充要条件为gcd(a, b) | c
证:
必要性:
gcd(a, b) | a && gcd(a, b) | b && 性质2
-->
gcd(a, b) | (a * x + b * y)
-->
gcd(a, b) | c
充分性:
gcd(a, b) = c && gcd(a, b) | a && gcd(a, b) | b
-->
c = k * gcd(a, b) && a = k1 * gcd(a, b) && b = k2 * gcd(a, b)
-->
k1 * x + k2 * y = k
未证完......

*/