You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.0 KiB
1.0 KiB
问题：13能否整除9^{36}-1、9^{39}-1?
费马小定理
假如p是质数，且gcd(a,p)=1，那么 \huge \displaystyle a^{p-1}≡1\ (mod \ p)
本题中，p=13，是质数。a=9,gcd(a,p)=1,满足费马小定理，所以利用其得到结论：
\large \displaystyle \because 9^{p-1}=9^{13-1}=9^{12}
\large \displaystyle \therefore 9^{12}\equiv 1 (mod \ 13)
\large \displaystyle \therefore (9^{12})^3\equiv 1 (mod \ 13)
即
\large \displaystyle \therefore 9^{36}\equiv 1 (mod \ 13)
也就是\large \displaystyle 13 | 9^{36} -1
再来看一下\large \displaystyle 9^{39}-1:
\large \displaystyle 9^{39}\equiv 9^{36} \times 9^3 (mod \ 13)
\large \displaystyle \because 9^{36} \equiv 1 (mod \ 13)
\large \displaystyle 9^3=729=(13 \times 56 +1)=1 (mod \ 13)
也就是\large \displaystyle 13 | 9^{39} -1
总结： 望文知义，看着像就往定理上套，这个思路很明显啊，王道！