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

71. Artin 原根猜想(Artin's primitive root conjecture)

Posted by haifeng on 2016-04-07 17:21:39 last update 2016-04-07 17:23:10 | Answers (0) | 收藏


Artin 原根猜想(Artin's primitive root conjecture)

对所有 $a\in\mathbb{Z}$, $a\neq 0,\pm 1$, 存在无穷多个素数 $p$ 使得 $a$ 是模 $p$ 的原根.

 

72. Euler 准则(Euler's criterion)

Posted by haifeng on 2016-04-05 20:28:47 last update 2016-04-05 20:28:47 | Answers (1) | 收藏


Euler 准则.

设 $p$ 是一个奇素数, $a$ 是一不能被 $p$ 整除的整数. 则 $a$ 是模 $p$ 的平方剩余当且仅当

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

 

Remark: 证明要用到模素数的剩余构成一个域这个事实.

 

73. 计算 $(-6)^{\frac{101-1}{2}}\mod 101$.

Posted by haifeng on 2016-04-05 19:58:33 last update 2016-04-05 20:09:05 | Answers (1) | 收藏


计算

\[(-6)^{\frac{101-1}{2}}\mod 101\]

 


[Hint]

利用 Euler 准则(Euler's Criterion), 即计算 $\Bigl(\frac{-6}{101}\Bigr)$.

Answer: 

==> jacobi(-6,101).
-: 1

74. 对于 $n=1,2,\ldots,10$, 计算 $\Bigl(\frac{n}{11}\Bigr)$.

Posted by haifeng on 2016-04-05 19:49:30 last update 2016-04-05 19:49:30 | Answers (1) | 收藏


对于 $n=1,2,\ldots,10$, 计算 $\Bigl(\frac{n}{11}\Bigr)$.

75. 二次互反律(Quadratic Reciprocity Law)

Posted by haifeng on 2016-04-05 19:46:28 last update 2016-04-05 19:46:28 | Answers (0) | 收藏


\[
\Bigl(\frac{p}{q}\Bigr)\Bigl(\frac{q}{p}\Bigr)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}
\]

76. Legendre 符号

Posted by haifeng on 2016-04-05 17:33:08 last update 2016-04-05 17:33:08 | Answers (0) | 收藏


Legendre 符号的定义

设 $p$ 是一素数, $a$ 是一整数, Legendre 符号 $\Bigl(\frac{a}{p}\Bigr)$ 的值定义为:

\[
\Bigl(\frac{a}{p}\Bigr)=\begin{cases}
0, & \text{若}\ p|a,\\
1, & \text{若}\ a\ \text{是模}\ p\ \text{的平方剩余},\\
-1, & \text{若}\ a\ \text{不是模}\ p\ \text{的平方剩余}.\\
\end{cases}
\]

这 $a$ 是模 $p$ 的平方剩余(un résidu quadratique modulo $p$) 是指存在整数 $k$ 使得 $a\equiv k^2\pmod p$, 这里 $p\not| k$.

77. 设 $p,q$ 互素, 求 $\sum_{k=0}^{pq-1}(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}$.

Posted by haifeng on 2016-04-05 16:48:45 last update 2016-04-06 01:28:16 | Answers (1) | 收藏


设 $p,q$ 互素, 证明

\[
\sum_{k=0}^{pq-1}(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}=
\begin{cases}
0, & pq\ \text{是偶数},\\
1, & pq\ \text{是奇数}.\\
\end{cases}
\]

 

这里 [ ] 是指取整.

(Proposed by Alexander Bolbot, State University, Novosibirsk)


 

[Hint] 当 $pq$ 为偶数时, 由于 $p,q$ 互素, 故它们的奇偶性不同. 令 $a_k=(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}$, 证明

\[
a_k+a_{pq-1-k}=0.
\]

78. [Thm] 当素数 $p > 5$ 时, $(p-1)!+1$ 不可能是 $p$ 的幂.

Posted by haifeng on 2016-04-04 19:51:48 last update 2016-04-04 19:51:48 | Answers (0) | 收藏


定理. 当素数 $p > 5$ 时, $(p-1)!+1$ 不可能是 $p$ 的幂.

 

Theorem. There is no prime $p$ great than 5 for which $(p-1)!+1$ is a power of $p$.

 


相关定理:

 

Thm.(Wilson's 定理) 若 $p$ 是素数, 则 $(p-1)!+1$ 可被 $p$ 整除.

若 $m$ 是大于 4 的合数, 则 $m|(m-1)!$.

 

 

79. 设 $x_1,x_2,\ldots,x_m$ 是 $m$ 个整数, 证明存在 $1\leqslant k < \ell\leqslant m$, 使得 $\sum_{i=k}^{\ell}x_i\equiv 0\pmod m$.

Posted by haifeng on 2016-04-04 17:09:15 last update 2016-04-04 20:20:14 | Answers (0) | 收藏


设 $x_1,x_2,\ldots,x_m$ 是 $m$ 个整数, 证明存在 $1\leqslant k\leqslant\ell\leqslant m$, 使得

\[
\sum_{i=k}^{\ell}x_i\equiv 0\pmod m
\]

 


 

Remark:

这个结果很神奇, 就比如 2,3,5,7,11,13,17,19 这八个素数, 我们有 $8|(3+5)$ 及 $8|(11+13)$.

打乱顺序也没关系, 比如 2,5,11,3,17,19,7,13.  则 $8|(5+11)$ 及 $8|(2+5+11+3+17+19+7)$.

 

题中 $k\leqslant\ell$ 不能改为 $k < \ell$, 比如考虑 1,0,1 这三个数. 

 

如果题中 $x_i$ 要求是正整数, 则可以改为 $1\leqslant k < \ell\leqslant m$.

80. 若正整数 $n$ 不能被 5 整除, 则有 $n^4\equiv 1\pmod 5$.

Posted by haifeng on 2016-04-04 17:00:43 last update 2016-04-04 17:05:04 | Answers (0) | 收藏


若正整数 $n$ 不能被 5 整除, 则有 $n^4\equiv 1\pmod 5$.

 


[Hint]

完全平方数 $n^2$ 的末尾数字只能是 0, 1, 4, 9, 6, 5. 再次平方, $n^4$ 的末尾数字为 0, 1, 6, 5.

<[4] [5] [6] [7] [8] [9] [10] [11] [12] [13] >