# In (m mod n = x) how to find m when you know n and x?

So I'm doing some cryptography assignment and I'm dealing with a modular arithmetic in hexadecimal. Basically I have the values for $n$ and the remainder $x$, but I need to find the original number $m$, e.g.

$$m \mod 0x6e678181e5be3ef34ca7 = 0x3a22341b02ad1d53117b.$$

I just need a formula to calculate $m$.

Edit: ok, let's put it this way, $x = K^e \mod n$, I know the values for $x$, $e$ and $n$. Does that help?

Ok, I realized I was approaching the problem in a wrong way, basically I had the RSA public key and I should have used RSA problem to decrypt the file without having the private key. Sorry for the stupid question.

• You need some hypotesis on $m$, otherwise the solution is not unique (in fact, there are infinite solutions) – Exodd Feb 28 '15 at 11:47
• Basically, $x\equiv a\bmod m$ implies $x=a+mk$ for any integer $k$. This should generate all the solutions. – rah4927 Feb 28 '15 at 12:48

There are infinitely many solution for $m$ and you need additional information to determine its value.
• @Keivan Consider $x=1, n=p\in\mathbb P, e=p-1$. Then every single natural $K$ such that $p\not\mid K$ will satisfy your congruence. – user26486 Feb 28 '15 at 11:55