0
$\begingroup$

You are given two positive integers $A$ and $M$ where $\gcd(A, M) = 1$. You have to determine whether there exists at least one integer $X$ such that $AX = 1 \pmod M$.

Okay, this is actually finding the modular multiplicative inverse exists. But here $A$ can be greater than $M$. $A$ and $M$ are $\geq 1$. So is there any case that I need to consider when $A \gt M$?

$\endgroup$
0
$\begingroup$

No consideration is required. Because there exist $A_1<M$ so that

$A \equiv A_1 \mod{M}$

$A_1$ is relatively prime to M.

$(A_1,M)=(Mk+A,M)=(A,M)=1$

Therefore $A_1$ has an inverse (mod M) and So has $A$.

$\endgroup$
  • $\begingroup$ in this problem X can also be negative. Anything special for that> $\endgroup$ – rabinra singh Feb 25 '16 at 13:51
  • $\begingroup$ I can see no difference. it can be treated the same way. $\endgroup$ – Med Feb 25 '16 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.