本帖最后由 业余的业余 于 2019-3-16 00:57 编辑
求 $2019!$ 的 $455(=5\times 7 \times 13)$ 进制表示数去掉尾部零后的个位数的十进制表示数。和主贴问题 $2$ 完全一样的处理。运用上面的一些技巧可使计算量尽可能的小,小到笔算可轻易解决。
辅助表 (除 13)
数 商 余
2019 155 4
155 11 12
11 0 11
和 166
用类似的方法定义 $a_k$, 以下说不通的地方都是省略了模 13。 $a_{12}\equiv -1, a_{11}\equiv 1, a_4\equiv -2$
记 $m=\cfrac {2019!}{13^{166}}$, 则 $m\equiv (-1)^{166}a_4a_{12}a_{11}\equiv (-2)(-1)(1)\equiv 2 \pmod{13}$
于是 $\cfrac m{5^{166}7^{166}}\equiv \cfrac 2{35^{10}}\equiv \cfrac 2{(-4)^{10}}\equiv \cfrac 1{2^{19}} \equiv \cfrac 1{2^7} \pmod{13}$
上面利用了 $\varphi(13)=12, 5^{12}\equiv 7^{12}\equiv 2^{12}\equiv 1 \pmod{13}$
$2^7=128$, 如果有一定的编程经验,这个应该是印在脑子里的了。问题变成了求 $128$ 的 inverse modulo 13, 可以用上面的扩展欧几里得算法求解,即求 $128 x +13y=1$ 的整数解中的 $x$
$\begin{align*}
11&=128-9\times 13=(1,-9)\\
2&=13-11=(0,1)-(1,-9)=(-1,10)\\
1&=11-5\times 2=(1,-9)-5(-1,10)=(6,-59)
\end{align*}$
$6$ 是所求的 $x$. 我曾经想硬抗,发现数字大了还是用普遍接受的算法来得快、稳、准。
(注。以上略笨, $\cfrac 1{128}\equiv \cfrac 1{-2}\equiv \cfrac 1{11} \pmod{13}$, 答案当然仍然是 $6$, 数字小多了 )
于是,所求的数
1. 除 $13$ 余 $6$,
2. 在 $1$ 到 $454$ 之间的整数
3. 是 $5\times 7=35$ 的倍数。
即 $35x\equiv 6 \pmod{13}$, 或 $35x+13y=6$ 又是一个扩展欧几里得算法问题,不嫌啰嗦的话,把草稿纸上的内容再罗列一遍:
如果有 $35x+13y=1$ 的话,显然 $x'=6x,y'=6y$ 是原方程的解.
$\begin{align*}
4&=-35+3\times 13=(-1,3)\\
1&=9\times 4 -35=9(-1,3)-(1,0)=(-10,27)
\end{align*}$
所以 $-10$ 是新方程的解, $-60$ 是原方程的解,$-60\equiv 5\pmod{13}$, $35\times 5=175$ 是所求的答案。检验 $175\equiv 6\pmod{13}$ |