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 :(

Improve this question
$\endgroup$
22
  • 3
    $\begingroup$ 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. $\endgroup$ – Alex B. Dec 13 '10 at 2:34
  • 1
    $\begingroup$ @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 now $\endgroup$ – Arturo Magidin Dec 13 '10 at 16:42
  • 2
    $\begingroup$ @Tony K: Truth is, misuse of \mod is one of my peeves that I raise whenever I proofread/review/referee papers. $\endgroup$ – Arturo Magidin Dec 13 '10 at 16:47
  • 1
    $\begingroup$ 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. $\endgroup$ – TonyK Dec 13 '10 at 17:25
  • 2
    $\begingroup$ @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. (-: $\endgroup$ – Arturo Magidin Dec 13 '10 at 19:28
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks this makes it much more clear $\endgroup$ – Nathan Schwermann Dec 13 '10 at 3:47
6
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ thanks for the swift response but the original question was finding the inverse of 4 mod 9 not 7 mod 9 $\endgroup$ – Nathan Schwermann Dec 13 '10 at 2:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Jonas Meyer Dec 13 '10 at 2:26
  • $\begingroup$ 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. $\endgroup$ – Nathan Schwermann Dec 13 '10 at 2:29
  • $\begingroup$ @schwiz: More explicitly, 9-2=7 $\endgroup$ – J. M. isn't a mathematician Dec 13 '10 at 2:29
  • 2
    $\begingroup$ 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.) $\endgroup$ – Jonas Meyer Dec 13 '10 at 2:39
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Dec 13 '10 at 4:05
  • $\begingroup$ hah I certainly appreciate it, perhaps if my brain weren't already so stressed from studying all day. $\endgroup$ – Nathan Schwermann Dec 13 '10 at 4:09
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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