[問題]同餘
第1頁(共1頁)
由 Raceleader 於 星期一 五月 19, 2003 5:38 pm
We require 1978m(1978n-m - 1) to be a multiple of 1000=8.125. So we must have 8 divides 1978m, and hence m >= 3, and 125 divides 1978n-m - 1.
By Euler's theorem, 1978f(125) =1 (mod 125). f(125) = 125 - 25 = 100, so 1978100 =1 (mod 125). Hence the smallest r such that 1978r= 1 (mod 125) must be a divisor of 100 (because if it was not, then the remainder on dividing it into 100 would give a smaller r). That leaves 9 possibilities to check: 1, 2, 4, 5, 10, 20, 25, 50, 100. To reduce the work we quickly find that the smallest s such that 1978s =1 (mod 5) is 4 and hence r must be a multiple of 4. That leaves 4, 20, 100 to examine.
We find 9782 = 109 (mod 125), and hence 9784 = 6 (mod 125). Hence 97820 =65 = 36.91 = 26 (mod 125). So the smallest r is 100 and hence the solution to the problem is 3, 103.
By Euler's theorem, 1978f(125) =1 (mod 125). f(125) = 125 - 25 = 100, so 1978100 =1 (mod 125). Hence the smallest r such that 1978r= 1 (mod 125) must be a divisor of 100 (because if it was not, then the remainder on dividing it into 100 would give a smaller r). That leaves 9 possibilities to check: 1, 2, 4, 5, 10, 20, 25, 50, 100. To reduce the work we quickly find that the smallest s such that 1978s =1 (mod 5) is 4 and hence r must be a multiple of 4. That leaves 4, 20, 100 to examine.
We find 9782 = 109 (mod 125), and hence 9784 = 6 (mod 125). Hence 97820 =65 = 36.91 = 26 (mod 125). So the smallest r is 100 and hence the solution to the problem is 3, 103.
-
Raceleader - 訪客
第1頁(共1頁)