Linear Congruence Calculator
Solve linear congruences of the form ax ≡ b (mod m) and find all solutions.
Linear Congruence Input
Enter the coefficients for the linear congruence ax ≡ b (mod m):
Coefficient of x
Right side constant
Modulus (≥ 2)
Current Congruence:
Solution
Congruence:
Solutions:
All Solutions (mod m):
Solution Steps
Step 1: Check Solvability
Step 2: Extended Euclidean Algorithm
Step 3: Construct Solution
No Solution
Reason:
Explanation:
A linear congruence ax ≡ b (mod m) has a solution if and only if gcd(a,m) divides b. Since this condition is not satisfied, there is no solution to this congruence.
About Linear Congruences
What is a Linear Congruence?
A linear congruence is an equation of the form ax ≡ b (mod m), where we want to find all values of x that satisfy the equation. This is fundamental in number theory and has applications in cryptography, computer science, and mathematics.
Solution Method
- Check Solvability: Calculate gcd(a,m). The congruence has a solution if and only if gcd(a,m) divides b.
- Find Inverse: If solvable, use the Extended Euclidean Algorithm to find the modular inverse of a/gcd(a,m) modulo m/gcd(a,m).
- Construct Solutions: The general solution is x ≡ x₀ + k(m/gcd(a,m)) (mod m), where x₀ is a particular solution.
- List All Solutions: There are exactly gcd(a,m) distinct solutions modulo m.
Examples
Example 1: Unique Solution
- a = 3, b = 7, m = 10
- 3x ≡ 7 (mod 10)
- gcd(3,10) = 1, and 1 divides 7
- Solution: x ≡ 9 (mod 10)
Example 2: Multiple Solutions
- a = 6, b = 9, m = 15
- 6x ≡ 9 (mod 15)
- gcd(6,15) = 3, and 3 divides 9
- Solutions: x ≡ 4, 9, 14 (mod 15)
Applications
- Cryptography: RSA encryption, Diffie-Hellman key exchange
- Computer Science: Hash functions, random number generation
- Mathematics: Solving systems of congruences, Chinese Remainder Theorem
- Calendar Calculations: Day of the week calculations