Overview

congruence equation


Show Summary Details

Quick Reference

The following are examples of congruence equations:(i)x+5 ≡ 3 (mod 7); this has the solution x ≡ 5 (mod 7).(ii) 2x ≡ 5 (mod 4); this has no solutions.(iii)x2 ≡ 1 (mod 8); this has solutions x ≡ 1,3,5 or 7 (mod 8).(iv)x2+2x+3≡ 0 (mod 6); this has solutions x ≡ 1 or 3 (mod 6).In seeking solutions to a congruence equation, it is necessary only to consider a complete set of residues and find solutions in this set. The examples (i) and (ii) above are linear congruence equations. The linear congruence equation axb (mod n) has a solution if and only if (a, n) divides b, where (a, n) is the greatest common divisor of a and n.

(i)x+5 ≡ 3 (mod 7); this has the solution x ≡ 5 (mod 7).

(ii) 2x ≡ 5 (mod 4); this has no solutions.

(iii)x2 ≡ 1 (mod 8); this has solutions x ≡ 1,3,5 or 7 (mod 8).

(iv)x2+2x+3≡ 0 (mod 6); this has solutions x ≡ 1 or 3 (mod 6).

Subjects: Mathematics.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.