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}\text{.}\) Then we have an equivalence between this congruence and a related system of congruences.

Certainly if \(N\) divides \(X-Y\text{,}\) so does every factor of \(N\text{,}\) so \(X\equiv Y\) (mod \(p_i^{e_i}\)) for each of the prime power factors of \(N\text{.}\) (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

\begin{equation*} X_i\equiv Y_i\text{ (mod }p_i^{e_i}) \end{equation*}

then when combined they will give a solution of

\begin{equation*} X\equiv Y\text{ (mod }N\text{)}\text{.} \end{equation*}

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\text{?}\)

\begin{equation*} Ax\equiv B\text{ (mod }N) \end{equation*}

Just take \(N=p_1^{e_1}\cdots p_k^{e_k}\) and then solve all the congruences \(Ax\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:

\begin{equation*} 21x\equiv 33 \text{ (mod }180)\text{.} \end{equation*}

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

\begin{equation*} x\equiv a_j\text{ (mod }n_j) \end{equation*}

we would like to start by solving congruences

\begin{equation*} x\equiv a_j\text{ (mod }p^e) \end{equation*}

where \(p^e\) divides \(n_j\text{.}\)

The general approach, then, is to first solve modulo \(p\text{,}\) in the hope that this could lead to a solution modulo \(p^e\text{.}\) 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\text{.}\) That is solving \(4x\equiv 1\) (mod \(49\)).

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

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

\begin{equation*} 4x\equiv 4(2+7k)\equiv 4\cdot 2+4\cdot 7k\equiv 1\text{ (mod }49\text{),} \end{equation*}

or, rearranging (but keeping everything unmultiplied),

\begin{equation*} 1-4\cdot 2\equiv 4\cdot 7k\text{ (mod }7^2)\text{.} \end{equation*}
Now, we know that \(7\mid 1-4\cdot 2\text{,}\) because we already know that \(2\) solved our original congruence:

\begin{equation*} 1\equiv 4\cdot 2\text{ (mod }7\text{).} \end{equation*}

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

\begin{equation*} \frac{1-4\cdot 2}{7}\equiv 4k\text{ (mod }7\text{)}\text{.} \end{equation*}

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

\begin{equation*} 2+7k=2+7\cdot 5=37\text{ (mod }7^2) \end{equation*}

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\text{,}\) i.e. a solution to \(4x\equiv 1\) modulo \(7^3=343\text{.}\)

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

\begin{equation*} 4\cdot 7^2 \ell \equiv 1-4\cdot 37\text{ (mod }7^3)\text{.} \end{equation*}
Since we know that \(37\) solves \(4x\equiv 1\) (mod \(7^2\)), that means (by definition of congruence) that

\begin{equation*} 7^2\mid 1-4\cdot 37\text{,} \end{equation*}

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

\begin{equation*} 4\ell\equiv \frac{1-4\cdot 37}{7^2}\equiv \frac{-147}{7^2}\equiv -3\equiv 4\text{ (mod }7)\text{.} \end{equation*}
Solving this yields \(\ell\equiv 1\) (mod \(7\)), so

\begin{equation*} x\equiv 37+7^2 \cdot 1\equiv 86\text{ (mod }343)\text{.} \end{equation*}

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\text{,}\) one step at a time. We’ll see a generalization of this in Section 7.2.

Number Theory: In Context and Interactive

Search Results: