1

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

Kamil Jarosz
  • 4,984
Sajeeb Ahamed
  • 111
  • In general there is not only one value of $a$ which verifies this. So we can't find the actual value of $a$. – Bérénice Apr 23 '16 at 07: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$. – almagest Apr 23 '16 at 08:57

1 Answers1

1

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.

peterwhy
  • 22,256