1
$\begingroup$

Find an inverse for $43$ modulo $600$ that lies between $1$ and $600$, i.e., find an integer $1 \leq t \leq 600$ such that $43 \cdot t \equiv 1 (\text{ mod } 600)$.

The solution below states $600 = 43 \cdot 15+15$ which is in fact $660$, but somehow it still arrives at the correct answer of $307$? enter image description here

$\endgroup$
1
$\begingroup$

This is a coincidence, and this is how it happened:

Because of the miscalculation, we now found the inverse of 43 modulo 660. We found that $1=43\cdot307-660\cdot20$. But coincidently, we have $660\cdot20=13200=600\cdot22$, so $1=43\cdot307-600\cdot22$. This means that we also have found the inverse of 43 modulo 600.

Edit: We can do the same trick for any divisor of 13200. Take 825 for example. We get $1=43\cdot307-825\cdot16$, so we also have found the inverse of 43 modulo 825.

$\endgroup$
0
$\begingroup$

Because $43 \cdot 307 = 13201 \implies 13201 \text{ mod } 600 = 1$

That is the same to say

$$43 \cdot 307 \equiv 1 (\text{ mod } 600)$$

For more information see: Modular-inverses and wiki modular-inverses

$\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.