theory of numbers

作业

  1. 分别求出 $n^2,n^3,n^4,n^5$ 被 3,4,8,10 除后,可能取到的最小非负余数,最小正余数及绝对最小余数。

    其实就是求剩余系,先求出 n 对模 3、4、8、10 后的余数,进行相应的变换得到的新集合就是了。

  2. 证明:若 $2 \nmid xy$ ,则 $x^2+y^2 \neq n^2$

    也就是 x 和 y 都是奇数。$x=2k_1-1,y=2k_2-1$ ,则

    $x^2+y^2 = (2k_1+1)^2+(2k_2+1)^2=4(k_1^2+k_1+k_2^2+k_2)+2$ ,显然整除 2 但不整除 4,没有这样的平方数。

  3. 设奇数 $a>2,a\mid2^d-1$ 的最小正整数 $d=d_0$ 。证明:$2^d$ 被 a 除 后,所可能取到的不同的最小非负余数有 $d_0$ 个。

    反证法:不妨取 $2^0,2^1,\cdots,2^{d_0-1}$ 这 $d_0$ 个数。分别对 a 进行取余,如果存在两个余数相同,那么和 $d_0$ 是最小整数矛盾。

  4. 若 $2\nmid n,3\nmid n$ ,则 $24 \mid n^2+23$

  5. $30 \mid n^5-n$

  6. 任一形如 $3k-1,4k-1,6k-1$ 形式的正整数必有同样形式的素因数

  7. 形如 $4k-1$ 的素数有无穷多个

  8. 形如 $6k-1$ 的素数有无穷多个

  9. 用辗转相除法求以下数组的 $u_{k+1}$ ,并把它表为这些数的整系数线性组合

    ① 1819,3587 ② 2947,3997 ③ -1109,4999

实例

  1. 设 $a>2$ 是奇数,证明:

    1. 一定存在正整数 $d\le a-1$ ,使得 $a\mid2^d-1$

      取以下 a 个数 :

      $2^0,2^1,2^2,\cdots,2^{\alpha-1}.$

      显然奇数 $a \nmid 2^j(0\le j <a)$ ,利用背景知识 1 可得

      $2^j=q_ja+r_j, 0<r_j<a$

      所以 a 个余数 $r_0,r_1,\cdots,r_{a-1}$ 仅可能取 a-1 个值(0 被刨去了),盒子定理可知必有两个余数相同,设为 $r_i,r_k$ ,不妨设 $0\le i<k<a.$ 因而有

      $a(q_k-q_1)=2^k-2^i=2^i(2^{k-i}-1).$

      $a \nmid 2^i$ ,故 $a\mid 2^{k-i}-1$ 。取 $d=k-i \le a-1$ 。

    2. 设 $d_0$ 是满足 1 的最小正整数 d,那么 $a \mid 2^h-1$ 的充要条件是 $d_0\mid h$ 。

      充分性是显然的,证明必要性

      $h=qd_0+r,0\le r<d_0$

      因此有 $a\mid 2^h-1$ 及 $a\mid2^{qd_0}-1$ ,就推出 $a\mid 2^r-1$ ,由于 $d_0$ 是最小的,所以 $r=0$ ,即 $d_0\mid h$ 。

背景知识

  1. 带余数除法

    设 a, b 是两个给定的整数,a ≠ 0 。那么,一定存在唯一的一对整数 q 与 r,满足

    b = q a + r,0 ≤ r < |a|

    此外,a|b 的充要条件是 r = 0。r 称为最小非负余数。

  2. 辗转相除法

    用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是 0 为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

  3. 设整数 $a \ge 2$ ,那么 a 一定可表为素数的乘积。即 $a=p_1p_2\cdots p_s$ 。(利用第二归纳法)