-1
$\begingroup$

How is $$PQ^{-1} \mod (10^{9}+7) = 400000004 $$?

where $P= 6$, and $Q= 5$

So far I was reading on modular arithmetic online, and most of the sites were relating to a clock analogy. Unfortunately, me being very naive (w.r.t modular arithmetic), I find it very difficult to relate the clock analogy to evaluate an expression like this.

Most of the articles were saying to find a number $x$ which multiplied by the given number $a$ would be equivalent to $1$. So do I need to literally go and find that magic number $x$ by looping through all options?

$\endgroup$
  • $\begingroup$ @RobertZ Updated the question with values of P and Q $\endgroup$ – user3243499 Jul 12 '17 at 14:53
  • 2
    $\begingroup$ @Tim510 So what? I am not asking for the solution. Nor for any hints w.r.t to the problem. It's just a simple and generic doubt related to modular arithmetic concept which I am not aware of. Infact, the problem's comment section redirected me to the modular arithmetic wiki page. But I am not able to understand it. $\endgroup$ – user3243499 Jul 12 '17 at 15:01
  • 2
    $\begingroup$ @Tim510 Your comment is quite misleading. The question is certainly not "part" of said competition. Rather, it has to do with understanding the modular notation used there. It would be polite to delete and rephrase your comment. $\endgroup$ – Bill Dubuque Jul 12 '17 at 15:26
  • $\begingroup$ My apologies, comment deleted. The intent was to alert potential answerers so that they would assist in clarification and explanation of the notation used, rather than provide a walkthrough of how to calculate $PQ^{-1}$, since that is a large part of the problem. $\endgroup$ – TimD1 Jul 12 '17 at 17:47
  • $\begingroup$ @Tim510: The problem was definitely not focusing on modular multiplicative inverse. I'm sorry if you think it that way. But it is certainly not focusing on it. The question mainly checks how well you know graph theories and trees. Had it been the case that this question focuses on inverse, then after reading Bill's answer, I would say this question would have been super easy. So,I strongly disagree with your response. $\endgroup$ – user3243499 Jul 13 '17 at 10:22
1
$\begingroup$

${\rm mod}\ 10^9\!+7\!:\ \ \color{#c00}5\cdot 400000004 - \color{#c00}6\, =\, 2(10^9\!+7)\equiv 0\ $

which implies that $\ \color{#c00}{\dfrac{6}5} \equiv 400000004$

$\endgroup$
  • $\begingroup$ Thanks, Bill. Got it now. $\endgroup$ – user3243499 Jul 12 '17 at 15:17
1
$\begingroup$

To find the inverse of $a \mod M$.

What we usually do is to use Euclidean algorithm to find $x,y$ such that

$$ax+My=1$$

By taking $\mod M$,

we have $$ax \equiv1 \mod M$$

$x$ is the inverse.

Edit:

Since $$10^9+7 = 5(2 \times 10^8+1)+2 $$

$$5=2\times 2+1$$

Hence

\begin{align}1&=5 - 2 \times 2\\ &= 5-2\times(10^9+7-5(2\times 10^8+1))\\ &= 5 - 2 \times (10^9+7)+5(4\times 10^8+2) \\ &=5(4\times 10^8+3)-2 \times (10^9+7) \end{align}

Taking $\mod 10^9+7$, we have

$$1 \equiv 5 (4 \times 10^8+3) \mod 10^9+7$$

$$Q^{-1} \equiv 4 \times 10^8+3 \mod 10^9+7$$

\begin{align}PQ^{-1} &\equiv 24 \times 10^8 +18 \mod 10^9+7 \\ &\equiv 2 \times 10^9 + 4\times 10^8 +18 \mod 10^9+7 \\ &\equiv 2 ( 10^9 +7)+4 \times 10^8 + 4 \mod 10^9+7 \\ &\equiv 4 \times 10^8+4 \mod 10^9+7\end{align}

$\endgroup$
  • $\begingroup$ Thanks @Siong. Could you please extend your explanation to the example in question so that I can related precisely. Thanks. $\endgroup$ – user3243499 Jul 12 '17 at 14:48
  • $\begingroup$ what is $P$? what is $Q$? $\endgroup$ – Siong Thye Goh Jul 12 '17 at 14:50
  • $\begingroup$ Sorry, My bad. I should have put those values. P = 6, Q= 5 $\endgroup$ – user3243499 Jul 12 '17 at 14:51

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.