互质.md

若$a,b$除$\pm1$外无其它公因数，则我们说$a$和$b$互质

于是，$a$和$b$互质，等价于$a$和$b$的最高公因数为$\pm1$

定理

1. $\pm1$和任意整数互质

2. 由这个定理可知，$a$与$b$互质，等价于1可表示为$a$和$b$的线性组合，即存在整数$s$和$t$使$1=sa+tb$

3. 若$a$和$b$互质，且$a\mid bc$，则有$a\mid c$

   证明：因为$a$和$b$互质，所以存在$s$和$t$使得$1=sa+tb$，两边乘上$c$

   $$ c=sac+tbc $$ 因为$a\mid sac$，而且$a\mid tbc$（由$a\mid bc$得），所以$a\mid c$（由整除的性质5得）

4. 若$b$和$a_1,a_2,\cdots,a_n$都互质，则$b$和$a_1a_2\cdots a_n$互质

   证明：可知$1=s_ib+t_ia_i$，把所有这样的式子乘起来，能化成下面的形式

   $$ 1=Sb+Ta_1a_2\cdots a_n $$ 于是得证啦～ ^740f56

5. 若$m_1,m_2,\cdots,m_k$两两互质而且都整除$a$，则$m_1m_2\cdots m_k\mid a$，

   证明

   • 若$b\mid a$，$c\mid a$，且$b,c$互质，则$bc\mid a$ 证明：存在整数$p$使得$a=pb$，于是$c\mid pb$，因为$b,c$互质，由定理$3$可知，$c\mid p$，于是存在整数$q$使得$p=qc$，于是$a=bcq$，于是$bc\mid a$
   • 于是，$k=2$时，$m_1m_2\mid a$
   • 假设$k=n-1$时成立，$k=n$时，$m_n$与$m_1,m_2,\cdots,m_{n-1}$互质，由定理$4$可知，$m_n$与$m_1m_2\cdots m_{n-1}$互质，于是$m_1m_2\cdots m_n\mid a$

6. $2^p-1$和$2^q-1$互质等价于$p$和$q$互质

   证明：

   • 充分性：假设$p$和$q$不互质，设$p=ax$，$q=bx$，$2^{ax}-1$和$2^{bx}-1$有公因数$2^x-1$，矛盾

   • 必要性：$gcd(p,q)=1$，不妨设$p\ge q$

     于是

     $$ \begin{align} p&=l_1q+r_1\\ q&=l_2r_1+r_2\\ &\cdots\\ r_{n-2}&=l_nr_{n-1}+r_n\\ r_{n-1}&=l_{n+1}r_n \end{align} $$

     于是$r_n=1$

     $$ \begin{align} 2^p-1&=2^{l_1q+r_1}-1\\ &=2^{r_1}(2^{l_1q}-1)+(2^{r_1}-1)\\ &=N(2^q-1)+(2^{r_1}-1) \end{align} $$ 于是

     $$ \begin{align} gcd(2^p-1,2^q-1)&=gcd(2^q-1,2^{r_1}-1)\\ gcd(2^q-1,2^{r_1}-1)&=gcd(2^{r_1}-1,2^{r_2}-1)\\ &\cdots\\ gcd(2^{r_{n-1}}-1,2^{r_n}-1)&=2^{r_n}-1=1\\ \end{align} $$

7. 设$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$是整系数多项式，若$10\mid f(2)$，$10\mid f(5)$，则$10\mid f(10)$

   证明：注意到$f(10)=a_n10^n+a_{n-1}10^{n-1}+\cdots+a_0$，于是只需证$10\mid a_0$即可。因为$10\mid f(2)$，所以$2\mid f(2)$，所以$2\mid a_0$。同理$5\mid a_0$，又因为$2,5$互质，所以$10\mid a_0$，得证