>> IndefiniteEquation(13,19)
in> IndefiniteEquation(13,19)
Solve the equation: 13*x+19*y = 1
19==1*13+6
13==2*6+1
1 2
test: 9==9*2-3*3

事实上, 19*2-13*3=-1

这里还需测试

test: 9*3-3*2, 结果是 21, 个位数是1, 符合要求.

>>  IndefiniteEquation(19,21)
in> IndefiniteEquation(19,21)
Solve the equation: 19*x+21*y = 1
21==1*19+2
19==9*2+1
1 9
test: 9==1*9-9*0

in> IndefiniteEquation(13,19)
out> 
Solve the equation: 13*x+19*y = 1
19==1*13+6
13==2*6+1
1 2 
test: -1==9*2-3*3
13*3-19*2 == 1
x = 3+19t
y = -2-13t

-----------end---------

\[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