0
$\begingroup$

When the $\gcd(a,m)=1$, we know that $ax≡1\mod(m)$ does have an inverse in $m$. Normally $a$ and $m$ are given and $x$ must be found. How can I find $a$ and $m$ when only $x $ is given so that $ax≡1(\mod(m))$?

For example when I choose $x=1337$ one solution would be $36290x=1(\mod (48519729))$.

$\endgroup$
2
  • 1
    $\begingroup$ Take any $a$ you like, compute $ax-1$, and let $m$ be any divisor of that. $\endgroup$
    – lulu
    May 10, 2018 at 11:28
  • $\begingroup$ Take $a=1$ and $m=x-1$. $\endgroup$ May 10, 2018 at 11:28

2 Answers 2

0
$\begingroup$

Take any $a\neq 0$ you like, and let $m$ be any divisor of $ax-1$.

For example, with $x=1337$, take $a=731$, note that $$731\times 1337-1=977346 = 2\times 3^5\times 2011$$ and we might take $m=2011$ or we could take $m= 977346$ and so on.

$\endgroup$
2
  • $\begingroup$ Will there always be an $m≠1$ ? $\endgroup$
    – 766F6964
    May 10, 2018 at 12:45
  • $\begingroup$ Of course, since $ax-1$ is not always $1$. $\endgroup$
    – lulu
    May 10, 2018 at 13:18
0
$\begingroup$

If $x$ is given, let$ a=1 $and$ m=x-1$ is also solution to this question. We can find many values of $m$ and$ a$

$\endgroup$

You must log in to answer this question.

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