Question

19)解下列同余式:-|||-(1) 3x=8(mod 31 );-|||-(2) 47x-10=0(mod 107).

Answer 1

问：19)解下列同余式:-|||-(1) 3x=8(mod 31 );-|||-(2) 47x-10=0(mod 107).

答：首先，将方程两边同时取模： 3x ≡ 8 (mod 31) 等价于 3x mod 31 = 8 mod 31 然后，利用模幂运算法则 A^B mod C = ((A mod C)^B) mod C，将 3^(-1) 作为左侧乘数，两边同时乘以该数： 3^(-1) × 3x ≡ 3^(-1) × 8 (mod 31) 即 x ≡ 3^(-1) × 8 (mod 31) 接下来，需要求解模 31 意义下的逆元 3^(-1)。 由于 31 是质数，因此根据费马小定理可以得到： 3^(30) ≡ 1 (mod 31)。 进而推得： 3^(-1) ≡ 3^(30-1) ≡ 3^29 (mod 31)。 因此，原方程的解为： x ≡ 3^(-1) × 8 (mod 31) x ≡ 3^29 × 8 (mod 31) x ≡ 18 (mod 31) 所以，方程 3x=8(mod 31) 的解是在模 31 意义下 x ≡ 18。

答：# 47x - 10 ≡ 0 (mod 107) 47x - 10 ≡ 0 (mod 107) 可以理解为107是模数，这个等式的含义是：(47x - 10)可以被107整除。为了解这个方程，同样可以用模重复减的方法，即：47x - 10 ≡ 0 (mod 107) 47x ≡ 10 (mod 107) 使用扩展欧几里得算法求最大公约数： 107 = 2 × 47 + 13 47 = 3 × 13 + 8 13 = 1 × 8 + 5 8 = 1 × 5 + 3 5 = 1 × 3 + 2 3 = 1 × 2 + 1 由此可得，最大公约数是1。 继续套用扩展欧几里得算法模板，求得其中一组可行解： 1 = 3 - 2 × 1 1 = 3 - (5 - 3) × 1 1 = 2 × 3 - 5 1 = 2 × (8 - 5) - 5 1 = 2 × 8 - 3 × 5 1 = 2 × 8 - 3 × (13 - 8) 1 = 5 × 8 - 3 × 13 1 = 5 × (47 - 3 × 13) - 3 × 47 1 = 5 × 47 - 18 × 13 1 = 5 × 47 - 18 × (107 - 2 × 47) 1 = 41 × 47 - 18 × 107 这表明，对于模数107，47的逆元为41，即47x ≡ 1 (mod 107) 的解为41。两边同时乘10，得：47x ≡ 10 (mod 107) 41 × = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x = × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × 56 因此，方程的所有解可以表示为x = + ，其中n为任意整数。"

问：第一题能不能也用第二题的方法

答：亲亲，3x ≡ 8 (mod 31) 可以理解为31是模数，这个等式的含义是：(3x - 8) 可以被31整除。为了解这个方程，可以用模重复减的方法，即： 3x ≡ 8 (mod 31) -23x ≡ -62 (mod 31) 模31加减法（即加上31或减去31）：8 + 31 = 39 ≡ 8 (mod 31)，所以： 3x ≡ 39 (mod 31) 同理，可以继续重复减去31，直到得到x的值： 3x ≡ 39 (mod 31) 3x ≡ 70 (mod 31) 3x ≡ 101 (mod 31) 3x ≡ 132 (mod 31) 3x ≡ 163 (mod 31) 可知3x ≡ 163 (mod 31)，即： 3x = 163 + 31n (n为任意整数) 为了解x的具体值，需要再进一步约束x的取值范围，例如在模31的情况下x的取值范围是0到30，因为这些余数在模31时完全取遍。所以，还需要列出所有不超过模数31的解并验证： 3x = 163 + 31n x = (163/3 + 31n/3) 163/3 = 54余1，31/3 = 10余1，所以： x ≡ 11 (mod 31) 即x ≡ 11，是这个方程在模数31下的一个解。