第 $1$ 讲

知识点

定义 $1$

对任给的两个整数 $a,b(a,b\ne0)$，如果存在整数 $q$，使得 $b=aq$，那么称 $b$ 能被 $a$ 整除（或 $a$ 能整除 $b$），记作 $a\mid b$。否则称 $b$ 不能被 $a$ 整除，记作 $a\nmid b$。

性质 $1$

如果 $a\mid b$，则 $a\mid(-b)$ 且 $(-a)\mid b$，反之亦然。

性质 $2$

如果 $a\mid b,b\mid c$，则 $a\mid c$。

性质 $3$

如果 $a\mid b,a\mid c$，则对于任意整数 $x,y$，有 $a\mid bx+cy$。

练习

1. 求证：$3^n+1$（$n$ 为正整数）能被 $2$ 或 $2^2$ 整除，但不能被 $2$ 的更高次幂整除。

   证明：$n=1$ 时，$3^n+1=4$，$2\mid4,2^2\mid4$。

   只要证明 $8\nmid 3^n+1$，命题即得证。

   • 如果 $n$ 为奇数，$3^n+1=4(3^{n-1}-3^{n-2}+\ldots-3+1)$。而括号内为 $n$ 个奇数的和差，仍为奇数，所以 $8\nmid3^n+1$。
   • 如果 $n$ 为偶数，可得 $4\nmid3^n+1$ 读者自证不难。

   $\mathcal{Q.E.D.}$

2. 是否存在 $100$ 个不同的正整数，使得他们的和等于他们的最小公倍数？

   解：存在。

   构造 $100$ 个数：

   $$1,2,2\times3^1,2\times3^2,\ldots,2\times3^{97},3^{98}$$

   然后自己算去。

   $\mathcal{Q.E.D.}$

3. 求所有的有理数 $a$，使得 $\left\vert4a-2\right\vert\le1$，并且 $A=\dfrac{4a-1}{27a^4}$ 为整数。

   解：由题得 $\dfrac{1}{4}\le a\le\dfrac{3}{4}$。

   设 $a=\dfrac{x}{y}\ [(x,y)=1]$。

   则计算得 $A=\dfrac{4xy^3-y^4}{27x^4}$。

   $\because(x,y)=1$，

   $\therefore x^4\mid4x-y$。

   $\therefore x\mid4x-y$。

   $\therefore x\mid y$。

   $\therefore x=1$。

   $\therefore A=\dfrac{y^3(4-y)}{27}$。

   又 $a=\dfrac{1}{y}\ge\dfrac{1}{4}$，

   $\therefore 2\le y\le4$。

   经检验，当 $y=3,a=\dfrac{1}{3}$ 时，$A$ 为整数。

   $\mathcal{Q.E.D.}$

第 $2$ 讲

知识点

对于正整数 $n>1$，如其因数仅有 $1$ 与 $n$，称 $n$ 为素数，否则 $n$ 为合数。$1$ 既不是素数也不是合数。

性质 $1$

设 $n$ 为大于 $1$ 的正整数，$p$ 为 $n$ 的最小的大于 $1$ 的因数，则 $p$ 为素数。

性质 $2$

如果对任意 $1\sim\sqrt n$ 之间的素数 $p$ 都有 $p\nmid n$，则 $n$ 为素数。

性质 $3$

素数有无穷多个。

性质 $4$

偶质数只有一个：$2$。

算术基本定理

设 $n$ 是大于 $1$ 的正整数，则 $n$ 可以分解为若干个素数的乘积的形式，而且他是唯一的。即存在唯一的一组素数 $p_1,p_2,\ldots,p_n$ 及指数 $\alpha_1,\alpha_2,\dots,\alpha_n$，使得 $n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\ldots\times p_n^{\alpha_n}$。

$n$ 的因数个数为

$$d(n)=\prod\limits_{i=1}^n(\alpha_i+1)$$

因数和为

$$\sigma(n)=\prod\limits_{i=1}^n(p_i^{\alpha_i}+p_i^{\alpha_i-1}+\ldots+p_i+1)$$

练习

1. 设 $n\ge2$ 为整数，$b$ 为合数。若有 $r$ 个不同的正整数整除 $b$，则至少有 $r$ 个正整数整除 $a^b-1$。

   解：设 $s_1\sim s_r$ 两两不等，且 $\forall1\le i\le r,s_i\mid b$。

   则

   $$\begin{aligned}a^b-1&=(a^{s_1}-1)(a^{b-s_1}+a^{b-2s_1}+a^{b-3s_1}+\ldots+a^{s_1}+1)\\&=(a^{s_2}-1)(a^{b-s_2}+a^{b-2s_2}+a^{b-3s_2}+\ldots+a^{s_2}+1)\\&=\ldots\\&=(a^{s_r}-1)(a^{b-s_r}+a^{b-2s_r}+a^{b-3s_r}+\ldots+a^{s_r}+1)\end{aligned}$$

   又 $\because s_1\sim s_r$ 两两不等

   $\therefore a^{s_1}-1,a^{s_2}-1,\ldots,a^{s_r}-1$ 两两不等。

   $\therefore$ 至少有 $r$ 个数整除 $a^b-1$。

   $\mathcal{Q.E.D.}$

2. 试证：已知 $n$ 为大于 $1$ 的奇数，则在 $2^1-1,2^2-1\ldots,2^{n-1}-1$ 中，至少有一个能被 $n$ 整除。

   证明：显然 $n\nmid 2^i(0\le i<n)$。

   其余数必为 $1\sim n-1$。

   根据抽屉原理，必存在两个整数 $1\le p<q<n$，使得 $2^p\equiv2^q\pmod n$。

   而 $2^q-2^p=2^p(2^{q-p}-1)$，因此 $n\mid 2^p(2^{q-p}-1)$。

   又 $\because (n,2^p)=1$，

   $\therefore n\mid 2^{q-p}-1$。

   $\mathcal{Q.E.D.}$

3. 试证：存在无穷多个正整数 $n$，使得 $n\mid 2^n+2$。

   证明：如 $n$ 为偶数，且 $n\mid 2^n+2,n-1\mid 2^n+1$（它是存在的，例如 $n=2$），

   则对于 $n'=2^n+2$ 也满足条件。

   设 $2^n+2=nk$（$k$ 为奇数）。

   $\because 2^{nk}+1=(2^n+1)\left[(2^n)^{k-1}-(2^n)^{k-2}+\ldots-2^n+1\right]$

   $\therefore 2^n+1\mid 2^{nk}+1$，即 $n'-1\mid 2^{n'}+1$。

   设 $2^n+1=m(n-1)$（$m$ 为奇数），

   同理可得 $2^{n-1}+1\mid 2^{2^n+1}+1$，即 $n'\mid 2^{n'}+2$。

   由此可生成无数个这样的 $n$。

   $\mathcal{Q.E.D.}$