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 .

It should be clear we expect at least two solutions once we move past the trivial case

n = 2,

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,

p ∣ x^{2} - 1 = (x - 1) (x + 1) implies x \equiv \pm 1 (mod p) .

🔗

More generally,

p^{e} ∣ (x - 1) (x + 1)

implies

p

divides

x - 1

x + 1 .

So we should just look at various

p^{e} .

🔗

p

is odd (and hence greater than two), the two possibilities

p ∣ x - 1

and

p ∣ x + 1

are mutually exclusive, so all the factors of

p

p^{e}

divide the same factor of

x^{2} - 1 .

p^{e} ∣ (x + 1)

p^{e} ∣ (x - 1)

are the only possibilities (

x \equiv [\pm 1]

) and there are two solutions.

🔗

However, if

p = 2

then simultaneously having

2 ∣ x - 1

and

2 ∣ 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} .$ In the latter case $+ 1 \equiv - 1,$ so then there is actually only one solution.
However, modulo $2^{3}$ it's possible that $2 ∣ (x + 1)$ and $2^{2} ∣ (x - 1),$ 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 ∣ (x + 1)$ and $2^{4} ∣ (x - 1) .$ However, it's not possible that $2^{2} ∣ (x + 1)$ and $2^{3} ∣ (x - 1)$ because numbers two apart can't both be divisible by four. So the only other possibility is that $2 ∣ (x + 1)$ and $2^{e - 1} ∣ (x - 1),$ 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 .$ 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,$ the number of odd primes that divide $n,$ and based on the equivalence class of $n$ modulo $8 .$

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

🔗

This is only the first of many such results.