同餘方程是數學中一種常見的方程形式，其一般形式為 \(ax \equiv b \pmod{n}\)，其中 \(a, b, n\) 是已知的整數，\(x\) 是未知數。這種方程在模 \(n\) 的意義下，即 \(n\) 的剩餘類環中，有特定的解。
線性同餘方程的求解方法：
轉化為一般式： 首先將同餘方程轉化為一般線性方程 \(ax + by = c\)，其中 \(a, b, c\) 是整數。
求最大公約數： 計算 \(a\) 和 \(b\) 的最大公約數 \(d = \gcd(a, b)\)。如果 \(d\) 不能整除 \(c\)，則原方程無解。
擴展歐幾里得算法： 如果方程有解，可以通過擴展歐幾里得算法找到一組特解 \((x_0, y_0)\) 使得 \(ax_0 + by_0 = d\)。
求解： 方程的通解可以表示為 \(x = x_0 + \frac{b'}{d} \times t\) 和 \(y = y_0 - \frac{a'}{d} \times t\)，其中 \(t\) 是任意整數，\(a', b'\) 是 \(a, b\) 的整數倍。
乘式求解：
選擇一個與模數 \(m\) 互素的正整數 \(n\)，使得 \(n\) 乘以分母後對 \(m\) 取余的結果為 1。
將方程兩邊同乘以 \(n\)，得到新的等式。
通過不斷乘以模數的逆元，使得分母變為 1，從而得到解。
加式求解：
在分子上加上模數 \(m\) 的倍數，直到分子和分母有公約數。
約去公約數，得到方程的解。
以上方法可以用於求解一般的線性同餘方程。在實際套用中，需要根據具體情況選擇合適的方法進行求解。