NTIC Congruences as Solutions to Congruences

🔗

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.

xxxxxxxxxx
 
@interact
def _(n=(12,[10..110])):
    counter = 0
    pretty_print(html("Values of $x^2-1$ mod %s"%(n,)))
    pretty_print(html("<ul>"))
    for m in [0..n]:
        pretty_print(html(r"<li>$%s^2-1\equiv %s\text{ (mod }%s)$</li>"%(m,mod(m,n)^2-1,n)))
        if mod(m,n)^2-1==0:
            counter += 1
    pretty_print(html("</ul>"))
    pretty_print(html(r"There are $%s$ solutions to $x^2-1\equiv 0$ (mod $%s$)."%(counter,n)))

🔗

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{.}$

🔗

$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.

🔗

Fact 7.3.1.

Let $k$ be the number of different odd primes that divide $n\text{.}$ Consider the congruence $x^2-1\equiv 0$ (mod $n$ ). Then:

There are $2^k$ solutions if $n$ is odd.
There are $1\cdot 2^k=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.

🔗

Proof.

Use Fact 7.2.2 and the argument above.

🔗

What does this have to do with the title of this section? Let's recast the result.

🔗

Fact 7.3.2.

We can list all possible solutions to $x^2-1\equiv 0$ (mod $n$ ) based on $k\text{,}$ the number of odd primes that divide $n\text{,}$ and based on the equivalence class of $n$ modulo $8\text{.}$

There are $2^k$ solutions if $n\equiv 1\text{ (mod }2)\text{,}$ or when $n\equiv 1,3,5,7\text{ (mod }8)\text{.}$
There are $2^k$ solutions if $n\equiv 2$ (mod $4$ ), or when $n\equiv 2,6\text{ (mod }8)\text{.}$
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)\text{.}$

🔗

This is only the first of many such results.