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\). It should be clear we expect at least two solutions, but why are there sometimes more? Could we ever get a solution that is comprehensible?
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:
We know that (for a prime \(p\)) \(p\mid x^2-1=(x-1)(x+1)\) implies \(x\equiv \pm 1\) (mod \(p\)).
More generally, \(p^e\mid (x-1)(x+1)\) implies \(p\) divides \(x-1\) or \(x+1\).
So we should just look at various \(p^e\).
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\) need to divide the same one. 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 \(2\mid x-1\) and \(2\mid x+1\) is definitely possible, so there could be more solutions.
We know that \(\pm 1\) are still the only solutions for \(2^2\) and \(2^1\); in the latter case \(+1\equiv -1\), so there is actually only one solution in this case.
However, for \(2^3\) it's possible that \(2\mid (x+1)\) and \(2^2\mid (x-1)\), or vice versa, so that \(2^2\pm 1=3,5\) are also solutions to the congruence.
For higher powers of \(2\) this sort of thing can happen, too. For instance, one could have \(2\mid (x+1)\) and \(2^4\mid (x-1)\). 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)\), or vice versa, which is a total of four solutions.
That means we get a very intriguing answer.
Let \(k\) be the number of odd primes that divide \(n\). Consider the congruence \(x^2-1\) (mod \(n\)). Then:
There are \(2^k\) solutions if \(n\) is odd.
There are \(1\cdot 2^k\) solutions if \(n\) is divisible by 2 but not by 4.
There are \(2\cdot 2^k=2^{k+1}\) solutions if \(n\) is divisible by 4 but not by 8.
There are \(4\cdot 2^k = 2^{k+2}\) solutions if \(n\) is divisible by 8.
What does this have to do with the title of this section? Let's recast the result.
There are \(2^k\) solutions if \(n\equiv 1\text{ (mod }2)\), or \(n\equiv 1,3,5,7\text{ (mod }8)\).
There are \(2^k\) solutions if \(n\equiv 2\) (mod \(4\)), or \(n\equiv 2,6\text{ (mod }8)\).
There are \(2\cdot 2^k=2^{k+1}\) solutions if \(n\equiv 4\) (mod \(8\)).
There are \(4\cdot 2^k = 2^{k+2}\) solutions if \(n\equiv 0\text{ (mod }8)\).
This is only the first of many such results.
