0
$\begingroup$

I want to calculate (6092427983/4)%(10^9+7). If preforming modular division by formula (a/b)%m = a*(b^-1)%m i get answer 273106987, and if i solve without modular division i get answer 523106988. Why are the answers different , even all the conditions of modular division are satisfied? b^-1 means modulo inverse of b with (10^9+7), and % means 'modulo'.

$\endgroup$
9
  • $\begingroup$ What does "%" mean there? $\endgroup$ – DonAntonio Nov 24 '17 at 16:21
  • $\begingroup$ % means modulo. $\endgroup$ – Akshat Sharma Nov 24 '17 at 16:24
  • $\begingroup$ Can you please clarify how it was that you got your answer - what calculations did you perform, and what were the intermediate steps? $\endgroup$ – Mark Bennet Nov 24 '17 at 16:24
  • $\begingroup$ 6092427983/4 = 1523106995 1523106995 % (10^9+7) = 523106988 By this answer comes 523106988. By modular division. (6092427983/4)%(10^9+7) = (6092427983 * 250000002) % (10^9+7) = 273106987 modulo inverse of 4 is 250000002. $\endgroup$ – Akshat Sharma Nov 24 '17 at 16:26
  • $\begingroup$ And what did you do with the remainder? $\endgroup$ – Mark Bennet Nov 24 '17 at 16:27
0
$\begingroup$

For $a \in \mathbb Z$ then the modulo class $[a]_n = \{a+ kn|k \in \mathbb Z\}$.

It's easy to prove that $[a]_n*[b]_n = [ab]_n$. (Pf: If $a' \in [a]_n$ and $b' \in [b]_n$ then $a'= a + kn$ and $b' = b+mn$ so $a'b' = ab + n(a'm + b'k + km) \in [ab]_n$. If $j \in [ab]_n$ then $j = ab + kn$. As $a \in [a]_a; b\in [b]_n$ so $ab = j - kn$ so $j\equiv a*b; a\in [a]_n; b\in [b_n]$. So $j \in [a]_n*[b_n]$.)

But if $x \not \in \mathbb Z$ we do not have a definition of $[x]_n$.

IF we TRIED to define $[x]_n = \{x +kn|k\in \mathbb Z\}$ we would immedieately discover that $[x]_n*[y]_n \ne [xy]_n$. Because, for example, $5 \frac 14 \in [\frac 14]_5$ and $\frac 13\in [\frac 13]_5$ would mean $(5 \frac 14)*( \frac 13) = 1\frac 34 \not \in [\frac 14*\frac 13]_5 = [\frac 1{12}]_n$.

So we do NOT have a definition for $[x]_n$ if $x$ is not an integer.

So claiming $\frac 54 \mod 7$ is the same as $\frac 54 \equiv 1.25 \mod 7$ simple doesn't mean anything. It's nonsense.

So what does it mean? It means: If there is an integer $m$ so that $4*m \equiv 5 \mod 7$. (For instance $m = 3$ as $4*3 = 12 \equiv 5 \mod 7$) Then we simple write $\frac 54 \equiv m \mod 7$. This only means $[\frac 54]_7*[4]_7 = [5]_7$. It has NOTHING to do with the fraction $\frac 54 \in \mathbb Q$. NOTHING to do with it!

It's confusing. But it is simply using the abstract algebra ring theory notation that $\frac 1m$ means $m^{-1}$ the multiplicative inverse in the ring $\mathbb Z_m$ and has nothing to do with the ring $\mathbb Q$ which is a completely different and irrelevent mathematical object.

So $\frac {6092427983}4= 1523106995.75$ is complete irrelevent and has nothing to do with anything.

BUT you can use it. $[\frac {6092427983}4]= [1523106995 + \frac 34]$.

$ 1523106995 \mod 10^9+7 = 523106988$ and whatever $k \equiv \frac 34 \mod 10^9+7$ is, we will have $\frac {6092427983}4 \equiv 1523106995 + k\mod 10^9 + 7$.

What you need to do is find $[\frac 14]$. So $1 \equiv 1+ 10^9 + 7 \mod (10^9+7) \equiv 10^9 + 8 \mod (10^9 + 7)\equiv $ then $250000002*4 \equiv 1 \mod (10^9 + 7)$ so $\frac 14 \equiv 250000002$.

So $\frac {6092427983}4 \equiv 1523106995 + 3*250000002 \mod 10^9 + 7\equiv = 523106988 + 3*250000002\equiv 273106986 + 250000002 + 3*250000002 = 273106986 + 4*250000002 \equiv 273106986 + 1 = 273106987\mod 10^9 + 7$.

$\endgroup$
6
  • $\begingroup$ Thanks a lot for this!. Now i have another question, can we calculate (integral part of (6092427983/4)) % (10^9+7) with modular division. Integral part of (6092427983/4)= 1523106995 , and then taking modulo gives, 1523106995 % (10^9+7)= 523106988. Is there any other way to calculate this. $\endgroup$ – Akshat Sharma Nov 24 '17 at 18:35
  • $\begingroup$ Yes, there are lots of ways. It'd probably be easier to reduce 609.... mod whatever... before we even start. Or we could multiply 609...*250000... from the beginning , get a huge nummber and reduce after. Burt reducing first is usually the most efficient. I got to say though, that this was a bear of a tedious problem what with all those pesky terms... sheesh. $\endgroup$ – fleablood Nov 24 '17 at 19:03
  • $\begingroup$ Can you please tell me how to reduce in the beginning when we have to deal with integer part only, as simply taking modulo of numerator is probably wrong when we have to take modulo of integer part only. $\endgroup$ – Akshat Sharma Nov 24 '17 at 19:35
  • $\begingroup$ Joffans answer shows you exactly how 5o do that. I was trying to explain why a fraction answer doesn't work. Honestly, in hindsight. I think I came down a little too heavy handed. Your actual problem was rounding. You can't throw away the remainder. The 3, is not insignificant. You shouldn't worry about integral parts. Modulo arithmetic is not about approximating and viewing $\frac 4/3$ as $1+\frac 13$ is not in any way better than viewing it as $4*3^{-1} $. In fact it's probably less good. $\endgroup$ – fleablood Nov 24 '17 at 19:46
  • $\begingroup$ What i meant was that, can we reduce 6092427983 by modulo (10^9+7). In Joffan's solution , he is dividing by 4 after subtracting from (10^9+7), and then again taking modulo. Can't we take modulo in the beginning? $\endgroup$ – Akshat Sharma Nov 24 '17 at 20:01
2
$\begingroup$

You just mistyped. The correct answer is $273106987$. If you change the last digit of your number from $3$ to $4$ you get $6092427984/4 \equiv 523106989 \pmod{10^9+7}$. This is one bigger than your other answer, so somehow you missed a parens and subtracted $1$. Probably the $-1$ exponent on the $4$ was taken as a plain "minus one" ....?

$\endgroup$
3
  • $\begingroup$ If 273106987 is the correct answer, then if we calculate (6092427983/4) which is equal to 1523106995+(3/4) , and then take modulo (10^9+7), 1523106995 % (10^9+7)= 523106988. What is wrong in this. $\endgroup$ – Akshat Sharma Nov 24 '17 at 16:35
  • $\begingroup$ 273106987 is correct. If you show your steps in getting the other answer, we can tell you exactly where you went wrong. Looking at your comment above, your first quotient ends in 5. But there is a remainder of 3 in that division which you have dropped. That's your error. $\endgroup$ – B. Goddard Nov 24 '17 at 16:42
  • $\begingroup$ The 3/4 can't just disappear. $\endgroup$ – B. Goddard Nov 24 '17 at 16:43
1
$\begingroup$

One way of calculating it: The starting number is greater than the modulus, so we'll adjust down to find a number that is cleanly divisible by $4$

  6092427983  
- 1000000007  
  ----------  
  5092427976  

  5092427976  
÷          4
  ----------
  1273106994

Reduce by modulus

  1273106994
- 1000000007  
  ----------  
   273106987  

If the starting number had been smaller than the modulus, we could have added the modulus until we found a suitable number to divide.

This is only suitable for small divisors of course.


Edit to add: For further illustration, what is $3/4 \bmod 1000000007$? This time we need to add the modulus, three times in fact, to get a number divisible by $4$.

           3  
+ 3000000021  
  ----------  
  3000000024  

  3000000024  
÷          4
  ----------  
   750000006  

So $3/4 \equiv 750000006 \bmod 1000000007$

We could also combine this result with the original problem.

  6092427983  
÷          4
  ----------
  1523101995 plus 3/4

  1523101995
+  750000006  (that is, 3/4)
  ----------  
  2273102001  

  2273102001
- 2000000014  (reduce by modulus)
  ----------  
   273106987  
$\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.