1

I actually needed to calculate $(a/b)\%m$ when $m$ is not prime. Here is what I have done so far.

$(a/b)\%m = (a* \text{modinv}(b))\%m$, I can calculate mod inverse only if $m$ and $b$ are co-primes.

So, $m= p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n}$.

For each prime factor, I will separately calculate $(a/b)\%(p_i^{k_i})$ and then combine all the answers using Chinese Remainder Theorem.

The problem is I am unable to calculate $(a/b)\%(p^k)$, can I please get some help on this.

R_D
  • 7,312
Pranay
  • 11
  • 2
    Welcome to MSE! Please learn how to format math for this site (simple things like those in your question are not hard to do). See formatting . You may also find the tour useful. – almagest Jul 02 '16 at 14:30
  • You can be more direct and use Euler's theorem. Or, if you like being optimal, Carmichael's theorem. –  Jul 02 '16 at 14:33
  • 2
    There are much more computationally efficient ways, such as the Extended Euclidean Algorithm. No factorization, no CRT. – André Nicolas Jul 02 '16 at 14:39
  • @AndréNicolas Can you please elaborate ? I though Extended Euclidean Algorithm will work only if $b$ and $m$ are co-prime. – Pranay Jul 02 '16 at 14:58
  • If $b$ and $m$ are not relatively prime, then $b$ does not have an inverse modulo $m$. However, if you want to solve $bx\equiv a\pmod{m}$, you can compute the gcd $d$ of $b$ and $m$. If $d$ does not divide $a$, there is no solution. If $d$ divides $a$, use the Euclidean Algorithm so solve $(b/d)x\equiv a/d\pmod{m/d}$. There will be a unique solution modulo $m/d$, but several modulo $m$. – André Nicolas Jul 02 '16 at 15:03
  • Do you mean $\pmod x$ when you use $%x$ as we do in Python? – Soham Jul 13 '16 at 13:33

1 Answers1

1

It looks as if you are trying to solve the congruence $bx\equiv a\pmod{m}$.

If $b$ and $m$ are coprime, use the Extended Euclidean Algorithm to find a $z$ such that $bz\equiv 1\pmod{m}$. Then $az$ is a solution of $bx\equiv a\pmod{m}$, and it is unique modulo $m$.

If $b$ and $m$ are not coprime, then $b$ does not have a modular inverse modulo $m$. However, sometimes we can solve the congruence $bx\equiv a\pmod{m}$.

Let $d=\gcd(b,m)$. If $d$ does not divide $a$, then our congruence does not have a solution. So suppose that $d$ divides $a$.

Then $b/d$ and $m/d$ are relatively prime. The congruence $(b/d)y\equiv a/d\pmod{(m/d)}$ has a unique solution modulo $m/d$, which we can obtain using the Extended Euclidean Algorithm.

However, the congruence has $d$ solutions modulo $m$, and from each of these solutions we can obtain a solution of $bx\equiv a\pmod{m}$.

Informally, if $b$ and $m$ are not relatively prime, then $a/b$ need not exist modulo $m$, and when it exists it is not uniquely defined modulo $m$.

André Nicolas
  • 507,029