Number Theory: In Context and Interactive

Example 6.5.2.

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

Here are some steps:

• Create the individual congruences

• Solve them

• Put them back together

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.3) 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.