1
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ In general there is not only one value of $a$ which verifies this. So we can't find the actual value of $a$. $\endgroup$
    – Bérénice
    Apr 23, 2016 at 7:59
  • $\begingroup$ 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$. $\endgroup$
    – almagest
    Apr 23, 2016 at 8:57

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .