费马小定理 练习题

hbghlyj

数论 2021 sheet 1
讲义 pdf
$(m,n)$ 表示 $m$ 和 $n$ 的最大公约数。

• 设 $a$ 是一个正整数，并且它的十进制展开有 7 位数字：$a=a_{0}+10 a_{1}+\cdots+1000000 a_{6}$。证明当且仅当 $a_{0}+3 a_{1}+2 a_{2}-a_{3}-3 a_{4}-2 a_{5}+a_{6}$ 能被 7 整除时，$a$ 能被 7 整除。
• 找一个正整数 $x$，使得 $x \equiv 3\pmod 4, 2 x \equiv 5\pmod 9$ 和 $7 x \equiv 1\pmod{11}$。
• 找出最小的正整数 $x$，使得 $x \equiv 11\pmod{59}$ 和 $x \equiv 29\pmod{71}$。
• 证明 $2^{340} \equiv 1\pmod{341}$。结合费马小定理对此进行评论。
• 设 $n=(6 t+1)(12 t+1)(18 t+1)$，其中 $6 t+1,12 t+1$ 和 $18 t+1$ 都是质数。证明当 $(a, n)=1$ 时，
  $$
  a^{n-1} \equiv 1\pmod n
  $$
  结合费马小定理对此进行评论。
• 证明如果 $x$ 是一个整数，那么 $x^{10} \in\{-1,0,1\}\pmod{25}$。
• 对于哪些 $N$，以下命题成立：如果你取一个 $N$ 位数，反转它的数字，然后将结果加到原数上，你总是得到 11 的倍数？
• 找出所有质数 $p$，使得映射 $\phi: \mathbb{Z} / p \mathbb{Z} \rightarrow \mathbb{Z} / p \mathbb{Z}$ 定义为 $\phi(x)=$ $x^{13}$ 是一个群同态。
• 找出所有四位数 $N$，使得当用十进制表示时，$N$ 的任何幂的最后四位数字与 $N$ 的数字相同。
• 对于以下每个性质，证明存在无穷多个正整数 $n$ 不具有该性质。
  (i) $n$ 是至多 3 个平方数的和；
  (ii) $n$ 是至多 8 个六次幂的和；
  (iii) $n$ 是至多 11 个十次幂的和；
  (iv) $n$ 是至多 15 个四次幂的和；
  (v) $n$ 是至多 7 个（正）七次幂的和。
  

hbghlyj

1. 注意到$10^1\equiv3\pmod7,10^6\equiv1\pmod7$即可

2.
设 x = 4k + 3. 代入第二式，
2x = 8k + 6 ≡ 5(mod 9)
8k ≡ −1(mod 9)
k ≡ 1(mod 9)
设 k = 9m + 1，则 x = 4(9m + 1) + 3 = 36m + 7. 代入第三式，
7x = 252m + 49
252m + 49 ≡ 1(mod 11)
21m ≡ −4(mod 11)
m ≡ 4(mod 11)
m = 11n + 4
x = 36(11n + 4) + 7 = 396n + 151.
所以 x 是 ≡151(mod 396) 的任意正整数。

3.
设 x = 59k + 11. 代入第二式，
59k + 11 ≡ 29(mod 71)
59k ≡ 18(mod 71)
−12k ≡ 18(mod 71)
−2k ≡ 3(mod 71)
k ≡ −36 × 3 ≡ 34(mod 71)
k = 71m + 34
x = 59(71m + 34) + 11 = 4189m + 2017.
所以 x 是 ≡2017(mod 4189) 的任意正整数。

4. 费马伪素数

10. (i) 设$n=8k+7$，$n$不能写成3个平方数的和。
(ii)

tommywong

5.
$(a,n)=1\implies (a,6t+1)=(a,12t+1)=(a,18t+1)=1$
$a^{36t}\equiv a^{6t}\equiv 1\pmod{6t+1}$
$a^{36t}\equiv a^{12t}\equiv 1\pmod{12t+1}$
$a^{36t}\equiv a^{18t}\equiv 1\pmod{18t+1}$
$a^{36t}\equiv 1\pmod{n}$
$a^{n-1}\equiv a^{1296t^3+396t^2+36t}\equiv 1\pmod{n}$

6.
$\color{red}{r^2 \in\{-1,0,1\}\pmod{5}}$
$\color{red}{r^{10} \in\{-1,0,1\}\pmod{5}}$
$\color{green}{r\in\{-2,-1,0,1,2\}}$
$\color{green}{r^{10}\in\{0,1,2^{10}\}\pmod{25}}$
$\color{green}{2^{10}\equiv 1024\equiv -1\pmod{25}}$
$\color{green}{r^{10}\in\{-1,0,1\}\pmod{25}}$
Let $x=5q+r$
$\displaystyle x^{10}\equiv (5q+r)^{10}\equiv \sum_{k=0}^{10}\binom{10}{k}(5q)^{10-k}r^k$
$\equiv r^{10}\in\{-1,0,1\}\pmod{25}$

7.
$\displaystyle \sum_{k=0}^{N-1}10^k a_k+\sum_{k=0}^{N-1}10^{N-1-k} a_k
\equiv\sum_{k=0}^{N-1}(-1)^k(1+(-1)^{N-1})a_k$
$\equiv\begin{cases} 0\pmod{11} & N\equiv 0\pmod{2}\\
\displaystyle 2\sum_{k=0}^{N-1}10^ka_k\pmod{11} & N\equiv 1\pmod{2}\end{cases}$
N是偶數時總是得到11的倍數。
如果N是奇數，當且僅當N位數是11的倍數時得到11的倍數。

不想做8,9,10了

tommywong

hbghlyj 发表于 2024-11-14 18:16
由上一步的 $r^{10} \in\{-1,0,1\}\pmod{5}$
是如何得出 $r^{10}\in\{-1,0,1\}\pmod{25}$ 的呢？ ...

我搞錯了
重做
$r\in\{-2,-1,0,1,2\}$
$r^{10}\in\{0,1,2^{10}\}\pmod{25}$
$2^{10}\equiv 1024\equiv -1\pmod{25}$
$r^{10}\in\{-1,0,1\}\pmod{25}$

hbghlyj

第10題“find infinitely numbers that can't be expressed by at most 7 seventh powers”
我还得想想

如果你有思路可以说一下

按理来说方法是你找一个a，然后任何数的7次方modulo这个数a等于一些值，然后发现7个这样的值组合起来不能等于某个数

但它确实很难计算