题目

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),并证明你的答案.

提问时间：2021-03-26

答案

1.18x≡1(mod 31)即18x-1=31y18x-31y=1方程有整数解当且仅当18和31互素（31是素数,所以显然互素）用辗转相除法求得x和y的一个特解7*31-12*18=1于是x≡-12(mod 31)即x≡19(mod 31)2.同理,因为18和33不互素,因此无反比...