NTIC Applications to Congruences

Section 6.5 Applications to Congruences

Subsection 6.5.1 Factoring the modulus

The reason the fundamental theorem is so useful for congruences is that prime powers (for different primes) are automatically relatively prime to each other. So in using the Chinese Remainder Theorem (Theorem 5.3.2) we don't have a spend time looking for coprime factors; we can just factor into prime powers using the Fundamental Theorem of Arithmetic. So here is a useful repositioning of Proposition 5.4.5.

🔗

Proposition 6.5.1. Converting to and from prime powers.

Suppose that $X \equiv Y$ (mod $N$ ), and $N = \prod p_{i}^{e_{i}} .$ Then we have an equivalence between this congruence and a related system of congruences.

Certainly if $N$ divides $X - Y,$ so does every factor of $N,$ so $X \equiv Y$ (mod $p_{i}^{e_{i}}$ ) for each of the prime power factors of $N .$ (Once again, solutions to the “big” congruence are also solutions to a system of many little ones.)
Conversely, the prime powers in a factorization are all coprime to each other, so if we are given a solution pair $(X_{i}, Y_{i})$ to each of the congruences

$X_{i} \equiv Y_{i} (mod p_{i}^{e_{i}})$

then when combined they will give a solution of

$X \equiv Y (mod N) .$

🔗

That means that any question about congruences is really a question about systems of congruences modulo prime powers. We will use this fact again and again in the remainder of the text, and it is a huge reason why the CRT is so intensely powerful.

🔗

Similarly, referring to Subsection 5.5.2, what if one has one complicated congruence with coefficients and a composite modulus

N ?

A x \equiv B (mod N)

🔗

Just take

N = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}

and then solve all the congruences

A x \equiv B

(mod

p_{i}^{e_{i}}

) first. Then use the Chinese Remainder Theorem to ‘patch’ them together for a final solution. This is a little tedious, but certainly doable.

🔗

Example 6.5.2.

Let's solve the following congruence using the method in the previous paragraph:

21 x \equiv 33 (mod 180) .

Here are some steps:

Create the individual congruences
Solve them
Put them back together

🔗

Subsection 6.5.2 Moduli that are prime powers

🔗

When it comes to linear congruences, these consequences of the Chinese Remainder Theorem and Fundamental Theorem of Arithmetic suggest that we reconsider the prime power case with a more subtle tool. Assume that in solving a bunch of congruences

x \equiv a_{j} (mod n_{j})

🔗

we would like to start by solving congruences

x \equiv a_{j} (mod p^{e})

🔗

where

p^{e}

divides

n_{j} .

🔗

The general approach, then, is to first solve modulo

p,

in the hope that this could lead to a solution modulo

p^{e} .

Consider the following extended example, divided into two parts.

🔗

Example 6.5.3. Prime Power Congruences.

One reason we might want to solve such a congruence is for finding an inverse (recall Definition 5.3.4) for various purposes, so suppose we want to find the inverse of $4$ modulo $49 = 7^{2} .$ That is solving $4 x \equiv 1$ (mod $49$ ).

First, let $f (x) = 4 x - 1 .$ The only solution of $4 x \equiv 1$ (mod $7$ ) is clear; it is $x = [2] .$ How might we get solutions (mod $49$ ) from this? We delineate relevant steps.

First, any solution of $4 x \equiv 1$ (mod $7^{2}$ ) is also a solution of $4 x \equiv 1$ (mod $7$ ). So $x \equiv 2 + 7 k$ (mod $49$ ) for some $k,$ since $[2] = {2 + 7 k ∣ k \in Z} .$
Plugging $2 + 7 k$ in the original congruence yields

$4 x \equiv 4 (2 + 7 k) \equiv 4 \cdot 2 + 4 \cdot 7 k \equiv 1 (mod 49),$

or, rearranging (but keeping everything unmultiplied),

$1 - 4 \cdot 2 \equiv 4 \cdot 7 k (mod 7^{2}) .$
Now, we know that $7 ∣ 1 - 4 \cdot 2,$ because we already know that $2$ solved our original congruence:

$1 \equiv 4 \cdot 2 (mod 7).$

So we can cancel out $7$ from the entire congruence (as in Proposition 5.2.6) to get that

$\frac{1 - 4 \cdot 2}{7} \equiv 4 k (mod 7) .$

This simplifies to $- 1 \equiv 4 k$ (mod $7$ ).
By inspection $- 1 \equiv 4 k$ has the solution $k \equiv 5$ (mod $7$ ). Using this $k$ and plugging it back in to get a solution to $4 x \equiv 1$ (mod $7^{2}$ ), we get

$2 + 7 k = 2 + 7 \cdot 5 = 37 (mod 7^{2})$

as the solution.

And indeed $4 \cdot 37 = 148 \equiv 1$ (mod $49$ ).

🔗

Example 6.5.4.

Let's do it all again, more tersely, to get an inverse modulo $7^{3},$ i.e. a solution to $4 x \equiv 1$ modulo $7^{3} = 343 .$

I already know that $[37]$ is the solution to $4 x \equiv 1$ (mod $7^{2}$ ). That means that a solution to $4 x \equiv 1$ (mod $7^{3}$ ) must look like $37 + 7^{2} ℓ$ (for some integer $ℓ$ ).
Plugging this in gives me $4 (37 + 7^{2} ℓ) \equiv 1$ (mod $7^{3}$ ), which rearranges to

$4 \cdot 7^{2} ℓ \equiv 1 - 4 \cdot 37 (mod 7^{3}) .$
Since we know that $37$ solves $4 x \equiv 1$ (mod $7^{2}$ ), that means (by definition of congruence) that

$7^{2} ∣ 1 - 4 \cdot 37,$

so we can divide “all three sides” of the last congruence by $7^{2},$ which yields

$4 ℓ \equiv \frac{1 - 4 \cdot 37}{7^{2}} \equiv \frac{- 147}{7^{2}} \equiv - 3 \equiv 4 (mod 7) .$
Solving this yields $ℓ \equiv 1$ (mod $7$ ), so

$x \equiv 37 + 7^{2} \cdot 1 \equiv 86 (mod 343) .$

And a quick check shows $4 \cdot 86 = 344 \equiv 1$ (mod $343$ ) works.

🔗

You can do this as often as you like, and (properly interpreted) it will yield all solutions of your congruence modulo

p^{e},

one step at a time. We'll see a generalization of this in Section 7.2.