Question

Given m = 2n + 1, what integer between 0 and m is the inverse of 2 modulo m? Answer in terms of n.

Answer 1

additive inverse?

Answer 2

yeah

Answer 3

why don't we try it with \(n=5\) so \(m=2\times 5+1=11\)

Answer 4

what is the additive inverse of \(2\) in this case?

Answer 5

So the additive inverse would be 6.

Answer 6

In this case.

Answer 7

no i don't think so
\(2+6=8\)

Answer 8

wait, can you explain that a bit more?

Answer 9

yes
modulo 11, 11 is the zero
what would you add to 2 to get 11?

Answer 10

9

Answer 11

lol

Answer 12

yeah 9

Answer 13

suppose \(n=10\) so \(m=21\)
what would you add to \(2\) to get \(21\) ?

Answer 14

19

Answer 15

ok now we are ready
what would you add to \(2\) to get \(2n+1\) ?

Answer 16

2n-1

Answer 17

got it

Answer 18

It's wrong though...
I'm doing the homework problems on aops and it says that the answer is wrong...

Answer 19

can you help me ganeshie8?

Answer 20

try multiplicative inverse

Answer 21

try `n+1`

Answer 22

It's correct.
Can you explain your answer?

Answer 23

in general you need to solve below to find the multiplicative inverse of \(a\) in \(\mod n \):

\(ax \equiv 1 \mod n \)

Answer 24

Thanks!

Answer 25

for this particular problem, you have :
\(2x = 1 ( \mod 2n+1 )\)

Answer 26

so the question is :
which number you need to multiply to 2, to get 1 ?

Answer 27

n+1

Answer 28

yes thats easy to guess here,
but if the mod is big then you can use euclid algorithm in reverse to find the inverse