【数学】数论定理-1

定理1(除法定理)
对于$\forall a\in N,\forall n\in N^{+}$,$\exists$唯一$q,r\in N$,满足$0\leq r< n$,且$a=qn+r$。

称$q=\lfloor a/n\rfloor$为除法的,值$r=a\mod n$,为除法的余数。$n | a$当且仅当$a\mod n == 0$。
根据整数模$n$的余数,可以将所有整数分成$n$个等价类。包含整数$a$的模$n$等价类为:$[a]_{n}={a+kn,k\in Z}$。

定理2
如果$\forall a,b\in N,a\neq 0,b\neq 0$,则$\gcd(a,b)$是$a$与$b$的线性组合集{${ax+by|x,y\in Z}$}的最小正元素。

推论3
对于$\forall a,b\in N$,如果$d|a$且$d|b$,则$d|\gcd(a,b)$。

推论4
对于所有$a,b\in N$以及$\forall n\in N^{+}$,有$\gcd(an,bn)=n\gcd(a,b)$

推论5
对于$\forall n,a,b\in N^{+}$,如果$n|ab$且$\gcd(a,n)=1$,则$n|b$。

定理6
对于$\forall a,b,p$,如果$\gcd(a,p)=1$且$\gcd(b,p)=1$,则$\gcd(ab,p)=1$。

定理7
对于所有素数$p$和所有$a,b\in N$,如果$p|ab$,则$p|a$或$p|b$。

定理8
唯一分解定理

定理9(gcd递归定理)
对于$\forall a\in Q,\forall b\in N^{+}$,$\gcd(a,b)=\gcd(b,a\mod b)$。