给定正整数 $b$ 和 $n$, 满足下式

\[
b^e\equiv 1\pmod n
\]

的最小的正整数 $e$ 被称为 $b$ 模 $n$ 的 multiplicative order.  (或者称为 haupt-exponent or modulo order)

References:

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

比较 $2^{81}$ 与 $10^{24}$ 的大小.

证明恒等式

\[
\begin{vmatrix}
a & -b\\
b_1 & a_1\\
\end{vmatrix}\cdot
\begin{vmatrix}
c & -d\\
d_1 & c_1\\
\end{vmatrix}=
\begin{vmatrix}
ac+bd & -(a_1 d-b_1 c)\\
ad_1-b c_1 & a_1 c_1+b_1 d_1\\
\end{vmatrix}
\]

[Hint] 直接展开验证即可.

Remark:

(1) 若 $a,b,c,d\in\mathbb{C}$, $a_1=\bar{a}$, $b_1=\bar{b}$, $c_1=\bar{c}$, $d_1=\bar{d}$, 则相应的恒等式为

\[
\begin{vmatrix}
a & -b\\
\bar{b} & \bar{a}\\
\end{vmatrix}\cdot
\begin{vmatrix}
c & -d\\
\bar{d} & \bar{c}\\
\end{vmatrix}=
\begin{vmatrix}
ac+bd & -(\bar{a}d-\bar{b}c)\\
a\bar{d}-b\bar{c} & \overline{ac+bd}\\
\end{vmatrix}
\]

(2) 此恒等式用于证明任何一个正整数都可以表为四个数的平方和.

求方程

\[a^2+b^2+c^2+d^2+e^2=abcde\tag{*}\]

的正整数解. 这里不妨设 $a\leqslant b\leqslant c\leqslant d\leqslant e$.

(1) 若 $a,b,c,d,e$ 是方程 $(*)$ 的解, 容易验证 $b,c,d,e,bcde-a$ 也是方程 $(*)$ 的解. 从而可以构造无穷多组解.

(1) 若要求 $a < b < c < d < e$, 则对于 $[1,100]$ 之内的整数已经验证, 此方程无解.

猜测方程(*) 在此条件( $a < b < c < d < e$)下, 在 $\mathbb{Z}^{+}$ 上无解.

特别的, 我们能否证明

Prop. 若 $2+c^2+d^2+e^2=cde$, 则必有 $9|cde$.

Prop. 若 $a^2+b^2+c^2+d^2+e^2=abcde$, 则一定有两个数相等, 且存在两个数都是 3 的倍数, 从而有 $9|abcde$.

在集合 $1,2,\ldots,2n$ 中任取 $n+2$ 个数构成一个子集 $A$, 证明存在 $x,y\in A$, 使得 $x+y\in A$.

应用:

总共有 $2n$ 个参赛队 $A_1,A_2,\ldots,A_{2n}$, 组委会设定获奖队伍个数是 $n+2$ 个. 则存在这样两只获奖队伍 $A_i$ 和 $A_j$, 使得 $A_{i+j}$ 也是获奖队伍.

设 $p$ 是素数, 则集合 $\{1,2,\ldots,k\}$ 可划分为 $p$ 个子集, 其元素之和都相等的充分必要条件是

\[
k\geqslant 2p-1\quad\text{且}\quad p|\frac{1}{2}k(k+1)
\]

令

\[
F(n)=\sum_{i=1}^{n}\sum_{d|i}\mathrm{gcd}(d,\frac{i}{d})
\]

若记

\[
f(i)=\sum_{d|i}\mathrm{gcd}(d,\frac{i}{d}),
\]

则 $F(n)=\sum_{i=1}^{n}f(i)$. 证明

\[
f(p_{i_1}^{s_1}p_{i_2}^{s_2}\cdots p_{i_k}^{s_k})=f(p_{i_1}^{s_1})\cdot f(p_{i_2}^{s_2})\cdots f(p_{i_k}^{s_k}).
\]

用例子进行分析:

显然, $f(1)=1$, 且对于素数 $p$, $f(p)=2$.

\[
f(2^n)=\begin{cases}
2(1+2^1+2^2+\cdots+2^{[\frac{n-1}{2}]}), & \text{当}\ n\ \text{是奇数},\\
2(1+2^1+2^2+\cdots+2^{[\frac{n-1}{2}]})+2^{\frac{n}{2}}, & \text{当}\ n\ \text{是偶数}.\\
\end{cases}
\]

对于一般的素数 $p$

\[
f(p^n)=\begin{cases}
2(1+p^1+p^2+\cdots+p^{[\frac{n-1}{2}]}), & \text{当}\ n\ \text{是奇数},\\
2(1+p^1+p^2+\cdots+p^{[\frac{n-1}{2}]})+p^{\frac{n}{2}}, & \text{当}\ n\ \text{是偶数}.\\
\end{cases}
\]

对于任两个素数 $p,q$, 有

\[
f(pq)=2+\mathrm{gcd}(p,\frac{pq}{p})+\mathrm{gcd}(q,\frac{pq}{q})=4.
\]

对于三个素数 $p,q,r$, 有

\[
\begin{split}
f(pqr)&=2+\mathrm{gcd}(p,\frac{pqr}{p})+\mathrm{gcd}(q,\frac{pqr}{q})+\mathrm{gcd}(q,\frac{pqr}{r})\\
&\quad+\mathrm{gcd}(pq,\frac{pqr}{pq})+\mathrm{gcd}(pr,\frac{pqr}{pr})+\mathrm{gcd}(qr,\frac{pqr}{qr})\\
&=8.
\end{split}
\]

因此, 不难证明

\[
f(p_{i_1}p_{i_2}\cdots p_{i_k})=C_k^0+C_k^1+C_k^2+\cdots+C_k^k=2^k.
\]

设 $n=p^2 q^3$,

\[
\begin{split}
f(p^2 q^3)&=\mathrm{gcd}(1,p^2 q^3)+\mathrm{gcd}(q,p^2 q^2)+\mathrm{gcd}(q^2,p^2 q)+\mathrm{gcd}(q^3,p^2)\\
&\quad+\mathrm{gcd}(p,p q^3)+\mathrm{gcd}(pq,p q^2)+\mathrm{gcd}(pq^2,pq)+\mathrm{gcd}(pq^3,p)\\
&\quad+\mathrm{gcd}(p^2,q^3)+\mathrm{gcd}(p^2 q,q^2)+\mathrm{gcd}(p^2 q^2,q)+\mathrm{gcd}(p^2 q^3,1)\\
&=4+2p+4q+2pq\\
&=(2+p)(2+2q).
\end{split}
\]

注意到, 应用上面的公式, 有 $f(p^2)=2+p$, $f(q^3)=2(1+q)$. 因此我们有

\[
f(p^2 q^3)=f(p^2)f(q^3).
\]

于是我们就猜测

\[
f(p_{i_1}^{s_1}p_{i_2}^{s_2}\cdots p_{i_k}^{s_k})=f(p_{i_1}^{s_1})\cdot f(p_{i_2}^{s_2})\cdots f(p_{i_k}^{s_k}).
\]

这个证明实际上就隐藏在上面计算 $f(p^2 q^3)$ 的过程中, 你会发现

\[
\begin{matrix}
1 & q & q & 1\\
p & pq & pq & p\\
1 & q & q & 1\\
\end{matrix}
\]

关于中间竖直直线(未画出)的对称性, 这是由 $q$ 的指数是奇数带来的. 然后其他的行只不过是考虑到了 $p$. 

对任意素数 $p$, 证明

\[
\biggl(\frac{2}{p}\biggr)=\begin{cases}
1, & \text{若}\ p\equiv\pm 1\pmod 8,\\
-1, & \text{若}\ p\equiv\pm 3\pmod 8.
\end{cases}
\]

Artin 原根猜想(Artin's primitive root conjecture)

对所有 $a\in\mathbb{Z}$, $a\neq 0,\pm 1$, 存在无穷多个素数 $p$ 使得 $a$ 是模 $p$ 的原根.

Euler 准则.

设 $p$ 是一个奇素数, $a$ 是一不能被 $p$ 整除的整数. 则 $a$ 是模 $p$ 的平方剩余当且仅当

\[
a^{\frac{p-1}{2}}\equiv 1\pmod p
\]

Remark: 证明要用到模素数的剩余构成一个域这个事实.