设 $p$ 是素数, $a,b$ 都与 $p$ 互素, 且

\[
a^p\equiv b^p\pmod p
\]

证明

\[
a^p\equiv b^p\pmod {p^2}
\]

设 $a,b,c$ 和 $m$ 都是整数, $m > 0$. 且 $d=(a,b,m)$. 证明: 二元线性同余方程

\[
ax+by\equiv c\pmod m
\]

在 $d|c$ 时恰有 $dm$ 个不同余的解, 其他情形无解.

设 $N$ 是一个完全数, 它的所有正因子(不包含自身)是 $1,d_1,d_2,\ldots,d_n$, 证明

\[1=\frac{1}{N}+\frac{1}{d_1}+\frac{1}{d_2}+\cdots+\frac{1}{d_n}.\]

[Hint] 利用二进制进行解释. 这个结论是 Euler 发现的.

Reference:

定理(Cataldi-Fermat). 若 $2^n-1$ 是素数, 则 $n$ 一定是素数.

[Hint] 若 $n=rs$, $r > 1$, $s > 1$, 则 $2^r-1 | 2^n-1$.

证明: 若 $a$ 是 $p$ 的平方剩余, 则它是 $p^k$ 的平方剩余, $k$ 为任意正整数.

设 $p$ 素数, 则

\[
\biggl(\frac{3}{p}\biggr)=(-1)^{[\frac{p+1}{6}]}.
\]

证明 $2^p-1\equiv 7\bmod 12$, 其中 $p$ 为大于 1 的奇数.

也就是说, 从小时来看, 从 0 点经过 $2^p-1$ 小时, 总是 7 时. (这里 $p$ 为大于 1 的奇数.)

梅森素数(Mersenne primes)的 Lucas-Lehmer 测试.

设 $M_p=2^p-1$ 是梅森数(Mersenne number), $p$ 是大于 2 的素数. 定义序列 $\{s_i\}_{i=0}^{\infty}$:

\[
s_n=\begin{cases}
4, & n=0,\\
s_{n-1}^2 -2, & n > 0.
\end{cases}
\]

即 $s_0=4$, $s_1=14$, $s_2=194$, $s_3=37634$, 等等. (参见 OEIS A003010) 于是我们有.

定理. $M_p=2^p-1$ 是素数当且仅当 $s_{p-2}\equiv 0\bmod M_p$.

等价的, 如果令 $s_1=4$, $s_n=s_{n-1}^2-2$, 则叙述改为 $M_p=2^p-1$ 是素数当且仅当 $s_{p-1}\equiv 0\bmod M_p$.

证明的关键是令 $w=2+\sqrt{3}$, $v=2-\sqrt{3}$, 从而可证明

\[
s_n=w^{2^{n-1}}+v^{2^{n-1}}.
\]

注意 $w\cdot v=1$.

References:

https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test

https://primes.utm.edu/notes/proofs/LucasLehmer.html

称 $g$ 是模 $n$ 的原根, 如果对于任意与 $n$ 互素的 $a$, 存在 $k$ 使得

\[
g^k\equiv a\pmod n.
\]

例如, 3 是模 7 的原根.

[Definition by Ribenboim 1996]

素数 $p$ 的原根是指整数 $g$, 使得 $g\pmod p$ 具有 multiplicative order $p-1$. 即

\[
g^{p-1}\equiv 1\pmod p
\]

更一般的定义, by Burton 1989

[Def](by Burton 1989) 若 $\text{gcd}(g,n)=1$ ($g$ 和 $n$ 互素) 且 $g$ 模 $n$ 具有 multiplicative order $\varphi(n)$, 即满足

\[
g^{\varphi(n)}\equiv 1\pmod n
\]

这里 $\varphi(n)$ 是指欧拉函数(totient function), 则 $g$ 是 $n$ 的一个原根.

第一个定义是第二个定义的特殊情形, 因为对于素数 $p$, $\varphi(p)=p-1$.

设 $n$ 是具有原根的一个正整数. 若 $g$ 是模 $n$ 的一个原根, 则数 $1,g,g^2,\ldots,g^{\varphi(n)-1}$ 构成模 $n$ 的一个 reduced residue system. 在这个集合中, 有 $\varphi(\varphi(n))$ 个原根, 且这些数形如 $g^c$, 这里 $c$ 与 $\varphi(n)$ 互素.

References:

http://mathworld.wolfram.com/PrimitiveRoot.html

Euler's totient function $\phi(m)$ 定义为 $\{1,2,3,\ldots,m-1\}$ 中与 $m$ 互素的元素个数.

显然对于素数 $p$, 有 $\phi(p)=p-1$.

证明: $\phi(2p)=p-1$.

问 $\phi(p^2)$ 等于多少?

事实上, Euler phi function 具有乘积性, 如果 $(m,n)=1$, 则

\[
\phi(mn)=\phi(m)\phi(n).
\]

Euler 证明

\[
\frac{\phi(n)}{n}=\prod_{p|n}(1-\frac{1}{p}),
\]

这里 $p$ 取遍 $n$ 的所有素因子.

有了这个公式, 就很容易计算一个正整数在欧拉函数下的值.

Reference:

https://en.wikipedia.org/wiki/Euler's_totient_function