初等数论

点击此处下载试卷
点击此处下载习题课(2016/03-2016/07)讲义


  1. 对于任意整数 $m$, 求最大公因数 $(21m+4,14m+3)$.
    1. 求最大公因数 $(252,198)$,并把它表为 $252$ 和 $198$ 的整系数线性组合.
    2. 求最小公约数 $[252,198]$.
  2. 求 $20!$ 的标准素因子分解式.
  3. 求 $5x+7y=41$ 的全部正整数解.
  4. 证明多项式 $x^6+x^5+\cdots+x+1$ 不能分解为两个低于 $6$ 次的有理系数多项式的乘积.
  5. 令 $\sigma(n)$ 为 $n$ 的所有正因数之和. 求 $\sigma(117)$.
  6. 令 $\varphi(m)$ 为 Euler 函数. 求 $\varphi(7\cdot 9\cdot 11)$.
  7. 解同余方程 $7x\equiv1\bmod{31}.$
  8. 解同余方程组
    $$\left\{ \begin{split}&x\equiv3\bmod{5}\\&x\equiv 4\bmod {7}.\end{split} \right.$$
  9. 问同余方程 $x^2\equiv 14\bmod{55}$ 是否有解?

  1. 用 Fermat 定理 $(p\mid n^p-n)$, 对任意整数 $n$, 证明 $$2730\mid n^{13}-n.$$
  2. 解同余方程组
    $$\left\{\begin{split}
    &x\equiv 2\pmod 3,\\
    &x\equiv 3\pmod 5,\\
    &x\equiv 4\pmod 7.\\
    \end{split}\right.$$
  3. 由 Wilson 定理 $$(p-1)!\equiv -1\pmod p$$ 推出: 当 $p$ 为奇素数时, 有
    $$2^2\cdot 4^2\cdot \cdots\cdot (p-1)^2\equiv (-1)^{\frac{1}{2}(p+1)}\pmod p.$$
  4. 求以 $3$ 为二次剩余的素数 $p(>3)$.
  5. 问同余方程 $$x^2\equiv 23\pmod{91}$$ 是否可解? 如果可解的话, 有几个 $\bmod{91}$ 的解?
  6. 令 $$f(x)=x^4+4x^3+x^2+2x+4,\quad g(x)=x^3+3x^2+5$$ 为 $\mathbb{F}_7[x]$ 上的多项式. 求 $f(x)$ 和 $g(x)$ 的最大公因式 $d(x)$ (首项系数为 $1$), 并将 $d(x)$ 写成
    $$d(x)=r(x)f(x)+s(x)g(x),$$ 这里 $r(x),s(x)$ 均属于 $\mathbb{F}_7[x]$.
  7. 设 $s>1$. 令 $\mu(n)$ 为 Möbius 函数,
    $$\zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s}.$$ 证明
    $$\sum_{n=1}^\infty \frac{\mu^2(n)}{n^s}=\frac{\zeta(s)}{\zeta(2s)}.$$
  8. 令 $d(r)$ 为除数函数. 证明 $$\sum_{r\mid n}d^3(r)=\big(\sum_{r\mid n} d(r)\big)^2.$$
  9. 令 $\varphi(n)$ 为 Euler 函数, $\mu(n)$ 为 Möbius 函数. 对于 $x\ge 1$, 证明
    $$\sum_{n\le x}\frac{\varphi(n)}{n}=\sum_{n\le x}\frac{\mu(n)}{n}\big[\frac{x}{n}\big].$$
  10. 对于 $x\ge 2$, 利用渐近公式 $$\sum_{p\le x}\frac{\log p}{p}=\log x+O(1),$$
    证明 $$\sum_{p\le x}\frac{\log^3 p}{p}=\frac{1}{3}\log^3 x+O(\log^2 x),$$
    这里 $p$ 表示素数.
  11. 令 $\varphi(n)$ 为 Euler 函数. 对于 $x\ge 2$, 证明
    $$\sum_{n\le x}\frac{1}{\varphi(n)}=O(\log x).$$

发表评论