数论(证明)

1. 同余

1.1 同乘性

\({\displaystyle a\equiv b{\pmod {m}}}\)
\({\displaystyle c\equiv d{\pmod {m}}}\)
则 \({\displaystyle a*c\equiv b*d{\pmod {m}}}\)

证明

\({a = k_1m+x}\) ; \({b = k_2m+x}\)
\({c = k_3m+y}\) ; \({d = k_4m+y}\)
\({a*c = k_1k_3m^2+k_1my+k_3mx+x*y}\) ; \({b*d = k_2k_4m^2+k_2my+k_4mx+y*x}\)
\({a*c {\pmod m} = x*y}\) ; \({b*d {\pmod m} = x*y}\)
\({\displaystyle a*c\equiv b*d {\pmod m}}\)

1.2 同除性

\({\displaystyle a*p\equiv b*p{\pmod {m}}}\)
当且仅当 \(p\) 与 \(m\) 互质时 , \({\displaystyle a\equiv b{\pmod {m}}}\)一定成立

证明

因为

\({\displaystyle a*p\equiv b*p{\pmod {m}}}\)

所以

\((a-b)*x*p=m*y\) \((x,y \in N^*)\)

所以

$(a-b)*x = m * y/p $ \((x,y \in N^*)\)

若 \(m\) 与 \(p\) 互质, 则 \(y\) 必整除 \(p\) ,满足系数为整数. 否则,由于 \(p\) 与\(m\) 有公因数,且这个公因数一定不是 \(y\) 的因数, 所以 \(y/p\) 不是整数,所以不成立.

2. 扩展欧几里得及求通解

求通解