How to find $x$ value such that $x^5\equiv 99 \pmod{21}$ using congruences

Question

I know congruences somewhat, however this problem is troubling me a lot. Please help me.

If $17^5\equiv 5 \pmod {21}$, then at what value of x, $x^5\equiv 99 \pmod{21}$?

High regards, ZION

Answer 1

The problem is to find $x$ where $x^a \equiv b \pmod N$ for composite $N$.

The way to do this is to write the problem as a polynomial factorization problem modulo $N$. In other words, we write $x^a - b \equiv 0 \pmod{N}$.

Now for any polynomial factorization problem we first decompose $N$ into its prime factors, and solve each congruence separately: $$21 = 3 \cdot 7$$

So we have to solve these congruences: $$x^5 - 99 \equiv 0 \pmod 3$$ $$x^5 - 99 \equiv 0 \pmod 7$$

In general, we would factor each polynomial over the modulus, then we would see the roots $x$ (just like when you solve a quadratic equation by factoring it). However, your particular problem is so easy we actually don't have to factor anything. Reduce $99$ by each modulus and you'll see this. In other words, $99\equiv 0 \pmod{3}$ and $99\equiv 1 \pmod{7}$. So now we have:

$$x^5 - 0 \equiv 0 \pmod 3$$ $$x^5 - 1 \equiv 0 \pmod 7$$

How do we solve the first congruence? Well, what number to the 5th power equals 0? That's easy: Zero!

How do we solve the second congruence? Well, what number to the 5th power equals 1? That's also easy: 1.

If the constants were anything else, we might have to use complicated polynomial factoring algorithms like Berlekamp's or the Cantor–Zassenhaus algorithm, which are out of my league.

Now that we have our $x$'s for each factor of $N$, we use the Chinese Remainder Theorem to solve $x$ for these congruences: $$x \equiv 0 \pmod{3}$$ $$x \equiv 1 \pmod{7}$$

Since the solution for $x$ will apply modulo both prime factors of $N$, it will therefore apply modulo $N$, and we have our solution.

You can read about the Chinese Remainder Theorem here. And there is a nice calculator to solve it here. Just type in the last two equations (using an equals sign and no parentheses), and you'll have the answer.

Answer 2

To solve $x^5\equiv 99\pmod{21}$ is equivalent to solving the system $x^5\equiv 1\pmod{7}$, $x^5\equiv 0\pmod{3}$.

The solution to $x^5\equiv 0\pmod{3}$ is obvious: $x\equiv 0\pmod{3}$.

It is clear that $x\equiv 1\pmod{7}$ is a solution of $x^5\equiv 1\pmod{7}$. There are in fact no other solutions.

Finally, we want to solve the system of two linear congruences, $$x\equiv 1\pmod{7},\quad x\equiv 0\pmod{3}.$$ One could use the machinery of the Chinese Remainder Theorem. But that would be overkill here. We want $x$ to be congruent to $1$ modulo $7$ and to be divisible by $3$. The answer is $x\equiv 15\pmod{21}$.

Remark: I do not see any useful connection between the above solution and the fact that $17^5\equiv 5\pmod{21}$.