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

71. 计算 $(-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

72. 对于 $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)$.

73. 二次互反律(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}}
\]

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

75. 设 $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.
\]

76. [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)!$.

 

 

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

78. 若正整数 $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.

79. [Thm]Lucas 定理

Posted by haifeng on 2016-04-04 16:45:58 last update 2016-04-04 16:50:21 | Answers (0) | 收藏


Lucas 定理

设 $p$ 素数, $m$ 和 $n$ 是非负整数. 则

\[
\binom{m}{n}\equiv\prod_{i=0}^{k}\binom{m_i}{n_i}\pmod p
\]

其中

\[
\begin{aligned}
m&=m_k p^k+m_{k-1}p^{k-1}+\cdots+m_1 p+m_0,\\
n&=n_k p^k+n_{k-1}p^{k-1}+\cdots+n_1 p+n_0,\\
\end{aligned}
\]

约定 $\binom{m}{n}=0$, 如果 $m < n$.


 

一个直接推论是 $p|\binom{m}{n}$ 当且仅当存在 i, 使得 $n_i > m_i$.

 


例子: 设 $p$ 是素数, $m\geqslant 1$, $0\leqslant k\leqslant p-1$, 证明

\[
\binom{mp+k}{p}\equiv m\pmod p
\]

 

 


References:

https://en.wikipedia.org/wiki/Lucas%27_theorem

 

80. 正整数 $a,b,c$ 都是两位数, 且 $a,b$ 的个位数字分别是 7 和 5. $c$ 的十位数字是 1.

Posted by haifeng on 2016-04-03 20:18:38 last update 2021-06-19 08:01:38 | Answers (1) | 收藏


正整数 $a,b,c$ 都是两位数, 且 $a,b$ 的个位数字分别是 7 和 5. $c$ 的十位数字是 1. 如果它们满足

\[
a\times b+c=2005,
\]

求这三个数的和.

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