Find X in the Equation

Question

I'm not a mathematician and I have forgotten about some basics in mathematics. I have this equation:

$$x^y \pmod z = w$$

Given $y, z,$ and $w,$ how will I find $x$? How will I get the equation for $x$?

Answer 1

I assume here that $x,y,z,w$ are integers (and $y$ is a positive integer). Then your equation means: $$ x^y = rz+w$$ for some integer $r$. Now note that if $x$ has this property, then so does $x+kz$ for any integer $k$. So it suffices to search for $x \in \{0, 1, 2, ..., z-1\}$.

Example: $$x^{11} \mod 5 = 2 $$

Try $x \in \{0, 1, 2, 3, 4\}$: \begin{align} 0^{11} = 0 \: (mod 5)\\ 1^{11} = 1 \: (mod 5) \\ 2^{11} = 3 \: (mod 5) \\ \boxed{3^{11} = 2} \: (mod 5) \\ 4^{11} = 4 \: (mod 5) \end{align} So then solutions are $x=3+5k$ for all integers $k$.

---

The $\mod z$ operation is equal to the remainder when we divide by $z$. So for example

• $Rem[26/5] = 1$ if and only if $26-1$ is divisible by $5$.
• $Rem[83/9] = 2$ if and only if $83-2$ is divisible by $9$.
• $Rem[26/7] = 5$ if and only if $26 - 5$ is divisible by $7$.
• $Rem[n/z] = w$ if and only if $n-w$ is divisible by $z$.

In particular $Rem[n/z]=w$ if and only if $n-w= rz$ for some integer $r$.

If we take $n=x^y$ then we see that $Rem[x^y/z]=w$ if and only if $x^y - w = rz$ for some integer $r$.