\[2^{7^9}\equiv 2^7\pmod{279}\]

发现于 2022-06-12

By haifeng

Question:

有没有其他类似的等式了?

例如: 设 $x,y,z\in\{1,2,3,4,5,6,7,8,9\}$ 

\[x^{y^z}\equiv x^y\pmod{\overline{xyz}},\]

这里 $\overline{xyz}=100x+10y+z$.

证明 $3\times 10^n+121$ 不是平方数, 这里 $n$ 是任意非负整数.

注: 由于 $124$, $151$, $421$ 都不是平方数, 故不妨限定 $n\geqslant 3$.

设 $m,n$ 是正整数, 证明 $(2^m-1,2^n-1)=2^{(m,n)}-1$. 

一般的, 对于正整数 $a,m,n$, 有

\[
(a^m-1, a^n-1)=a^{(m,n)}-1.
\]

[Hint] 使用辗转相除法证明.

求 $(m,n)$ 的过程和求 $(2^m-1, 2^n-1)$ 的过程是一致的.

Question:  考虑 $(a^m-1, b^n-1)$, 这里 $a,b$ 是大于1的正整数.

勒让德(Legendre)符号的性质.

勒让德符号 $\Bigl(\frac{a}{p}\Bigr)$ 定义为

\[
\biggl(\frac{a}{p}\biggr)=\begin{cases}
1, & a\ \text{是}\ p\ \text{的平方剩余},\\
-1, & a\ \text{不是}\ p\ \text{的平方剩余}.\\
\end{cases}
\]

所谓平方剩余是指:

若方程 $x^2\equiv a\pmod p$ 有解, 则称数 $a$ 是素数 $p$ 的平方剩余. (这里 $p$ 是奇素数.)

(1)  若 $a\equiv b\pmod p$, 则 $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.

(2) $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.

作为(2) 的推广, 我们有

(3) 

\[\left(\frac{a^n}{p}\right)=\left(\frac{a}{p}\right)^n,\quad \left(\frac{a^2}{p}\right)=+1,\quad \left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right).\]

以上内容参见 [1] P. 99

References:

A. K. 苏什凯维奇 著  叶乃膺 译 《数论初等教程》,  哈尔滨工业大学出版社.

Goldbach 猜想指每个大于 4 的偶数都可以表为两个奇素数之和.

设 $n$ 为大于 4 的偶数, 若记 $\varphi(n)$ 为 $n$ 表示成两素数之和的表示方法数, 则有

参见 A002375 - OEIS

Remark:

这里使用 Calculator 中的 goldbach() 函数计算. 例如:

>> goldbach(30)
in> goldbach(30)
7 + 23
11 + 19
13 + 17

Total: 3

设 $p,q$ 均为素数. 证明: $p+q=(p-q)^3$ 当且仅当 $p=5$ 且 $q=3$.

设 $n$ 是正整数, 证明 $n$ 和 $n^5$ 具有相同的个位数.

Remark:

题目原文:

Prove that if $n$ is an integer, then $n$ and $n^5$ have the same units digit (first digit from the right).

注: units digit 指个位数, 即从右起第一个数字.

设 $k$ 是正整数. 证明 $\mathrm{gcd}(k,2^n+3^n+6^n-1)=1$ 对所有正整数 $n$ 成立当且仅当 $k=1$.

Remark:

问题来源: 

原文:

Let $k$ be a positive integer. Prove that $\mathrm{gcd}(k,2^n+3^n+6^n-1)=1$ for every positive integer $n$ if and only if $k=1$.

[Hint]:  Show that every prime must divide $2^n+3^n+6^n-1$ for some natural n. Consider cases when $p=2,3$ and $ > 3$. When $p > 3$, you may want to particularly look at $6(2^n+3^n+6^n-1)$, and to choose a value of $n$ which will allow you to use $\mathrm{F}\ell\mathrm{T}$.

Remark.  这里 $\mathrm{F}\ell\mathrm{T}$  指 Fermat Little Theorem.

$v(q)$ 表示 $q$ 的不同的素数因子的个数.

$d(q)$ 表 $q$ 的正除数的个数. 

若 $q=p_{i_1}^{s_1}p_{i_2}^{s_2}\cdots p_{i_m}^{s_m}$, 这里 $p_{i_1},\ldots, p_{i_m}$ 是 $q$ 的 $m$ 个不同的素数因子, $s_1,\ldots,s_m$ 分别是这些素数因子的重数. 则 $v(q)=m$, 
\[
d(q)=d(p_{i_1}^{s_1})\cdot d(p_{i_2}^{s_2})\cdots d(p_{i_m}^{s_m})=(s_1+1)(s_2+1)\cdots(s_m+1).
\]

引理 1.2  对于正整数 $q$, 存在 $\varepsilon > 0$, 使得

\[
2^{v(q)}\leqslant d(q)\leqslant c_3(\varepsilon)q^{\varepsilon}.
\]

参考 [1] P. 1 

References:

[1] 华罗庚 著, 王元 审校, 《华罗庚文集》数论卷 I

莫比乌斯函数(Mobius Function/Möbius Function) $\mu(x)$ 定义为

\[
\mu(x)=\begin{cases}
0, & \text{若}\ x \text{含有平方因子},\\
(-1)^{\omega}, & \text{若}\ x \text{不含有平方因子,  含有}\ \omega\ \text{个不同的素因子}.
\end{cases}
\]

换句话说, 设 $x$ 表示为 $p_{i_1}^{s_1}p_{i_2}^{s_2}\cdots p_{i_\omega}^{s_\omega}$,

若存在 $s_i\geqslant 2$, 则 $\mu(x)=0$; 否则, $\mu(x)=(-1)^{\omega}$.

若记 $\mu_d=\mu(d)$, 这里 $d$ 为正整数, 则有下面的定理.

定理.   对于 $m > 1$, $m\in\mathbb{Z}$, $\sum\limits_{d|m}\mu_d=0$;  当 $m=1$ 时, $\sum\limits_{d|m}\mu_d=1$.

这里求和 $\sum\limits_{d|m}$ 指 $d$ 跑遍 $m$ 的所有约数.

由此定理可导出戴德金-柳维尔公式.

实验（Calculator）

>> help(mobius)
in> help(mobius)
out> M?bius 函数

Example: mobius(168)

参见问题2765 on atzjg.net

Usage:
mobius(positiveInteger)

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

>> mobius(1234567)
in> mobius(1234567)
out> 1

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

>> factorise(1234567)
in> factorise(1234567)
127*9721
out> 127*9721

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

>> mobius(2765)
in> mobius(2765)
out> -1

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

>> factorise(2765)
in> factorise(2765)
5*7*79
out> 5*7*79