Questions in category: 初等数论 (Elementary Number Theory)
数论 >> 一般数论 >> 初等数论
<[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] >

11. 设 $m,n\in\mathbb{Z}^+$, 证明 $(2^m-1,2^n-1)=2^{(m,n)}-1$.

Posted by haifeng on 2022-06-10 13:15:36 last update 2022-06-10 13:38:47 | Answers (1) | 收藏


设 $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的正整数.

12. 勒让德符号的性质

Posted by haifeng on 2021-12-13 09:21:44 last update 2021-12-13 10:54:09 | Answers (2) | 收藏


勒让德(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. 苏什凯维奇 著  叶乃膺 译 《数论初等教程》,  哈尔滨工业大学出版社.

13. Goldbach 猜想相关

Posted by haifeng on 2021-11-30 22:59:30 last update 2021-11-30 23:08:43 | Answers (0) | 收藏


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

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

$n$ $\varphi(n)$ Example
6 1 3+3
8 1 3+5
10 2 3+7; 5+5
12 1 5+7
14 2 3 + 11
7 + 7
16 2 3 + 13
5 + 11
18 2 5 + 13
7 + 11
20 2 3 + 17
7 + 13
22 3 3 + 19
5 + 17
11 + 11
24 3 5 + 19
7 + 17
11 + 13
26 3 3 + 23
7 + 19
13 + 13
28 2 5 + 23
11 + 17
30 3 7 + 23
11 + 19
13 + 17
32 2 3 + 29
13 + 19
34 4 3 + 31
5 + 29
11 + 23
17 + 17
36 4 5 + 31
7 + 29
13 + 23
17 + 19
38 2 7 + 31
19 + 19
40 3 3 + 37
11 + 29
17 + 23
42 4 5 + 37
11 + 31
13 + 29
19 + 23
44 3 3 + 41
7 + 37
13 + 31
46 4 3 + 43
5 + 41
17 + 29
23 + 23
48 5 5 + 43
7 + 41
11 + 37
17 + 31
19 + 29
50 4 3 + 47
7 + 43
13 + 37
19 + 31

 

参见 A002375 - OEIS

 


Remark:

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

 

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

Total: 3

 

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

Posted by haifeng on 2021-11-24 22:51:14 last update 2021-11-24 22:51:14 | Answers (0) | 收藏


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

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

Posted by haifeng on 2021-11-24 16:01:48 last update 2021-11-24 16:01:48 | Answers (1) | 收藏


设 $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 指个位数, 即从右起第一个数字.

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

Posted by haifeng on 2021-11-24 14:43:25 last update 2021-11-24 15:58:12 | Answers (1) | 收藏


设 $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.

17. 正整数不同素因子个数与正除数个数之间的关系.

Posted by haifeng on 2021-07-10 15:35:59 last update 2021-07-10 15:37:41 | Answers (1) | 收藏


$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

18. 莫比乌斯函数(Mobius Function/Möbius Function)

Posted by haifeng on 2021-06-23 22:26:31 last update 2022-12-21 20:02:02 | Answers (0) | 收藏


莫比乌斯函数(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_{d}\mu_d=0$;  当 $m=1$ 时, $\sum_{d}\mu_d=1$.

这里求和 $\sum_d$ 指 $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

 

 

 

19. 水仙花数(Narcissistic Number)

Posted by haifeng on 2021-06-22 09:39:19 last update 2021-06-22 09:39:55 | Answers (0) | 收藏


一个 $n$-位的正整数, 如果其各个数字的 $n$-次方之和等于该数, 则称其为 $n$-水仙花数($n$-Narcissistic Number).

 

例如: 三位数中是水仙花数的, 仅有 153, 370, 371, 407.

\[
\begin{aligned}
1^3+5^3+3^3&=153,\\
3^3+7^3+0^3&=370,\\
​3^3+7^3+1^3&=371,\\
​4^3+0^3+7^3&=407.\\
\end{aligned}
\]

 

 

References:

Narcissistic Number -- from Wolfram MathWorld

 

20. 使用 Calculator 将循环小数转化为分数

Posted by haifeng on 2021-06-09 09:45:43 last update 2021-06-09 09:46:29 | Answers (0) | 收藏


61. 化下列循环小数成分数

  • 0.35(62)
  • 5.1(538)
  • 3.(27)
  • 11.12(31)

() 内的是循环节.


 

使用 Calculator, 首先进入分数计算模式

>> :mode=fraction

>> 0+(3562-35)/9900
in> 0+(3562-35)/9900

out> 3527|9900

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

>> 5+(1538-1)/9990
in> 5+(1538-1)/9990

out> 51487|9990

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


>> 3+(27-0)/99
in> 3+(27-0)/99

out> 36|11

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

>> 11+(1231-12)/9900
in> 11+(1231-12)/9900

out> 110119|9900

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

 


References:

A. K. 苏什凯维奇  著  《数论初等教程》  P. 92

<[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] >