One of the most important things we can do is study congruences with prime (power) modulus, because we can combine their solutions to get solutions for any congruences with the help of this important corollary to the CRT, which we have alluded to before.

For instance, if \(f(x)\equiv 0\) has 2 solutions modulo 3, 1 solution modulo 5, and 3 solutions modulo 7, it would have \(2\cdot 1\cdot 3=6\) solutions modulo 105.

Proof:

• Take a set \(a_1,a_2,\cdots a_k\) of solutions of \[f(x)\equiv 0\text{ mod }(n_i)\] for all \(i\).
• So we have \(k\) numbers \(a_i\) modulo \(n_i\), which means that we can use the Chinese Remainder Theorem to get one number \(a\) such that \(a\equiv a_i\) mod \((n_i)\) for all \(i\).
• Since modular arithmetic is well-defined, and since polynomials are exclusively composed of addition and multiplication, \(f(a)\) must be equivalent (modulo \(\left(\prod_{i=1}^k n_i\right)\)) to the one number which the CRT gives from the system \(x\equiv 0\) mod \((n_i)\). This is, of course, zero.
• So the Chinese Remainder Theorem gives exactly one solution to \[f(x)\equiv 0\text{ mod }\left(\prod_{i=1}^k n_i\right)\; .\] Clearly all such solutions must be different modulo \(\left(\prod_{i=1}^k n_i\right)\).
• Simply multiply how many there are for each \(n_i\) to get the total number of combinations of solutions. If there are \(N_i\) solutions modulo \(n_i\), we would get \(\prod_{i=1}^k N_i\).
• There aren't any additional answers, because any answer to the 'big' congruence automatically also satisfies the 'little' ones; if \(\prod_{i=1}^k n_i\mid f(a)\), then certainly \(n_i\mid f(a)\) as well.

(To summarize: if you want to get the total number of solutions of a congruence, just write the modulus as a product of prime powers \(n=\prod_{i=1}^k p_i^{e_i}\), find out how many solutions the congruence has with each prime power modulus, then multiply those numbers for the total number of solutions.)

We have already discussed prime power congruences in the previous chapter. Recall that we took the (obvious) solution of \(2x\equiv 3\text{ mod }(5)\) (namely, \(x=[4]\)), and from it relatively easily got solutions mod (\(25\)) and even mod (\(125\)).

But that is similar to asking for solutions to \(2x-3\equiv 0\). So let's connect to solving general polynomial congruences.

The key was taking the already known fact \(5\mid 3-2\cdot 4\) and then cancelling out \(5\) from the entire congruence to get that \[\frac{3-2\cdot 4}{5}\equiv 2k\text{ mod (5)}\; .\] We were able to solve the resulting congruence \(-1\equiv 2k\) mod (5), which had solution \(k\equiv 2\) mod (5). Finally, we plugged that back in to get a solution to \(2x\equiv 3\) mod (\(5^2\)), which was \[4+5k=4+5\cdot 2=14\text{ mod }(5^2)\] as the solution.

In general, this was this basic form of the following.

This is a very powerful technique. What is most interesting is that this is even interpretable as Newton's method. How? Note that the result above can be rearranged as \[x_{e}=x_{e-1}-\frac{f(x_{e-1})}{f'(x_{e-1})}\] since \(p^{e-1}\mid f(x_{e-1})\) and \(f'(x_{e-1})\) has an inverse.

If you didn't notice this, don't feel bad! In the linear case, where \(f(x)=2x-3\) the derivative was just \(f'(x)=2\) and it was not at all obvious that anything more than a trick was involved. Still, it's another fascinating place where ideas from calculus can invade the world of number theory.

Next up is our question of how many solutions there are to \(x^2-1\equiv 0\) mod (\(n\)) for arbitrary \(n\).

We can answer the question about \(x^2-1\) using the fact about the CRT, since \(x^2-1\) is a polynomial.

• We know that \(p|(x-1)(x+1)\) implies \(x\equiv \pm 1\) mod (\(p\)).
• But in fact, this is also (almost) true for any prime power \(p^e\); \(p^e|(x-1)(x+1)\) implies \(p\) divides \(x-1\) or \(x+1\), and so all the factors of \(p\) need to divide this one.
• That is, \(p^e\mid (x+1)\) or \(p^e \mid(x-1)\), and the powers of \(p\) are not spread out between \(x+1\) and \(x-1\).
• The only time this isn't true is if it's possible for \(p\) to divide both \(x-1\) and \(x+1\), which is the case precisely when \(p=2\). As it turns out, we know that \(\pm 1\) are still the only solutions for \(2^1\) (where \(+1\equiv -1\)) and \(2^2\).
• 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\) are also solutions to the congruence.
• For higher powers of \(2\) this 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 this is the only other thing that can happen.

That means we get a very intriguing answer, based on the number \(k\) of odd primes that divide \(n\)!

• There are \(2^k\) solutions if \(n\) is odd.
• There are \(2^k\) solutions if \(n\) is divisible by 2 but not by 4 (if \(n\equiv 2\) mod (\(4\)))
• There are \(2^{k+1}\) solutions if \(n\) is divisible by 4 but not by 8 (if \(n\equiv 4\) mod (\(8\)) but \(n\equiv 0\) mod (\(4\)))
• There are \(2^{k+2}\) solutions if \(n\) is divisible by 8.