2
$\begingroup$

I am working through a review problem asking to find the inverse of $4\bmod 9 $. Through examples I know that I first need to verify that the gcd is equal to 1 and write it as a linear combination of 4 and 9 to find the inverse. I can do this in just one step:

gcd(4,9)
9 = 2 * 4 + 1
1 = 9 - 2 * 4

This would suggest that the inverse is 1 if I am understanding this correctly. However, the solution manual doesn't show the work but says the LC should actually be

1 = 7 * 4 - 3 * 9

making the answer to the question 7.

Can anyone explain to me what is going on here and how to properly find the inverse? Thanks!

P.S. wish I could add tags for congruency, gcd, and inverse. I can't believe their isn't an inverse tag already :(

  • 3
    You seem to have some confusion over the definition of an inverse. The inverse of $a$ in a ring is an element $b$ such that $ab=1$. So what do you have to multiply 4 by to get 1 modulo 9? Re tags: would you also like to have a tag saying 4 and one saying 9? Seriously, "inverse" is not a mathematical topic or an area of maths, it's a concept - one out of several hundred. Tags should reflect the topic of the question.2010-12-13
  • 0
    arg i wish this would just click!! tomorrows final is gonna suck :-O2010-12-13
  • 0
    @Arturo Magidin: Now I'm confused! I saw that you edited my Answer (http://math.stackexchange.com/questions/14044/trick-to-showing-for-which-primes-p-is-34-a-square/14057#14057) by changing \mod to \pmod, to kill the superfluous leading space. OK, I thought, that's harmless enough; there are worse addictions than compulsive editing. But now I see that you have edited this Question by changing mod to \mod, thus *introducing* a superfluous space where none was before. You've disimproved the layout!2010-12-13
  • 1
    @Tony K: Two things: `\mod` is an operator used in CS; `x mod y` means the (nonnegative) remainder when dividing $x$ by $y$; by contrast, `\pmod` is the name of an equivalence relation, which consists of the symbol $\equiv$ and the `(mod y)`. Second: the names of operators and functions in mathematics follows the following convention: if they are one or two symbols long, then italics are prefered; if they are three or more symbols long, then roman typeface should be used. So $x\ mod\ y$ does not follow that convention; although it is probably better to use `\mathrm{mod}` than `\mod`; I did now2010-12-13
  • 2
    @Tony K: Truth is, misuse of `\mod` is one of my peeves that I raise whenever I proofread/review/referee papers.2010-12-13
  • 0
    @Arturo Magidin: Thank you for correcting the title! (But your disimproved "4 mod 9" remains in the body.) Has anybody ever told you that you resemble Donald Knuth (http://www.plope.com/Members/chrism/subpixel)?2010-12-13
  • 0
    @Tony K: Sorry; I did not notice the one in the body. Truth is, I don't understand the spacing in LaTeX's `\mod` command. It seems like it wants to be `\pmod` without the parentheses, and it just screws up the spacing something awful no matter what one does. An addendum for the convention I mentioned above: two letter operators that abbreviate longer words (such as `wt` for "weight", `ln`, `ad` for "adjoint") are also usually typeset in roman.2010-12-13
  • 0
    The italics render horribly in the Chrome browser you can barely read them. I had to switch to firefox just to read what Arturo's comment said.2010-12-13
  • 0
    @Arturo Magidin: What is the longer word that ln abbreviates?2010-12-13
  • 0
    Also, I wanted to say that the Question looks really nice now :-) Except that there's a full stop (period) missing after 4 mod 9.2010-12-13
  • 0
    @Tony: "natural logarithm" perhaps?2010-12-13
  • 0
    @J.M.: I believe it's "logarithmus naturalis". Which is not a word.2010-12-13
  • 0
    @Tony K: As J.M. says, it abbreviates the latin term *logarithmus naturalis*. Not a single word, but still an abbreviation for a longer term.2010-12-13
  • 0
    @Tony: okay, edit that to "longer words or phrases" perhaps... :) FWIW, you have the elliptic functions *sinus amplitudinis* $\mathrm{sn}$ and ilk also rendered in Roman typeface. Then there's also the exponential integral $\mathrm{Ei}(x)$ ...2010-12-13
  • 1
    Anyway, perhaps it's time to sum this up: Arturo has a pet peeve about misuse of \mod, although he doesn't understand its spacing. I have a pet peeve about people making gratuitous edits to my posts, but that's my problem. schwiz has finals tomorrow, so schwiz doesn't care.2010-12-13
  • 0
    @J.M.: Can you give an example of a two-letter operator that *doesn't* abbreviate a "longer word or phrase"?2010-12-13
  • 0
    @Tony: actually, only three of the twelve Jacobian elliptic functions have an assigned notation that is technically an abbreviation; the other nine aren't, but are still rendered in Roman typeface. But now we are reeeaallly veering off-topic. :D2010-12-13
  • 0
    @J.M.: Yeah, but who wants to talk about finding the inverse of 4 mod 9? (Sorry, 4 \mathrm{mod} 9)2010-12-13
  • 0
    @J.M.: @Arturo Magidin: If I have understood the abbreviation situation, it seems that two-letter operators that abbreviate longer words or phrases, or that don't, are rendered in Roman typeface. Have I got that right?2010-12-13
  • 0
    @TonyK: Two letter operators are in the border; some are *traditionally* typeset in roman (line `ln`, `ad`), others often are but sometimes aren't (like `wt`, ad-hoc abbreviations). (I note that the correct LaTeX for the binary mod operator is `\bmod`).2010-12-13
  • 0
    @J.M.: @Arturo Magidin: OK, so now it's this: two-letter operators that abbreviate longer words or phrases, or that don't, are rendered in Roman typeface. Or not. *Now* have I got it right?2010-12-13
  • 2
    @TonyK: Pretty much. As always, the rule is X, except when it isn't. And as J.M. said, perhaps these off-topic comments should be moved to a CW thread instead. (-:2010-12-13

6 Answers 6

0

It is true that x = -2, but if you want to make that -2 a positive number you should do this:

  • x = -2
  • -2 ≡ 7 (mod 9)

so 7 is the inverse.

6

$-2$ is congruent to $7$ mod $9$. Your arithmetic steps are correct, but the conclusion should be that the congruence class of $-2$ is the inverse of $4$ mod $9$, and you probably want to use representatives in $\{1,2,3,4,5,6,7,8\}$ for your inverses, for simplicity, by adding appropriate multiples of $9$.

  • 0
    thanks for the swift response but the original question was finding the inverse of 4 mod 9 not 7 mod 92010-12-13
  • 1
    Your work shows that $-2$ is the inverse of $4$ mod 9. The solution manual shows that $7$ is the inverse of $4$ mod 9. The point is that these are the same thing. Your only problem was in misinterpreting what you'd shown.2010-12-13
  • 0
    ok I almost understand can you briefly explain why -2 is the inverse of 4 mod 9? I understand why given -2 is the inverse so must be 7.2010-12-13
  • 0
    @schwiz: More explicitly, 9-2=72010-12-13
  • 0
    $(-2)(4)\bmod 9=(-8)\bmod 9=1$ or 9-8=1;2010-12-13
  • 0
    I guess what I'm hung up on is in all the examples in the book the inverse is the number being multiplied to the larger number. So why is the inverse -2 instead of 1 given the work I have.2010-12-13
  • 2
    There is never a unique way to express $1$ as $ax+by$ when $x$ and $y$ are relatively prime, so the exact numbers $a$ and $b$ aren't particularly relevant for this problem. What is important is that $ax=1-by$ is congruent to $1$ mod $y$, because it differs from $1$ by $by$, which is a multiple of $y$. This says that the class of $a$ is the inverse of the class of $x$. (I don't know how to address your concern about the examples having "larger numbers" being multiplied; at first I thought the issue was uniqueness of $a$ and $b$, but I'm not sure. In any case, I hope it's clear now.)2010-12-13
  • 0
    Its becoming more clear, thanks for all of your help I'm going to go back to stackoverflow now where I feel less dumb :P Cheers!2010-12-13
4

I know you've already gotten lots of responses, but instead of trying to fit responses into the comments under an answer I thought I'd just reiterate exactly why you need to do what you're doing.

An inverse to $4 \mod 9$ is an integer $a$ such that $4a \equiv 1 \mod 9$. If we rewrite this, it means precisely that $9| (4a-1)$, or that there is another integer $b$ so that $9b = 4a-1$. What this says is that you need to find integer solutions to $4x-9y=1$. If you find that $x=a$ and $y=b$ works then $a$ is an inverse.

So what you do to solve something like this is run the Euclidean algorithm for $9$ and $4$, and then "reverse" the steps.

$9=4\cdot 2 + 1$, so it is actually over in 1 step in this case. Just subtract over to get $9-4\cdot 2 = 1$, or in the form we wrote it above $4\cdot (-2)-9\cdot (-1)=1$. So a solution is $x=-2$ and $y=-1$ and we said the $x$-value was the inverse, so the inverse is $-2\mod 9$.

Hopefully if you understand the process of why you're doing these things, then if you get confused about which one is which on the final you can always just rederive it from these steps.

  • 0
    thanks this makes it much more clear2010-12-13
2

HINT $\ $ Congruences preserve inverses, i.e. $\rm\ A\equiv a\ \Rightarrow\ A^{-1}\equiv a^{-1}\:.\ $ This follows from the fact that congruences preserve products, i.e. it's the special case $\rm\: AB \equiv 1\: $ in this congruence product rule

LEMMA $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $

This congruence product rule is at the heart of many other similar product rules, for example Leibniz's product rule for derivatives in calculus, e.g. see my post here.

  • 2
    @schwiz: Alas, unfortunately their is no universal light bulb I can supply for everyone's head. Apologies if yours exploded! Perhaps at some later point in your studies you may safely see the light. You can ignore the link with no loss to comprehension of the above.2010-12-13
  • 0
    hah I certainly appreciate it, perhaps if my brain weren't already so stressed from studying all day.2010-12-13
1

1/4 = 4/16 = 4/7 = 8/14 = 8/5 = 16/10 = 16/1 = 16 = 7.

Note that in the first step I multiplied the numerator and denominator by 4 instead of 3. That is because 3 is not co-prime with 9.

0

Using Gauss Fraction Method: 1/4 = 2/8 = 2/(-1) = -2 = 7