Solve linear congruence equation a·x ≡ b (mod m) for all integer solutions
a · x ≡ b (mod m)
a =
b =
m =
Calculation Result
Equation
Step-by-Step Derivation
Solvability Condition
ax ≡ b (mod m) is solvable ⟺ gcd(a, m) | b
Meaning: The greatest common divisor of a and m must divide b
If solvable, total solutions = gcd(a,m)
Linear congruence equations are fundamental tools in number theory and cryptography, widely used in RSA encryption, linear congruential generators and the Chinese Remainder Theorem.
⚠If gcd(a,m)=1, a has a unique modular inverse a⁻¹ modulo m, and the solution is x ≡ b·a⁻¹ (mod m). This tool handles cases with gcd(a,m)>1 and outputs all distinct solutions.
What Is a Congruence Equation?
A linear congruence equation has the standard form ax ≡ b (mod m). It implies a−b is divisible by m, so a and b leave the same remainder when divided by m. It is an essential building block for number theory and modern cryptography.
Congruence Definition
a ≡ b (mod m) means a−b is divisible by m. Both integers have identical remainders modulo m, for example 17≡5 (mod 12).
Solvability Rule
ax ≡ b (mod m) has solutions if and only if gcd(a,m) divides b. The total number of distinct solutions equals d=gcd(a,m).
Modular Inverse
When gcd(a,m)=1, a has a unique inverse a⁻¹ satisfying a·a⁻¹≡1(mod m). The solution becomes x≡b·a⁻¹(mod m).
Extended Euclidean Algorithm
This algorithm calculates gcd(a,m) and finds integers u,v such that au+mv=gcd(a,m), used to compute modular inverse and general solutions.
💡 Example: Solve 3x ≡ 4 (mod 7). gcd(3,7)=1, so a unique solution exists. The inverse of 3 mod 7 is 5 (3×5=15≡1 mod 7). Then x=4×5=20≡6(mod 7). Verify: 3×6=18≡4(mod 7) ✓.
Application Scenarios
RSA EncryptionChinese Remainder TheoremModular ArithmeticCryptographyMath Contest Number Theory
Frequently Asked Questions
What is a linear congruence equation?▼
A linear congruence equation follows the form ax≡b (mod m). It means a−b is divisible by m, and a and b share the same remainder when divided by m.
Does every congruence equation have a solution?▼
No. The equation ax≡b (mod m) has integer solutions if and only if gcd(a,m) divides b. For example, 2x≡3 (mod 4) has no solution since gcd(2,4)=2 cannot divide 3.
How do you find the general solution?▼
Let d=gcd(a,m). If d divides b, divide a,b,m by d to get a'x≡b'(mod m'). Use the extended Euclidean algorithm to find the modular inverse of a', then the general solution is x = x₀ + k×(m/d).
What is the extended Euclidean algorithm?▼
The extended Euclidean algorithm computes the greatest common divisor gcd(a,b) and finds integers x and y satisfying ax+by=gcd(a,b). It is widely used to calculate modular inverse and solve congruence equations.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.