1.20: More Properties of Congruences

In this chapter we introduce an important idea in working with congruences. It will have useful consequences and will illustrate another reason Bezout’s Lemma is important. We introduce it with a theorem.

Theorem \(\PageIndex{1}\)

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

Example \(\PageIndex{1}\)

When \(m=9\), the relatively prime values for \(a\) are \(1,2,4,5,7,8\). Indeed, observe that

\(1 \cdot 1 \equiv 1 \pmod 9\),		\(2 \cdot 5 \equiv 1 \pmod 9\),
\(4 \cdot 7 \equiv 1 \pmod 9\),		\(8 \cdot 8 \equiv 1 \pmod 9\).

Hence \[1^* = 1, \qquad 2^* = 5, \qquad 4^*=7, \qquad 5^*=2, \qquad 7^* = 4, \qquad 8^* = 8.\nonumber \]

Observe, too, that requiring that \(a\) be relatively prime to \(m\) is important in this case: note that \(a\) could not equal 6, since \(\gcd(6,9) \neq 1\), and indeed, any multiple of 6 is congruent to \(0\), \(3\), or \(6\) modulo 9—there is no integer \(6^*\) that produces 1 (modulo 9) when \(6\) is multiplied by it.

We call \(a^\ast\) the inverse of \(a\) modulo \(m\). Note that we choose here not to denote \(a^\ast\) by \(a^{-1}\) (though we could) 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 of Theorem \(\PageIndex{1}\)

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 1.17.5 that \(c = a^\ast\), and this proves the uniqueness.

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 “guess and check.” We can even search for it systematically. 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\).

Theorem \(\PageIndex{1}\) tells us one way of knowing whether \(a\) has an inverse modulo \(m\)—we can check to see if \(a\) and \(m\) are relatively prime. But is it necessary that \(a\) and \(m\) be relative prime for \(a\) to have an inverse? The next results give us an answer.

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 1.10.3, this implies that \(\gcd(a,m)=1\) and \(\gcd(b,m)=1\), as claimed.

Corollary \(\PageIndex{1}\)

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

Now that we know exactly which integers have inverses modulo \(m\), let’s see what we can do with inverses. First, let’s use them in the next theorem to “simplify” a congruence.

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

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

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 1.17.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 \]

Note that in the proof above we “canceled” the \(c\) in the equation by multiplying by the inverse. This is very similar to what happens in earlier math courses where you solve \(2x = 6\) by multiplying both sides of the equation by \(1/2\) (the “multiplicative inverse” of 2). The difference above is that we are dealing with congruences, not equations, and when an integer has an inverse modulo \(m\), the inverse is another integer, not a fraction. (Note also that we could solve \(2x=6\) by dividing by 2; we don’t divide when dealing with congruences—instead, we multiply by inverses.)

Example \(\PageIndex{2}\): Solve Congruences

Sometimes we may solve for an unknown integer \(x\) in a congruence. For example, consider the congruence \[7x \equiv 4 \pmod{25}.\nonumber \] Can we determine which integer(s) \(x\) can be?

Since \(\gcd(7,25)=1\), Corollary \(\PageIndex{1}\) implies that 7 has an inverse modulo 25. Indeed, a little trial and error shows that \(7^* = 18\), since \(7 \cdot 18 = 126 \equiv 1 \pmod{25}\).

Now, as in the proof of Theorem \(\PageIndex{3}\), we use \(7^*\) to “cancel” the 7 in the congruence. We multiply both sides by \(7^*\), i.e., by \(18\), and obtain the following: \[\begin{aligned} 18(7x)&\equiv 18(4) \pmod{25};\\ (18\cdot 7)x &\equiv 72 \pmod{25};\\ 1x &\equiv 22 \pmod{25}. \end{aligned}\] We see that \(x\) must be congruent to 22 modulo 25—so \(x\) must belong to the set \[\{25q+22:q \in \mathbb{Z}\} = \{\dots,-28,-3,22,47,\dots\}.\nonumber \] Indeed, substituting \(25q+22\) in for \(x\) in the left-hand side of the congruence produces \[7(25q+22) = 175q + 154 = 25(7q + 6)+4,\nonumber \] and \(25(7q+6)+4\) is congruent to \(4\) modulo 25 no matter what integer value \(q\) takes on. Hence every number in \(\{25q+22:q \in \mathbb{Z}\}\) is a solution to the congruence \(7x \equiv 4 \pmod{25}\).

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

Theorem \(\PageIndex{4}\)

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

See Exercise \(\PageIndex{3}\).

Theorem \(\PageIndex{5}\)

Let \(m>0\) and let \(d=\gcd(c,m)\). Then \[ca\equiv cb\pmod m \quad \Rightarrow \quad a\equiv b\pmod{(m/d)}.\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 (m/d)}.\nonumber \] Since \(m>0\), \(d>0\), so by Theorem \(\PageIndex{4}\) we have \[\frac cd\,a\equiv\frac cd\,b\pmod{(m/d)}.\nonumber \] Now since \(\gcd(\frac cd,\frac md)=1\), by Theorem \(\PageIndex{3}\) \[a\equiv b\pmod{(m/d)}.\nonumber \]

We end this chapter by mentioning how the concept of inverses modulo \(m\) interacts with congruence modulo \(m\). To do so, we first discuss the greatest common divisors of \(m\) and numbers that are congruent modulo \(m\).

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 \[a=mt+b \quad \text{and} \quad b=m(-t)+a.\nonumber \] Let \(d=\gcd(m,a)\) and \(e=\gcd(m,b)\). Since \(e\mid m\) and \(e\mid b\), the first equation above implies that \(e\mid a\), so \(e\) is a common divisor of \(m\) and \(a\). Hence \(e\le d\). From the second equation 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}\).

Exercises

Exercise \(\PageIndex{1}\)

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

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\). What does this show about the theorems from this chapter?

Exercise \(\PageIndex{3}\)

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

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 \]

Exercise \(\PageIndex{5}\)

1. Determine the inverse of \(8\) modulo \(13\).
2. Using your answer to (a), and perhaps imitating Example \(\PageIndex{2}\), determine all integers \(x\) such that \(8x \equiv 4 \pmod{13}\). (Note: there will be infinitely many such integers; list enough of them to make the pattern clear, and justify your answer.)

Exercise \(\PageIndex{6}\)

Try to use the results from this chapter to completely describe the integer solutions to the following congruences. (Here the coefficients on \(x\) are not relatively prime to the modulus.) If a congruence has no solution in the integers, say so and explain why.

1. \(4x \equiv 6 \pmod{10}\)
2. \(30x \equiv 90 \pmod{200}\)
3. \(6x \equiv 4 \pmod{12}\).

Exercise \(\PageIndex{7}\)

Is it possible to find integers \(a,b,m\) where \(m \geq 2\) and \(0<a,b<m\) and \(a \neq b\), and there are at least three solutions to the congruence \[ax \equiv b \pmod{m}\nonumber \] in the set \(\{0,\dots,m-1\}\)? If so, demonstrate this for a specific choice of \(a\), \(b\), and \(m\). If it is not possible, explain why not.