Skip to main content
Logo image

Section 7.3 Congruences as Solutions to Congruences

We need to start applying these ideas more. In Section 7.1 we explored the number of solutions to \(x^2-1\equiv 0\) (mod \(n\)) for arbitrary \(n\text{.}\) It should be clear we expect at least two solutions once we move past the trivial case \(n=2\text{,}\) but why are there sometimes more?
Could we ever get a comprehensible answer to that question? Online, try the following interact to see if you find any patterns.
Since \(x^2-1\) is a polynomial, our knowledge of Fact 7.2.2 suggests we should try to answer this by looking at different prime power moduli first, then multiply the answers.
The key idea we will use is this. For a prime \(p\text{,}\)
\begin{equation*} p\mid x^2-1=(x-1)(x+1)\text{ implies }x\equiv \pm 1\text{ (mod }p\text{)}\text{.} \end{equation*}
More generally, \(p^e\mid (x-1)(x+1)\) implies \(p\) divides \(x-1\) or \(x+1\text{.}\) So we should just look at various \(p^e\text{.}\)
If \(p\) is odd (and hence greater than two), the two possibilities \(p\mid x-1\) and \(p\mid x+1\) are mutually exclusive, so all the factors of \(p\) in \(p^e\) divide the same factor of \(x^2-1\text{.}\) So \(p^e\mid (x+1)\) or \(p^e \mid(x-1)\) are the only possibilities (\(x\equiv [\pm 1]\)) and there are two solutions.
However, if \(p=2\) then simultaneously having \(2\mid x-1\) and \(2\mid x+1\) is definitely possible, so there could be more than two solutions. We examine three cases.
  • We know that \(\pm 1\) are still the only solutions modulo \(2^2\) and \(2^1\text{.}\) In the latter case \(+1\equiv -1\text{,}\) so then there is actually only one solution.
  • However, modulo \(2^3\) it’s possible that \(2\mid (x+1)\) and \(2^2\mid (x-1)\text{,}\) or vice versa, so that \(2^2\pm 1=3,5\) are also solutions to the congruence.
  • When the modulus is a higher power of \(2\) this sort of thing can happen, too. For instance, when \(e=5\) one could have \(2\mid (x+1)\) and \(2^4\mid (x-1)\text{.}\) However, it’s not possible that \(2^2\mid (x+1)\) and \(2^3\mid (x-1)\) because numbers two apart can’t both be divisible by four. So the only other possibility is that \(2\mid (x+1)\) and \(2^{e-1}\mid (x-1)\text{,}\) or vice versa, which is a total of four solutions. (See Exercise 7.7.15 to confirm these do all give solutions.)
That means we get a very intriguing answer.


What does this have to do with the title of this section? Let’s recast the result.
This is only the first of many such results.