课堂作业——关于同余的一些证明 (No more in progress)

体现Lifanの高级摄影技巧的题目图片

Problem200719-image


T5

我 不 会,长 大 后 再 学 习

T6

真解法

Solution(Really)

所以 2⁶⁸ mod 19 = 6

假解法

由 $2^{68} = 2^{18^3} \times 2^{14}$

和 $2 \equiv 1 \ (\mathrm{mod \ 19})$ 易得

$2^{54} \equiv 1 \ (\mathrm{mod \ 19})$

$2^{54} \times 2^{14} \equiv 2^{14} \ (\mathrm{mod \ 19})$

$2^{68} \equiv 2^{14} \ (\mathrm{mod \ 19})$

接下来经过一顿魔法操作我们可以轻易得出   $2^{14} \ \mathrm{mod \ 19} = 6$

$\therefore 2^{68} \ \mathrm{mod \ 19} = 6$

T7

$\begin{equation} \begin{aligned}
a^{25} - a &= a(a^{24} - 1)
\\&= a(a^{12} + 1)(a^{12} - 1)
\\&= a(a^{12} + 1)(a^{6} + 1)(a^{6} - 1)
\\&= a(a^{12} + 1)(a^{6} + 1)(a^{3} + 1)(a^{3} - 1)
\\&= a(a^{12} + 1)(a^4 - a^2 + 1)(a^2 + 1)(a^2 - a + 1)(a + 1)(a^2 + a + 1)(a - 1)
\end{aligned} \end{equation}$

$\because a(a + 1)$ 必为偶数 $, (a - 1)a(a + 1)$ 必为 $3$ 的倍数

$\therefore 6 \ | \ a^{25} - a$

令 $a = 5k$ ,此时 $a$ 为 $5$ 的倍数,故符合。

令 $a = 5k + 1$ ,此时 $a - 1$ 为 $5$ 的倍数,故符合。

令 $a = 5k + 4$ ,此时 $a + 1$ 为 $5$ 的倍数,故符合。

当 $a = 5k + 2$ 时,$a^2 + 1 = 25k^2 + 20k + 4 + 1 = 25k^2 + 20k + 5 = 5(5k^2 + 4k + 1)$ 此时 $a^2 + 1$ 为 $5$ 的倍数,故符合。

当 $a = 5k + 3$ 时,$a^2 + 1 = 25k^2 + 30k + 9 + 1 = 25k^2 + 30k + 10 = 5(5k^2 + 6k + 2)$ 此时 $a^2 + 1$ 为 $5$ 的倍数,故符合。

$\therefore 5 \ | \ a^{25} - a$

$\therefore 30 \ | \ a^{25} - a$

$\therefore a^{25} \equiv a \ (\mathrm{mod \ 30})$

点赞
  1. Google Chrome Windows 10

    Latex炸了差评 :zhenbang:

    1. potatoAdmin说道:
      Google Chrome Windows 10

      这里的Latex用的MathJax官方库,在大陆访问性能可能不太稳定

发表评论

电子邮件地址不会被公开。必填项已用 * 标注