Basically the style of the question is like this:
Find the inverse of $24$, modulo $35$.
The answer I get is $-16$ whereas wolframalpha gets 19. I know that $35 - 16 = 19$.
The question isn't necessarily how I find the inverse- but rather (since my exam is tomorrow)- how do I know when to convert a negative inverse into a positive one? And do I always use the rule of adding the negative to the larger number to get the desired inverse?
I ask mainly because I thought I've been getting the wrong inverses but its just that my book's answer key converts the negative to a positive inverse. However I don't recall my professor ever mentioning anything of this so I'm not sure what answer I should put on my exam tomorrow- and I don't know if context matters (is it okay to put down the inverse even if its negative sometimes).
TLDR; If the extended Euclidean Algorithm gives a negative inverse: How do I know what answer my instructor or someone else is looking for? Thanks.
$\endgroup$ 33 Answers
$\begingroup$One should get out of thinking of the values as distinct individual numbers but as classes of equivalence. -19 and 16 and 51 and 86 are all equivalent values under modulo 35 and should be thought of as being the same thing. Sometimes values such as -1 are useful. But usually positives are preferred.
$\endgroup$ $\begingroup$If you search for a number that is the multiplicative inverse of $24 \mod 35$, the inverse $x$ is defined $$ 24 \cdot x \mod 35 = 1 $$ since $24 \cdot 19 = 456$ and $456 \mod 35 = 1$, wolfram was right.
$\endgroup$ $\begingroup$Most of your question has already been adequately answered, but I wanted to address this part:
And do I always use the rule of adding the negative to the larger number to get the desired inverse?
No. In most cases this will be correct. (Nearly all, unless the exam writer tries to trip you up.) But it's getting the right answer for not quite the right reasons.
The rule you can follow always is: To convert a negative answer, or an overly large positive answer, add or subtract the modulo repeatedly to bring your answer into a range you're happy with.
Example exercise where "the larger number" rule will give an incorrect answer:
Find the inverse of 200 modulo 31.
See, the trick is, this is actually equivalent to asking "Find the inverse of 14 modulo 31." The equivalence class for 14 here is $\{...14, 14+31, 14+(2\times31), 14+(3\times31)...\}$.
Is this making sense?
So, you apply the Euclidean algorithm to my example problem, find $-11$ as your answer, and add the modulo, i.e., 31, to get the answer 20.
$\endgroup$
