# Find the modular arithmatic of mod p mod q.

I have an expression say

$$x = ((a \bmod p) \bmod q)$$

Now given $x, p,q$, I need to find out the actual value of $a$. How can I do it?

For an example I have:

$$p = 109,\quad q = 26,\quad a = 171$$ $$x = (171 \bmod 109) \bmod 26 = 62 \bmod 26 = 10$$

Now from given $x=10, p = 109, q = 26$ how can I find out $a = 171$?

• In general there is not only one value of $a$ which verifies this. So we can't find the actual value of $a$. Apr 23, 2016 at 7:59
• Are you assuming that $a\bmod p$ must belong to $0,1,\dots,p-1$? If so there may be no solutions. If not, then you have $a=mp+nq+x=r\gcd(p,q)+x$. Apr 23, 2016 at 8:57

For positive integral $p$ and $q$,
\begin{align*} (a\bmod p)\bmod q &= x\\ a\bmod p &= nq+x\\ a &= mp + nq + x \end{align*}
with the condition that $0\le x<q$, $0\le nq+x < p$, and $m,n\in\mathbb Z$.
Given $x,p,q$, the range of integral $n$ can be found, and there is no limit on the range of $m$.
For negative $p$ or $q$, the sign of $\bmod$, and hence its range, depends on convention.