Congruence in Number Theory

State the relation and its domain

For integers $a,b$ and a positive modulus $m$,

Congruence is reflexive, symmetric and transitive. For transitivity, if $a-b=km$ and $b-c=\ell m$, then $a-c=(k+\ell)m$, so $a\equiv c\pmod m$.

These properties explain why each residue class is a coherent group of equivalent representatives. They do not turn congruence into ordinary equality. The modulus remains part of the statement.

Find a modular inverse when it exists

For $m\ge2$, an inverse of $a$ modulo $m$ is an integer $u$ satisfying $au\equiv1\pmod m$. It exists exactly when $\gcd(a,m)=1$.

For $a=7$ and $m=26$, Euclid’s algorithm gives

Back-substitution yields $1=3\times26-11\times7$. Thus $-11$ is an inverse of 7 modulo 26; its least non-negative representative is 15. Check: $7\times15=105=4\times26+1$.

To solve $7x\equiv5\pmod{26}$, multiply by that inverse:

Every integer $23+26k$ is a solution, and no other residue class is. The check $7\times23=161=6\times26+5$ confirms the representative.

Explain the greatest-common-factor condition

For $m\ge2$, let $d=\gcd(a,m)$. The congruence

has an integer solution exactly when $d\mid b$. Necessity follows from $ax-b=km$: both $ax$ and $km$ are divisible by $d$, so $b$ must be too.

When $d\mid b$, divide the corresponding integer equation by $d$. This gives

When $m/d\ge2$, the reduced coefficient and modulus are coprime, so an inverse solves the reduced congruence. If its solution is $x\equiv x_0\pmod{m/d}$, it represents $d$ distinct classes modulo the original $m$.

Handle the remaining case directly: if $d=m$, then $m\mid a$. Every integer solves the original congruence when $m\mid b$, and none does otherwise. For example, $14x\equiv0\pmod{14}$ permits all fourteen residue classes; $14x\equiv1\pmod{14}$ permits none. There is no need to perform an inverse calculation modulo 1. This is the structure of linear congruence solutions.

Solve a congruence with several classes

Consider $6x\equiv8\pmod{14}$. The GCF is 2, and 2 divides 8. Divide all three entries, including the modulus:

The inverse of 3 modulo 7 is 5, so $x\equiv20\equiv6\pmod7$. In the range $0\le x<14$, this gives two representatives, 6 and 13:

Their products with 6 are 36 and 78; both leave remainder 8 modulo 14. By contrast, $6x\equiv5\pmod{14}$ has no solution because every value of $6x-14k$ is even while 5 is odd.

For a simpler cancellation warning, $2x\equiv2\pmod6$ reduces to $x\equiv1\pmod3$, not $x\equiv1\pmod6$. The original residue classes are 1 and 4. Changing the modulus is what preserves the full solution set.

Combine two coprime remainder conditions

Solve

The first condition gives $x=2+3k$. Substitute into the second:

Multiplying by the inverse 2 of 3 modulo 5 gives $k\equiv2\pmod5$. Write $k=2+5t$ and substitute back:

Thus $x\equiv8\pmod{15}$. The solution is unique modulo the product 15 because 3 and 5 are coprime. This is a two-modulus instance of the Chinese remainder theorem, not a claim that every pair of conditions is compatible.

Check compatibility for non-coprime moduli

The conditions $x\equiv1\pmod4$ and $x\equiv3\pmod6$ are compatible. Their first shared non-negative value is 9, and all solutions have the form $9+12k$. The combined repeat interval is the LCM 12.

The conditions $x\equiv1\pmod4$ and $x\equiv2\pmod6$ are incompatible: the first demands an odd integer and the second an even integer. In general, $x\equiv a\pmod m$ and $x\equiv b\pmod n$ are compatible exactly when $a-b$ is divisible by $\gcd(m,n)$. When compatible, the solution class is unique modulo $\operatorname{lcm}(m,n)$.

For the examples, the common divisor 2 tests whether the remainders have the same parity. A numerical answer should always be substituted into every original condition, not just the last transformed equation.

Related topics

Use Greatest Common Factor for the Euclidean and Bézout calculations. Rational and Irrational Numbers connects divisibility and prime exponents to exact number classification.