Congruences · Definition

Linear congruence

elementary number theorycongruences

Before you start you need to know

Linear congruences generalize linear equations to modular arithmetic. Their solution depends on whether the coefficient a is invertible modulo m.

Definition

A linear congruence is a first-degree congruence in one unknown \(x\), with integer coefficients \(a\), \(b\) and modulus \(m\); its solutions are the integers \(x\) that satisfy it.

\[ax \equiv b \pmod{m}\]

If \(\gcd(a,m)=1\), the congruence has exactly one solution modulo m, obtained by multiplying both sides by the modular inverse of a. If \(\gcd(a,m)=d\) divides b, the congruence has exactly d solutions modulo m, and no solution if d does not divide b.

To solve \(3x \equiv 2 \pmod{7}\), since \(\gcd(3,7)=1\) and \(3\cdot 5=15\equiv 1 \pmod{7}\), the inverse of 3 is 5. Multiplying by 5 gives \(x\equiv 10\equiv 3 \pmod{7}\).

A typical mistake is dividing both sides by a without checking the greatest common divisor, such as concluding that \(2x\equiv 4 \pmod{6}\) implies \(x\equiv 2 \pmod{6}\), when in fact there are d=2 solutions modulo 6.

Think about it

Why does \(2x \equiv 1 \pmod{4}\) have no solution?

Because \(\gcd(2,4)=2\) does not divide 1.

Exercises 10

  1. What is the modular inverse of 3 modulo 7?
  2. What is the greatest common divisor of 4 and 6?
  3. How many solutions modulo 10 does the congruence \(3x \equiv 1 \pmod{10}\) have?
  4. Does the congruence \(2x \equiv 1 \pmod{4}\) have a solution?
  5. What is the value of x in \(x \equiv 3 \pmod{5}\) that lies between 0 and 4?
  6. Solve \(3x \equiv 2 \pmod{7}\). What is the solution modulo 7?
  7. Solve \(5x \equiv 4 \pmod{9}\). What is the solution modulo 9?
  8. Solve \(2x \equiv 4 \pmod{6}\). How many solutions modulo 6 does it have?
  9. Solve \(4x \equiv 2 \pmod{10}\). What is the set of solutions modulo 10?
  10. Find all solutions of \(6x \equiv 9 \pmod{15}\) modulo 15.

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 4
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2