m是正整数,a和b都是整数,如果ab≡1(modm),那么可以说成整数b是整数a（modm）的反比.问：（a)18有没有反比(mod31)如果有,找出它并在0到m-1的范围内给出一个答案,如果没有,解释为什么.

Question

m是正整数,a和b都是整数,如果ab ≡ 1 (mod m),那么可以说成 整数 b 是整数 a （mod m）的反比.
问：
（a) 18 有没有反比 (mod 31) 如果有,找出它并在0到m-1的范围内给出一个答案,如果没有,解释为什么.
（b) 18 有没有反比 (mod 33) 如果有,找出它并在0到m-1的范围内给出一个答案,如果没有,解释为什么.
（c)在整数1,2,3,...,m 内,有多少个整数有反比 （mod m),并证明你的答案.

Answer 1

1.
18x≡1(mod 31)
即18x-1=31y
18x-31y=1
方程有整数解当且仅当18和31互素（31是素数,所以显然互素）
用辗转相除法求得x和y的一个特解
7*31-12*18=1
于是x≡-12(mod 31)
即x≡19(mod 31)
2.同理,因为18和33不互素,因此无反比(mod 33)
3.如果18和m互素,则在连续m个数内有且仅有1个反比；做法同上
如果不互素,则没有反比.
参考二元一次不定方程的相关理论