the theory of numbers

例题

  1. 设 a 是奇数,证明:必有正整数 d 使 $(2^d-3,a)=1$ 。

    tips:$(2^d-1,a)=1$

  2. 求 198 和 252 的最大公约数,并把它表为 198 和 252 的整系数线性组合。

    tips:利用辗转相除法化简得到多条式子以及最大公约数。最后一个式子逆向替换到只剩下 198 和 252 的线性组合。

  3. 求 198,252,924 的最大公约数,并把它表为 198,252 和 924 的整系数线性组合。

    tips:先求 198 和 252 的最大公约数 d,然后求 d 和 924 的最大公约数,然后所有式子逆向替换到只剩下 198,252,924 的线性组合。

  4. 设 m,n 是正整数,证明 $(2^m-1, 2^n-1) = 2^{(m,n) }-1$ 。

    tips:利用 $m = q_1n + r_1$ 替代,这里 $(m,n) = (n,r_1)$,然后进行配凑得到 $(2^m-1,2^n-1) = (2^n-1,2^{r_1}-1)$ ,若 $r_1$ 等于 0,得证;若 $r_1$ 不等于 0,利用辗转相除法做同样操作即可。

  5. 设 p 是素数,证明

    1. $p \mid(^p_j),1\le j\le p-1$ ,这里 $(^p_j)$ 表组合数;
    2. 对任意正整数 a,$p\mid a^p-a$ ;
    3. 若 $(a,p)=1$ ,则 $p\mid a^{p-1}-1$ 。

    tips:拆组合数,其中只有一个素数 p 整除 p;紧接着用归纳法解决 2,第 3 题其实是证明 $p \mid a^p -1$ 。

  6. 证明 1. $(a,uv) = (a,(a,u)v) $ 2. $(a,uv) \mid (a,u)(a,v)$

    1. 配凑法解决
    2. $(a,(a,u)v) \mid ((a,u)a,(a,u)v)=(a,u)(a,v)$ ,结合 1 得证。
  7. 设 k 是正整数,若一个有理数的 k 次方是整数,那么这个有理数一定是整数。

    tips:有理数可以用 $\frac{b}{a}$ 表示,然后得到 $ca^k = b^k$ ,得到 $a\mid b^k$ ,由于 (a,b)=1,则 $a\mid b$ ,因为 1=(a,b)=a,因此有理数就是整数。

  8. 设 k 是正整数,证明

    1. $(a^k,b^k) = (a,b)^k$

    2. 设 a,b 是正整数,若 $(a,b)=1,ab=c^k$ ,则

      $a=(a,c)^k,b=(b,c)^k$

    tips:1 很明显,2 的证明如下

    $a=a(a^{k-1}, b) = (a^k,ab)= (a^k,c^k)=(a,c)^k$

  9. 设 $a \ge 2,(a,b)=1$,证明

    1. 存在正整数 $d \le a-1$ ,使得 $a\mid b^d-1$ 。
    2. 设 $d_0$ 是满足 1 的最小正整数 d,那么,$a\mid b^h-1(h\ge 1) $ 的充要条件是 $d_0\mid h$ 。

    tips:由 $(a,b) = 1$ 得 $a\nmid b^j,j\ge 1$ ,因此令 $b^j=q_ja+r_j,0<r_j<a$ ,也就是说 a 个余数中有 a-1个值,其中必有两个相等。$a(q_k-q_i)=b^k-b^i=b^i(b^{k-i}-1)$ ,这里取 d=k-i 即可。

    2 的证明利用 $h = qd_0+r$ 拆分证明。最后得到 $a\mid 2^r-1$ ,由于 $d_0$ 是最小的,因此 r 必须为 0 ,不然可以继续找到比 d 更小的。

定义

  1. 最大公因数:所有共同因数中最大的。
  2. 最小公倍数:所有共同倍数中最小的。

背景知识

  1. 符号不影响倍数关系,因此我们一般考虑自然数即可。

  2. 如果存在整数 $x_1,…,x_k$ ,使得

    $a_1x_1+…+a_kx_k=1$

    则 $a_1, … , a_k$ 是既约的。

    证明:因为线性组合得到的值永远是最大公约数的倍数(令 $a_i=q_id$)。即 $d\mid1$ ,所以 d=1,也就是 $a_1,…,a_k$ 是互素的。

  3. 设正整数 $m\mid (a_1,…,a_k)$ ,我们有

    $m(a_1/m,…,a_k/m)=(a_1,…,a_k)$

    特别地有 证明:取 $d = ((a_1/m,…,a_k/m)) , D =(a_1,…,a_k)$ 分别证明以下两个式子即可

    1. $md \le D$
    2. $md \ge D$
  4. 设 m>0,我们有

    $[ma_1,\cdots,ma_k]=m[a_1,\dots,a_k]$

    证明:设 $L=[ma_1,\cdots,ma_k],L’=[a_1,\cdots,a_k]$

    1. 由 $ma_j\mid L(1\le j \le k)$ 推出 $a_j\mid L/m,(1\le j\le k)$ ,由定义 2 知 $L’\le L/m$ 。

    2. 由 $a_j\mid L’(1\le j \le k)$ 推出 $ma_j\mid mL’(1\le j \le k)$ ,由定义 2 知 $L \le mL’$ 。

    综合 1 和 2,得到 $L=mL’$

  5. $a_j\mid c(1\le j \le k) $ 的充要条件是 $[a_1, \cdots, a_k] \mid c$ 。

    tips:令 $L =[a_1,\cdots,a_k]$ ,利用 $c=qL+r$ 然后证明 r=0 即可。

    结论表明:公倍数一定是最小公倍数的倍数

  6. 公约数一定是最大公约数的约数。

  7. 求 k 个数的最大公约数可归纳为求 k-1 个数的最大公约数

  8. 设 $(m,a)=1$ ,若 $m\mid ab$ ,则 $m\mid b$

  9. 设 a,b均不为零,我们有 $(a,b)[a,b]=\mid ab\mid $

  10. 设 $a_1,\cdots,a_k$ 是不全为零的整数,那么对整数 n,存在整数 $y_1,\cdots,y_k$ 使得 $n=a_1y_1+\cdots+a_ky_k$ 成立的充要条件是 $(a_1,\cdots,a_k) \mid n$ ,特别地,当 n=1 时,$a_1,\cdots,a_k$ 互素。