1. What is a Linear Congruence?

A linear congruence is an equation of the form \( a x \equiv b \pmod{m} \) where \( a \), \( b \), and \( m \) are integers, and \( x \) is the unknown variable. The solution is all integers \( x \) that satisfy the congruence.

2. How Does the Calculator Work?

The calculator solves the linear congruence equation:

Method: The calculator uses the extended Euclidean algorithm to find solutions. The steps are:

1. Find \( d = \gcd(a, m) \) using the extended Euclidean algorithm
2. If \( d \) doesn't divide \( b \), there are no solutions
3. Otherwise, find one solution \( x_0 \) and generate all solutions as \( x = x_0 + k \cdot \frac{m}{d} \) for \( k = 0, 1, ..., d-1 \)

3. Importance of Linear Congruences

Applications: Linear congruences are fundamental in number theory, cryptography, computer science, and solving Diophantine equations. They're used in RSA encryption, hash functions, and pseudorandom number generation.

4. Using the Calculator

Tips: Enter integer values for \( a \), \( b \), and \( m \) (with \( m > 0 \)). The calculator will find all solutions modulo \( m \) or indicate if no solution exists.

5. Frequently Asked Questions (FAQ)

Q1: When does a linear congruence have solutions?
A: A solution exists if and only if \( \gcd(a, m) \) divides \( b \).

Q2: How many solutions are there?
A: If solutions exist, there are exactly \( d = \gcd(a, m) \) distinct solutions modulo \( m \).

Q3: What if a and m are not coprime?
A: The equation can still have solutions if \( \gcd(a, m) \) divides \( b \). The calculator handles this case.

Q4: Can the modulus be negative?
A: The modulus \( m \) must be positive. Negative values are treated as their absolute value.

Q5: What about non-integer solutions?
A: The calculator only finds integer solutions as congruences are defined over integers.