0

I know that $12(7)^{-(1)}=31(mod 41)$, but I have no idea why. $12(7)^{-(1)}=12/7 \approx 1.714285714$. This is an isolated part of an example of the Pohlig-Hellman algorithm that I'm trying to understand.

Matt Robbins
  • 287
  • 1
    $$7^{-1} \pmod{41} = 6 \implies 12 \times 7^{-1} \pmod{41} = 12 \times 6 \pmod{41} = 31 \pmod{41}$$ – Moo Nov 01 '17 at 03:26

1 Answers1

3

General rule: NEVER think about fractions when working modularly.

$7^{-1}$ does NOT mean anything resembling $\frac{1}{7}$. Instead, $7^{-1}$ means an integer $k$ such that $$ 7k = 1 \bmod 41. $$ Such a solution is unique (when it exists) when chosen to be $1 \leq k \leq 40$. These inverses might not exist, but since 41 is a prime, they always do (except for $0$).

In your case, note that $7 \cdot 6 = 42 =1 \bmod 41$, so $7^{-1}=6$.

Randall
  • 18,542
  • 2
  • 24
  • 47
  • Just to add on, the proper term is "modular multiplicative inverse". You also didn't say when it exists (apart from asserting that it always exists when the modulus is prime). The necessary and sufficient condition for $a$ to have an inverse modulo $b$ (or, in other words, $ax \equiv 1 \pmod b$ has a solution $x \pmod b$ is when $\mathrm {gcd}(a,b) = 1$, i.e. $a$ and $b$ are coprime. – Deepak Nov 01 '17 at 03:28
  • Well I wasn't going to give a whole course in ring theory... – Randall Nov 01 '17 at 03:36
  • Of course not, but it's important to be precise. For example, no solution exists for $82k \equiv 1 \pmod{41}$. So your assertion that a solution always exists for any value other than $0$ is untrue. Of course, $82 \equiv 0 \pmod {41}$, so in a sense $82$ is "equivalent" to zero, but that's something that may not be realised by a novice to modular math (which I believe the OP to be). I did upvote your answer because I think it's good. I just wanted to add a little more detail in comments. – Deepak Nov 01 '17 at 03:43
  • That is indeed a good point (for the OP's benefit, the point of the question/answer process). – Randall Nov 01 '17 at 03:46