Question

89个143相乘的积除以7的余数

Answer 1

先说一下，a^b表示a的b次方，于是89个143相乘写成143^89。
不清楚你是否学过同余，如果学过，见方法二和方法三；如果没学过，见方法一。
方法一：找规律：
先铺垫一个性质。
——————————————————————
乘积的余数相当于余数乘积的余数。
——————————————————————
下面证明。
假设
p÷a=b……c
q÷a=d……e
那么
p=ab+c，q=ad+e
pq=aabd+abe+adc+ce
注意到，aabd+abe+adc是a的倍数
因而pd÷a的余数相当于ce÷a的余数。
回到这个问题。
143÷7=20……3
因而，143^89÷7的余数相当于3^89÷7的余数。
3^1÷7=？……3
3^2÷7=？……2
3^3÷7=？……6
3^4÷7=？……4
3^5÷7=？……5
3^6÷7=？……1
3^7÷7=？……3
3^8÷7=？……2
3^9÷7=？……6
3^10÷7=？……4
3^11÷7=？……5
3^12÷7=？……1
3^13÷7=？……3
3^14÷7=？……2
3^15÷7=？……6
...
可以看出，这个是周期问题，周期=6
而89÷6=？……5
因而3^189÷7对应着3^5÷7=？……5
——————————————————————————————————————————
方法二：同余
143^89（mod 7）
≡3^89
≡(3^2)^44×3
≡9^44×3
≡2^44×3
≡(2^3)^14×2^2×3
≡8^14×12
≡1^14×5
≡5
_____________________________________________________________
方法三：费马小定理
对于质数p，对任意不是p的倍数a都有：a^(p-1)≡1（mod p）
那么
3^6≡1（mod 7）
于是
(3^6)^14×3^5≡1×3^5（mod 7）
3^5≡5（mod 7）
【经济数学团队为你解答！】