与2019指数幂有关的同余问题

青青子衿

怎么较为有效率地笔算出
\begin{align*}
\left(2^{2019}+1\right)^{2019}\equiv 9^3 \pmod{2019}\,
\end{align*}
我是先求这个的：
\begin{align*}
2^{2019}+1\equiv 9 \pmod{2019}\,
\end{align*}

1. Multicolumn[Table[Mod[(2^2019 + 1)^k, 2019], {k, 200}], {84, Automatic}]

Copy the Code

realnumber

好象也这样的，质因数分解2019=3×673，
$3\mid (2^{2019}+1)$---(1)
$2^{2019}+1=8^{673}+1=8+1=9\mod 673$(因为$a^{p-1}=1\mod p$其中(a,p)=1,p为质数)
$(2^{2019}+1)^{2019}=(2^{2019}+1)^3=9^3\mod 673$
即$(2^{2019}+1)^{2019}=9^3+673k,k\in Z$
又由(1)得$3\mid k,k=3t,t\in Z$
所以$(2^{2019}+1)^{2019}=9^3+2019t,t\in Z$
即$(2^{2019}+1)^{2019}=9^3\mod 2019$

tommywong

$\lambda(2019)=[\lambda(673),\lambda(3)]=672$

$x^{672+1}\equiv x\pmod{2019}$

$(2^{2019}+1)^{2019}\equiv (2^3+1)^3\equiv 9^3\pmod{2019}$