同余方程求解疑问：验证试错法解70x≡36(mod198)是否正确

你的试错法思路完全正确！而且你找到的x=9确实是这个方程的最小正整数解，咱们先验证一下：
计算 70 * 9 = 630，用630除以198：198 * 3 = 594，630 - 594 = 36，刚好和模运算的余数要求一致，所以这个解是对的。

试错法本身是一种非常直观且有效的方法，尤其是当模（这里是198）不算特别大的时候：你只需要在0到197的范围内逐个尝试x的值，检查70x mod 198是否等于36，逻辑简单、容易上手，只要计算时细心一点，完全能得到正确结果。

当然，如果遇到模特别大的情况，试错法的效率会很低，这时候可以用更系统的数论方法来求解，比如：

• 先判断方程是否有解：计算70和198的最大公约数gcd(70,198)=2，而2能整除36，所以方程有解；
• 将方程两边和模同时除以2，得到简化后的方程：35x≡18 mod 99；
• 找35在模99下的逆元（因为35和99互质，逆元存在），用扩展欧几里得算法可以算出逆元是17；
• 最后计算x≡18*17 mod 99，18*17=306，306 mod 99=9，和你试错得到的结果完全一致。

总之，你的试错法是正确的，得到的解也没问题，这种方法在小模场景下非常实用。

内容的提问来源于stack exchange，提问作者user529514