欧拉-费马定理

Thm. 若 $a$ 与 $m$ 互素, 则

\[
a^{\varphi(m)}\equiv 1\pmod m
\]

特殊情形

若 $p$ 是一素数, 且 $a$ 不能被 $p$ 除尽, 则因 $\varphi(p)=p-1$, 所以有

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

Remark:

[俄] A. K. 苏什凯维奇 著, 叶乃膺 译《数论初等教程》 定理 58.

求同余方程 $x^{205}\equiv 3\pmod{1024}$.

[讨论]

这是模为 $2^k$ 的同余式情形. 并且由于 3 是奇数(模2余1), 所以 $x$ 也必是奇数.

Note: $2^k$ 当 $k > 2$ 时没有元根(primitive root).

设 $a,b,c$ 是三个素数, 求方程 $a(a+b)=12768+c$ 的所有解.

Remark:

题目来源: QQ群: 编程&数论&椭圆曲线

(1) 找两个不同汉字 $A$ 与 $B$, 使得 $AB$ 与 $BA$ 都是有意义的词, 且意思不一样.

比如: 工人、人工

(2) 找两个不同汉字 $A$ 与 $B$, 使得 $AB$ 与 $BA$ 都是有意义的数学词汇, 且意思不一样.

Remark:

题目来源: 孙智伟

$\tau(n)$ 是计算正整数 $n$ 的因子个数的一个函数, 也就是所有能整除 $n$ 的数的个数.

定义为:

\[
\tau(n):=\sum_{d|n}1.
\]

33是否可以写成三个整数的立方和, 长久以来这是一个悬而未决的问题.

感谢 Andrew R. Booker, 他发现了下面的表达式:

\[33=8866128975287528^3+(-8778405442862239)^3+(-2736111468807040)^3\]

对于100以内的数, 之前除了 33 和 42 之外, 都找到了表示成三个立方之和的表达式. 现在只剩下 42 了.

(2019-09-06)

\[42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3\]

来源:

孙智伟老师
 

Thm. 如果 $p$ 是素数, 且 $0 < x < p$, 那么 $x^2\equiv 1\mod p$ 仅有的解为 $x=1$ 和 $x=p-1$.

设 $p$ 是奇素数, 证明 $0^2,\ 1^2,\ ,\ldots,\ (\frac{p-1}{2})^2$ 模 $p$ 两两互不同余.

References:

https://arxiv.org/abs/1901.04837

怀疑是素数的

12039022919278967120019673

6019511459639483560009

如何快速计算 $2^{2019}$?

Hint:

令 $m1=2\times 2$, 则

\[
\begin{aligned}
m2:=2^4=m1\times m1\\
m3:=2^8=2^4\times 2^4=m2\times m2\\
m4:=2^{16}=2^8\times 2^8=m3\times m3\\
m5:=2^{32}=2^{16}\times 2^{16}=m4\times m4\\
\end{aligned}
\]