-2
$\begingroup$

$(3 \cdot d) \mod 8=1$. I know the answer is $d=3$ by common sense. But what is the mathematical approach to solve this problem? How do I solve this mathematically?

How do we get this value of 125^107 mod 187=5? This figure

$\endgroup$
1
  • 1
    $\begingroup$ If there are two questions, ask them separately. And, do not use images in your questions, see this. $\endgroup$ Commented Jul 24, 2021 at 18:52

2 Answers 2

1
$\begingroup$

Use Extended gcd algorithm. The time complexity is $O(\log n)$.

$\endgroup$
0
$\begingroup$

We know that $gcd(3,8)=1$ since $3$ is a prime, and therefore $3$ has one and unique inverse under multiplication modulo $8$.

As you have seen, its not hard to guess that $3$ is its own inverse, that is, $x=3$ is the solution for the equation: $$3x\equiv1 \mod 8$$

Since there is only one and unique solution, we know that $3$ is the only solution.

Its important to note that "guessing" a solution and verifying it, is a totally fine thing to do, and it is totally "mathematical".

$\endgroup$
2
  • $\begingroup$ Can you solve this? (d*7) mod 60=1 $\endgroup$
    – Team B.I
    Commented Jul 24, 2021 at 16:44
  • $\begingroup$ Yea my bad. I was confused with some other computational problem $\endgroup$
    – nir shahar
    Commented Jul 24, 2021 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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