# Modular multiplicative inverse

• Oct 24th 2010, 11:01 PM
Pan
Modular multiplicative inverse
I don't quite understand this concept, or how to write it down algebraically (not sure what the triple equals thing means).

So let's say I want to find the multiplicative inverse of $3 \mod{11}$. Am I right in thinking that I am looking for a number that when multiplied by 3, and then divided by 11, I will get remainder 1. The reason I struggle writing this down is because the quotient is irrelevant.

Anyway, to work this out in my head, I would use trial and error:
$1 \times 3 \mod{11} = 3$
$2 \times 3 \mod{11} = 6$
$3 \times 3 \mod{11} = 9$
$4 \times 3 \mod{11} = 1$ because 12/11 is 1 remainder 1

So the answer is 4.

Presuming what I have done so far is right, I don't understand why Wikipedia says 15 is also an answer? 15*4 = 60, and 60/11 is 5 r5, NOT r1.
• Oct 25th 2010, 03:30 AM
tonio
Quote:

Originally Posted by Pan
I don't quite understand this concept, or how to write it down algebraically (not sure what the triple equals thing means).

So let's say I want to find the multiplicative inverse of $3 \mod{11}$. Am I right in thinking that I am looking for a number that when multiplied by 3, and then divided by 11, I will get remainder 1. The reason I struggle writing this down is because the quotient is irrelevant.

Anyway, to work this out in my head, I would use trial and error:
$1 \times 3 \mod{11} = 3$
$2 \times 3 \mod{11} = 6$
$3 \times 3 \mod{11} = 9$
$4 \times 3 \mod{11} = 1$ because 12/11 is 1 remainder 1

So the answer is 4.

Presuming what I have done so far is right, I don't understand why Wikipedia says 15 is also an answer? 15*4 = 60, and 60/11 is 5 r5, NOT r1.

You are right in your calculations but you got confused with 15: it is the inverse of 3, NOT of 4! And indeed, 15*3=45 = 11*4+1.

Of course, 15=4 modulo 11, so we usually use 4 instead of 15 when working modulo 11.

Tonio
• Oct 25th 2010, 04:05 AM
Pan
Oh thanks... I really get confused when trying to think of modular arithmetic.
• Oct 25th 2010, 06:26 AM
HallsofIvy
There are two ways of thinking about modular arithmetic (mod 11, say).
1) Think of the "numbers" as only 0 to 10.
2) Think of the "numbers" as sets of numbers which have the same remainder when divided by 10.

In the first case, only "4" is the multiplicative inverse of 3 because 3*4= 12= 11+ 1 so 3*4= 1 (mod 11). "15" would not qualify because it is not between 0 and 10.

In the second case, the multiplicative inverse of "3" (representing the set {3, 14, -8, 25, -19, ...}) is the set {4, 15, -7, 26, -18, ...}. If we think of each set as "represented" by the smallest positive number in the set, we are back to (1).