theory of numbers

作业

  1. 求 $2^{400}$ 对模 10 的最小非负剩余。

    其实就是让你求个位数是多少。2,4,8,16,32,可以发现每 4 个一个循环,所以是 6。

  2. 求 $2^{1000}$ 的十进位表示中的最后两位数字。我们只需要考虑最后两位的循环。02,04,08,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,04。从 2 到 21 是一个循环,也就是 从 2 开始每 20 一个循环,所以最后答案是 76。

  3. 求 3 对模 7 的逆

    $3x\equiv 1(mod \ 7)$ ,求得 $x=-2$ 。

  4. 求 13 模 10 的逆

    $13x\equiv 1(mod \ 10)$ ,求得 $x=-3$ 。

  5. 证明不定方程 $x^2-2y^2=77$ 无解。(参照实例 3)

    $77=7*11$ ,若有解 $x_0,y_0$ ,则 $(x_0y_0,77)=1$ 。对不定方程解读得到

    $x_0^2=2y_0^2(mod \ 11)$ (因为 mod 7不能判断无解,参照实例3),由于 $(y_0,11)=1$ ,利用逆元变换得到

    $(x_0y_0^{-1})^2=2 (mod \ 11)$ ,$n^2$ 对模 11 的剩余仅可能是 0,1,4,-2,5,3,9。不可能是 2,所以原方程无解。

  6. 证明不定方程 $x^2-3y^2+5z^2=0$ 无解。

    若不定方程有解 $x_0,y_0,z_0$ ,我们取本原解,即 $(x_0,y_0,z_0)=1$ ,此时 $x_0,y_0$ 都和 5 互素(反证法)。

    对不定方程解读得到

    $x_0^2\equiv 3y_0^2 (mod \ -5z_0^2)$ ,即 $x_0^2 \equiv 3y_0^2(mod \ 5)$ 由于 $(y_0,5)=1$ 逆元变换得到

    $(x_0y_0^{-1})^2=3(mod \ 5)$

    $n^2$ 对模 5 的剩余系仅可能是:0,1,4,不可能是 3,所以原方程无解。

实例

  1. 求 $3^{406}$ 写成十进位数时的个位数。

  2. 求 $3^{406}$ 写成十进位数时的最后两位数。

  3. 证明:$641\mid 2^{2^5} +1$。

  4. 证明不定方程 $x^2+2y^2=203$ 无解。

    $203=7*29$ ,若有解 $x_0,y_0$ ,利用反证法可知 $(xy,203)=1$ 。对不定方程解读可得

    $x_0^2 \equiv -y_0^2 mod \ 203$ 即 $x_0^2\equiv -y_0^2 \ mod \ 7$

    由于 $(y_0,7)=1$ ,由背景知识 9 可知 $y_0$ 对模 7 有逆元 $y_0^{-1}$

    在同余式两边乘 $(y_0^{-1})$ 得

    $(x_0y_0^{-1})^2\equiv x_0^2(y_0^{-1})^2 \equiv-2y_0^2(y_0^{-1})^2\equiv-2(y_0y_0^{-1})^2\equiv -2 (mod \ 7)$

    但 $n^2$ 对模 7 的剩余(n 对模 7 的剩余进行平方得到)仅可能是:0,1,-3,2,不可能是 -2,所以原方程无解。

  5. 设 $n\ge 1$ ,b 的素因数都大于 n。证明:对任意正整数 a 必有

    $n!\mid a(a+b)(a+2b)\cdots (a+(n-1)b)$

  6. 设 $m>n\ge1$ ,求最小的 m+n 使得

    $1000 \mid 1978^m-1978^n$

背景知识

  1. 同余

    $a \equiv b(mod \ m)$ ,也就是 a-b=km,b 是 a 对模 m 的剩余

  2. 同余的充要条件是最小非负余数相等。

  3. 同余具有自反性,对称性和传递性。因此可以有同余类。

  4. 若 $a\equiv b(mod \ m) , c \equiv d(mod \ m)$

    1. $a+c \equiv b+d (mod \ m).$
    2. $ac\equiv bd(mod \ m)$
  5. 设 $f(x) =a_nx^n+\cdots+a0,g(x)=b_nx^n+\cdots+b_0$ 是两个整系数多项式,满足

    $a_j\equiv b_j(mod \ m),0\le j \le n \cdots (2)$

    那么,若 $a \equiv b(mod \ m)$ ,则 $f(a)\equiv g(b)(mod \ m)$

    我们把满足条件 (2)的两个多项式 $f(x),g(x)$ 称为 多项式 $f(x)$ 同余于多项式 $g(x)$ 模 m。

    注意:函数同模不一定相应系数相同。

  6. $a \equiv b(mod \ m),d \mid m$ 则,$a\equiv b(mod \ d)$

  7. $da\equiv db(mod \ \mid d\mid m)$

  8. $ca\equiv cb (mod \ m)$

  9. 若 $m\ge 1,(a,m)=1$ ,则存在 c 使得

    $ca\equiv 1(mod \ m)$

    我们把 c 称为是 a 对模 m 的 ,记作 $a^{-1}(mod \ m)$ 或 $a^{-1}$ 。

  10. 同余式组 $a\equiv b(mod \ m_j),j=1,2,\cdots,k$ 同时成立的充要条件是

    $a\equiv b(mod \ [m_1,\cdots,m_k]).$