0
$\begingroup$

How can I calculate $(x*k)/i$ (mod $m$) where i and m are relatively not co-prime ?

We know that, if $\gcd(i,m)\neq1$ , then there doesn't exist a modular multiplicative inverse of $i$ mod $m$. Then how can it be solved?

Thanks in Advance :)

$\endgroup$
1
$\begingroup$

As imu96 remarked, there is no solution in the general case.

However, if $(x*k)/\gcd(i,m)$ is an integer, you could calculate it using: $$ (x*k)/i \equiv (x*k)\Big/\left(\gcd(i,m)*\frac{i}{\gcd(i,m)}\right)\pmod m \\\equiv (x*k/\gcd(i,m))*\left(\frac{i}{\gcd(i,m)}\right)^{-1} \pmod m $$

Note that $\frac{i}{gcd(i,m)}$ and $m$ are co-prime.

$\endgroup$
0
$\begingroup$

If i and m are not coprime, then i does not have a multiplicative inverse and so, there is no solution to the equation.

If you think about it, it makes sense for there to be no solution because you are essentially trying to multiply by a number that doesn't exist.

$\endgroup$

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.