一个数 $n$, 如果对所有的基 $a$ (满足 $(a,n)=1$), 都有

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

则称 $n$ 为 Carmichael 数.

性质: Carmichael 数一定是伪素数, 伪素数不一定是 Carmichael 数.

比如 341 是伪素数, 但 341 不是 Carmichael 数. 事实上方程 $x^{341-1}\equiv 1\pmod{341}$ 有很多解. (参见问题2306)

相关条目:  伪素数

Thm. (Carmichael数的判别法) 设 $n$ 为合数, 则 $n$ 是 Carmichael 数当且仅当 $n$ 是奇数且对整除 $n$ 的每个素数 $p$, 满足

• $p^2\not\mid n$
• $p-1\mid n-1$
   

所谓的伪素数是指满足费马小定理的合数.

Fermat 小定理: 设 $p$ 是一个素数, 且 $0 < a < p$, 则有 $a^{p-1}\equiv 1\pmod p$.

举出10000以内的所有伪素数. 比如1000以内的伪素数只有三个: 341, 561, 645.

10000 以内的pseudo prime 有:

341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4371
4681
5461
6601
7957
8321
8481
8911

------------

Total: 21

[10000, 20000] 以内的伪素数

10261, 10585, 11305,12801,13741,13747,13981,14491,15709,15841,16705,18705,18721,19951

欧拉-费马定理

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