$(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?
1$\begingroup$ If there are two questions, ask them separately. And, do not use images in your questions, see this. $\endgroup$– Inuyasha YagamiJul 24, 2021 at 18:52
Use Extended gcd algorithm. The time complexity is $O(\log n)$.
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".
$\begingroup$ Can you solve this? (d*7) mod 60=1 $\endgroup$– bromanJul 24, 2021 at 16:44
$\begingroup$ Yea my bad. I was confused with some other computational problem $\endgroup$ Jul 24, 2021 at 17:19