the theory of numbers

作业

  1. 若 $x^2+ax+b=0$ 有整数根 $x_0\neq0$ ,则 $x_0\mid b$ ,一般地,若

    $x^n+a_{n-1}+\cdots+a_0=0$ 有整数根 $x_0\neq0$ ,则 $x_0 \mid a_0$ 。

  2. 判断 $x^3-x^2-4x+4=0$ 是否有整数解并求解。

  3. 设 $q\neq0,\pm1.$ 若对任意的 a,b,由 $q\mid ab$ 可推出 $q\mid a$ 或 $q\mid b$ 至少有一个成立,则 q 一定是素数。

例题

  1. 若 $3 \mid n$ 且 $7\mid n$,则 $21\mid n$ 。

  2. 找到不大于 100 的所有素数(利用 Eratosthenes 筛法)

    根号 100 等于 10,小于 10 的素数有 2,3,5,7,将这四个数的倍数全部去掉,剩下的全是素数。

背景知识

  1. $d_i$ 是 b 的全体约数,则 $b/d_i$ 也是它的全体约数。

  2. 若 a 是合数,则必有素数 $p\mid a$ 。

  3. 一个大于 2 的数可以表示为多个素数的乘积。

Eratosthenes 筛法

设整数 a ≥ 2。

  1. 若 a 是合数,则必有素数 $p\mid a, p \le a^{1/2}$
  2. 若 a 为 s 个素数的乘积,则必有素数 $p\mid a$ ,$p \le a^{1/s}$ 。

利用这两个规律,可以得到一个寻找素数的有效算法。