1.18: More Properties of Congruences

Theorem \(\PageIndex{1}\)

Let \(m \ge 2\). If \(a\) and \(m\) are relatively prime, there exists a unique integer \(a^\ast\) such that \(aa^\ast\equiv1\pmod m\) and \(0 < a ^\ast < m\).

We call \(a^\ast\) the inverse of \(a\) modulo \(m\). Note that we do not denote \(a^\ast\) by \(a^{-1}\) since this might cause some confusion. Of course, if \(c \equiv a^\ast \pmod m\) then \(ac \equiv 1 \pmod m\) so \(a^\ast\) is not unique unless we specify that \(0 < a ^\ast < m\).

Proof

If \(\gcd(a,m)=1\), then by Bezout’s Lemma there exist \(s\) and \(t\) such that \[as+mt=1.\nonumber \] Hence \[as-1=m(-t),\nonumber \] that is, \(m\mid as-1\) and so \(as\equiv 1\pmod m\). Let \(a^\ast=s \bmod m\). Then \(a^\ast \equiv s \pmod m\) so \(aa^\ast\equiv1\pmod m\) and clearly \(0 < a ^\ast < m\).

To show uniqueness assume that \(ac \equiv1\pmod m\) and \(0 < c < m\). Then \(ac \equiv aa^\ast \pmod m\). So if we multiply both sides of this congruence on the left by \(c\) and use the fact that \(ca \equiv 1 \pmod m\) we obtain \(c \equiv a^\ast \pmod m\). It follows from Exercise 15.5 that \(c = a^\ast\).

Remark \(\PageIndex{1}\)

From the above proof we see that Blankinship’s Method may be used to compute the inverse of \(a\) when it exists, but for small \(m\) we may often find \(a^\ast\) by “trial and error.” For example, if \(m=15\) take \(a=2\). Then we can check each element \(0,1,2,\dotsc,14\): \[\begin{aligned} 2\cdot 0 &\not\equiv 1\pmod{15} \\ 2\cdot 1 &\not\equiv 1\pmod{15} \\ 2\cdot 2 &\not\equiv 1\pmod{15} \\ 2\cdot 3 &\not\equiv 1\pmod{15} \\ 2\cdot 4 &\not\equiv 1\pmod{15} \\ 2\cdot 5 &\not\equiv 1\pmod{15} \\ 2\cdot 6 &\not\equiv 1\pmod{15} \\ 2\cdot 7 &\not\equiv 1\pmod{15} \\ 2\cdot 8 &\equiv 1\pmod{15}\text{ since }15\mid 16-1.\end{aligned}\] So we can take \(2^\ast=8\).

Exercise \(\PageIndex{1}\)

Show that the inverse of \(2\) modulo \(7\) is not the inverse of \(2\) modulo \(15\).

Theorem \(\PageIndex{2}\)

Let \(m>0\). If \(ab\equiv 1\pmod m\) then both \(a\) and \(b\) are relatively prime to \(m\).

Proof

If \(ab\equiv 1\pmod m\), then \(m\mid ab-1\). So \(ab-1=mt\) for some \(t\). Hence, \[ab+m(-t)=1.\nonumber\] By Exercise 9.2, this implies that \(\gcd(a,m)=1\) and \(\gcd(b,m)=1\), as claimed.

Corollary \(\PageIndex{1}\)

\(a\) has an inverse modulo \(m\) if and only if \(a\) and \(m\) are relatively prime.

Theorem \(\PageIndex{3}\): Cancellation

Let \(m>0\) and assume that \(\gcd(c,m)=1\). Then \[\label{eq:1} ca\equiv cb\pmod m\Rightarrow a\equiv b\pmod m. \]

Proof

If \(\gcd(c,m)=1\), there is an integer \(c^\ast\) such that \(c^\ast c\equiv 1\pmod m\). Now since \(c^\ast\equiv c^\ast\pmod m\) and \(ca\equiv cb\pmod m\) by Theorem 15.3, \[c^\ast ca\equiv c^\ast cb\pmod m.\nonumber \] But \(c^\ast c\equiv 1\pmod m\) so \[c^\ast ca\equiv a\pmod m\nonumber \] and \[c^\ast cb\equiv b\pmod m.\nonumber \] By reflexivity and transitivity this yields \[a\equiv b\pmod m.\nonumber \]

Exercise \(\PageIndex{2}\)

Find specific positive integers \(a,b,c\) and \(m\) such that \(c \not \equiv 0 \pmod m\), \(\gcd(c,m) >0\), and \(ca\equiv cb\pmod m\), but \(a \not\equiv b\pmod m\).

Although \(\eqref{eq:1}\) above is not generally true when \(\gcd(c,m)>1\), we do have the following more general kinds of “cancellation:”

Theorem \(\PageIndex{4}\)

If \(c>0\), \(m>0\) then \[a\equiv b\pmod m\Leftrightarrow ca\equiv cb\pmod{cm}.\nonumber\]

Exercise \(\PageIndex{3}\)

Prove Theorem \(\PageIndex{4}\).

Theorem \(\PageIndex{5}\)

Let \(m>0\) and let \(d=\gcd(c,m)\). Then \[ca\equiv cb\pmod m\Rightarrow a\equiv b\pmod{\frac md}.\nonumber\]

Proof

Since \(d=\gcd(c,m)\) we can write \(c=d(\frac cd)\) and \(m=d(\frac md)\). Then \(\gcd(\frac cd,\frac md)=1\). Now rewriting \(ca\equiv cb\pmod m\) we have \[d\,\frac cd\,a\equiv d\,\frac cd\,b\pmod{d\,\frac md}.\nonumber \] Since \(m>0\), \(d>0\), so by Theorem \(\PageIndex{4}\) we have \[\frac cd\,a\equiv\frac cd\,b\pmod{\frac md}.\nonumber \] Now since \(\gcd(\frac cd,\frac md)=1\), by Theorem \(\PageIndex{3}\) \[a\equiv b\pmod{\frac md}.\nonumber \]

Theorem \(\PageIndex{6}\)

If \(m>0\) and \(a\equiv b\pmod m\) we have \[\gcd(a,m)=\gcd(b,m).\nonumber \]

Proof

Since \(a\equiv b\pmod m\) we have \(a-b=mt\) for some \(t\). So we can write \[\label{eq:2} a=mt+b\] and \[\label{eq:3} b=m(-t)+a. \] Let \(d=\gcd(m,a)\) and \(e=\gcd(m,b)\). Since \(e\mid m\) and \(e\mid b\), from \(\eqref{eq:2}\) \(e\mid a\) so \(e\) is a common divisor of \(m\) and \(a\). Hence \(e\le d\). Using \(\eqref{eq:3}\) we see similarly that \(d\le e\). So \(d=e\).

Corollary \(\PageIndex{2}\)

Let \(m>0\). Let \(a\equiv b\pmod m\). Then \(a\) has an inverse modulo \(m\) if and only if \(b\) does.

Proof

Immediate from Theorems \(\PageIndex{1}\), \(\PageIndex{2}\) and \(\PageIndex{6}\).

Exercise \(\PageIndex{4}\)

Determine whether or not each of the following is true. Give reasons in each case.

1. \(x\equiv 3\pmod 7\Rightarrow\gcd(x,7)=1\)
2. \(\gcd(68019,3)=3\)
3. \(12x\equiv 15\pmod{35}\Rightarrow 4x\equiv 5\pmod 7\)
4. \(x\equiv 6\pmod{12}\Rightarrow\gcd(x,12)=6\)
5. \(3x\equiv 3y\pmod{17}\Rightarrow x\equiv y\pmod{17}\)
6. \(5x\equiv y\pmod 6\Rightarrow 15x\equiv 3y\pmod{18}\)
7. \(12x\equiv 12y\pmod{15}\Rightarrow x\equiv y\pmod 5\)
8. \(x\equiv 73\pmod{75}\Rightarrow x\bmod 75=73\)
9. \(x\equiv 73\pmod{75}\) and \(0\le x<75\Rightarrow x=73\)
10. There is no integer \(x\) such that \[12x\equiv 7\pmod{33}.\nonumber \]