Finding the Inverse Integer Modulo n

[PsychonautQQ]

Homework Statement

in mod 35, find the inverse of 13 and use it to solve 13x = 9
gcd(35,13) =1 so the inverse exsists:
35 = 2*13 + 9
13 = 1*9 + 4
9 = 2*4 + 1
4 = 4*1
and then to find the linear combination
1 = 9 - (2*4) = 9 - 2(13-9) = 3*9 - 2*13 = 3* (35 - 2*13) - 2*13 = 3*35 - 8*13 = 1
but mostly
3*35 - 8*13 = 1..
so -8 is the inverse of 13 in modulo 35.. using that to solve the equation
x = -72

but the back of my book says the inverse is 27, which would make x = 243... where did I go wrong? I can't find my mistake

Homework Equations

The Attempt at a Solution

 

[Mentallic]

Homework Statement

in mod 35, find the inverse of 13 and use it to solve 13x = 9
gcd(35,13) =1 so the inverse exsists:
35 = 2*13 + 9
13 = 1*9 + 4
9 = 2*4 + 1
4 = 4*1
and then to find the linear combination
1 = 9 - (2*4) = 9 - 2(13-9) = 3*9 - 2*13 = 3* (35 - 2*13) - 2*13 = 3*35 - 8*13 = 1
but mostly
3*35 - 8*13 = 1..
so -8 is the inverse of 13 in modulo 35.. using that to solve the equation
x = -72

but the back of my book says the inverse is 27, which would make x = 243... where did I go wrong? I can't find my mistake

Homework Equations

The Attempt at a Solution

The numbers modulo 35 range from 0-34, so any number out of that range needs to be moved into it. -8 is out of that range

 

[1MileCrash]

In short, you worked the problem correctly, but there is some confusion about what you are regarding as the "inverse" and "answer." You used a different set of residues, which gives you different numbers from the book, but you and the book still arrived at the same answer, because the answers are congruence classes, not single numbers (note that your inverse is congruent to their inverse, and your solution is congruent to their solution!).

-8 is certainly an inverse of 13 mod 35, and 27 is an inverse of 13 mod 35 (note that -8 and 27 are congruent) but neither is the inverse, and 27 is not more correct than -8. There are many inverses. Namely, any member of the congruence class [27] (which we could also call [-8] with equal validity - they are exactly the same) is an inverse.

The same applies to the value of x. x = 243 and x = -72 are equally valid solutions. Any member of [-72] (or [243] - again, same thing) is a solution. To say that x = 243 is "the" solution is wrong. To say that [243] is "the" solution is correct.

I would expect that your book said that [27] is the inverse, not the number 27. Both the inverse and value for x are entire congruence classes, not single numbers.

The numbers modulo 35 range from 0-34, so any number out of that range needs to be moved into it. -8 is out of that range

This is not true. There is nothing special about the set of nonnegative residues, one may use the set of least absolute residues to solve problems (as I think the OP did), and it is often advantageous. One may use any other, really. Using numbers outside of that specific range you chose is not incorrect and can never lead one to an incorrect answer.

When reporting your answers, it is nice to pick a set of residues and report your congruence classes in those terms, but that is purely a matter of notation. If one reports [-8] as the inverse (thereby using least absolute residues), they should report [-2] as the solution. If one reports [27] as the inverse (thereby using least nonnegative residues), they should report [33] as the solution. These are the same answer, though.

 

[Mentallic]

From my experience at least, when dealing with inverses in modulo arithmetic, it is expected that the solutions be given in the appropriate range. Just because any integer of the form 35n-8 for all integers n can be chosen, doesn't mean there aren't more appropriate choices of n in this particular situation.

 

[1MileCrash]

From my experience at least, when dealing with inverses in modulo arithmetic, it is expected that the solutions be given in the appropriate range. Just because any integer of the form 35n-8 for all integers n can be chosen, doesn't mean there aren't more appropriate choices of n in this particular situation.

The point being that it is not the source of any mathematical error to use a different set of residues.

I would disagree that the least nonnegative residues is the most appropriate choice though. I think most people would pick the least absolute residues simply because most people would rather multiply -8 and 13 than multiply 27 and 13. Least absolute residues is usually the way to go when talking about any type of function also (for the same reason).

It would be weird to use 13, 14, 1, 2, 38... Indeed. But using {-17, -16,... 16, 17} is actually what most people would use to solve this problem.