the theory of numbers

作业

  1. 写出模 9 的一个完全剩余系,它们的每个数都是奇数。

    对 $0,1,\cdots,9$ 中的每个偶数加 9 得到的集合就是一个全是奇数的完全剩余系。

  2. 写出模 9 的一个完全剩余系,它的每个数都是偶数。(做法和 1 雷同)

  3. 证明:当 m>2 时,$0^2,1^2,\cdots,(m-1)^2$ 一定不是模 m 的完全剩余系

    $1^2 \equiv (m-1)^2(mod \ m)$ ,而完全剩余系中是不允许出现同余的。

  4. 设有 m 个整数,它们都不属于剩余类 $0 \ mod \ m$ 。那么,其中必有两个数之差属于剩余类 $0 \ mod \ m$

    m-1 个剩余类,m 个整数,根据盒子定理,必有两个整数属于同一个剩余类,这两个整数只差等于 km。

例子

  1. 设 n,k 是正整数,(k,n)=1,0<k<n。再设集合 $M = \lbrace1,2,\cdots,n-1\rbrace$ ,现对集合 M 中的每一个数 $i$ 涂上蓝色或白色,要满足以下条件

    1. i 和 n-i 要涂上同一种颜色
    2. 当 $i\neq k$ 时,i 和 $\mid k-i \mid$ 要涂上同一种颜色

    证明:所有的数一定都涂上同一种颜色。

  2. 利用模 10、模 199 的完全剩余系来表示模 1990 的完全剩余系。

  3. 利用模 3 的剩余系来表示模 $3^n(n \ge 2)$ 的剩余系。

背景知识

  1. 由定义可以推出

    1. $r \ mod \ m=\lbrace r+km:k\in Z;$
    2. $r \ mod \ m = s \ mod \ m$ 的充要条件是 $r\equiv s(mod \ m);$
    3. 对任意的 r,s,要么 $r \ mod \ m=s \mod \ m$ ,要么 $r \ mod \ m$ 与 $s \ mod \ m$ 的交集为空集。
  2. 对给定的模 m,有且恰有 m 个不同的模 m 的同余类,它们是

    $0 \ mod \ m,1 \ mod \ m, \cdots ,(m-1)mod \ m$

  3. 在任意取定的 m+1 的整数中,必有两个数对模 m 同余

  4. 存在 m 个数两两对模 m 不同余。

  5. 设 $m_1 \mid m$ ,那么对任意的 r 有

    $r \ mod \ m \subseteq r \ mod \ m_1$ ,等号仅当 $m=m_1$ 成立。更精确地说,若 $l_1,\cdots,l_d$ 是模 $d=m/m_1$ 的一组完全剩余系,则

    $r \ mod m_1 = \bigcup \limits_{0\le j <d}(r+l_jm_1) mod \ m$

  6. 模 m 的一个同余类中的任意两个整数 $a_1,a_2$ 与 m 的最大公约数相等,即 $(a_1,m_)= (a_2,m)$

  7. 模 m 的所有不同的既约同余类是

    $r \ mod \ m,(r,m)=1,1\le r \le m.$

    $\phi(m)$ 等于 $1,2,\cdots,m$ 中和 m 既约的数的个数。

  8. 在任意取定的 $\phi(m) +1$ 个均和 m 既约的整数中,必有两个数对模 m 同余。

  9. 存在 $\phi(m)$ 个数两两对模 m 不同余且均和 m 既约。

  10. 设 p 是素数, $k\ge1.$ 那么

    $\phi(p^k)=p^{k-1}(p-1)$

    以及模 $p^k$ 的既约同余类是

    $(a+bp) mod \ p^k,1\le a\le p-1,0\le b\le p^{k-1}-1$

  11. 从 x 开始遍历和从 x+c 开始遍历模 m 的完全剩余系得到的结果都一样。

  12. 对既约剩余系中的每一个数加上 km,还是既约剩余系。

  13. $x_1,\cdots,x_n$ 是完全剩余系,若 (a,m)=1,则 $ax_1,\cdots,ax_n$ 也是完全剩余系。

  14. 设 $m=m_1m_2$ ,$x^{(1)}$ 是模 $m_1$ 的完全剩余系,$x^{(2)}$ 是模 $m_2$ 的完全剩余系,则 $x=x^{(1)}+m_1x^{(2)}$ 是模 m 的完全剩余系。

  15. 根据 14,设 $m=m_1m_2\cdots m_k$ ,及

$x=x^{(1)} + m_1x^{(2)} + m_1m_2x^{(3)}+\cdots+m_1\cdots m_{k-1}x^{(k)}$ 是 模 m 的剩余系。