关于余数的问题

noss

关于余数的问题的，我对于余数的概念掌握的很不好，很多都忘了，这个边有两道很类似的余数的题，

希望高人指点：

1. The reminder of 3^(50)/4?

2.  The reminder of 3^(11)/5?

thunderPeak

不是高人，共同切磋切磋。

设任意一个自然数K. 求其被一个自然数M除的余数，这很简单，有0，1，。。。M-1种可能。那么， K^2呢？

若K/M余1， 则设K = nM + 1， K^2 = (nM)^2 + 2nM + 1, 可知K的任意次方除M仍然余1!
若K/M余M-1, 则设K = jM - 1，   K^2 = (jM)^2 - 2jM + 1,    可知K的平方除M余1!

所以，这种题的关键是构造K/M余1或M-1的数

例1。 The reminder of 3^(50)/4? （K=3, M = 4)
3 = 4-1。 由上可知，3^2 = 9 必然为除M余1
3^50 = 9^25。 由上，9的任意次方除4仍然余1， 题破。

例2。The reminder of 3^(73)/5?（K=3, M = 5)

3 = 5 - 2， 需要一些转换。若K/5余3，则设K = 5n - 2， K^2 = 25n - 10n + 4,  可知K的平方除5余4(M-1).
3^(73) = 3 * 9^36

延此思路，9的平方是我们需要的余1的数：3 * 9^36 = 3 * 81^18

由此知K= 3(5N + 1), 答案为3.

 

noss

兄弟你太牛了，不是数学系的吧：）

thunderPeak

no no no, I am the legendary.... 菜鸟...