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.
34 lines
1.0 KiB
34 lines
1.0 KiB
2 years ago
|
### 问题：$13$能否整除$9^{36}-1$、$9^{39}-1$?
|
||
|
|
|
||
|
|
#### 费马小定理
|
||
|
|
|
||
|
|
假如$p$是质数，且$gcd(a,p)=1$，那么 <font color='red'><b>$$\huge \displaystyle a^{p-1}≡1\ (mod \ p)$$
|
||
|
|
</b></font>
|
||
|
|
|
||
|
|
本题中，$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 $
|
||
|
|
|
||
|
|
<font color='red'><b>总结：</b></font>
|
||
|
|
望文知义，看着像就往定理上套，这个思路很明显啊，王道！
|