How do I find the inverse of $e \bmod (p-1)(q-1)$?

Question

I'm trying to find this inverse modulo to set up a solution for an RSA cipher. I haven't the slightest how to go about this. When I looked up the formula for such a question, it states: $$ d \equiv e^{-1} \bmod (p-1)(q-1) $$ where $e = 71, p = 13, q = 19$ which, when I run to completion gives me $\frac 1{71}$ which is incorrect apparently. I do know that $\gcd(216,71) = 1$

Answer 1

We're looking for an integer $d$ with the property that $d \equiv e^{-1} \bmod (p-1)(q-1)$, i.e. that $de \equiv 1 \bmod (p-1)(q-1)$. In this case $p=13,q=19$, (so $(p-1)(q-1)=216$) and $e=71$. So we want an integer $d$ with the property that $71d+216k = 1$ has some integer solution $k$.

Let's try to solve $71d+216k = 1$ for integers $k$ and $d$. As you've pointed out $\gcd(216,71)=1$. So there is a solution. Let's employ a variant of Euclid's algorithm: $$216=3\cdot 71+3$$ $$71=23\cdot 3+2$$ $$3=1\cdot 2+1$$

We've got an equation with $1$ in. Now going backwards we can get $1$ expressed as a linear combination of $71$ and $216$: $$1 = 3-1 \cdot 2$$ $$= 3-1 \cdot (71-23 \cdot 3)$$ $$= 24 \cdot 3 - 1 \cdot 71$$ $$=24 \cdot (216-3 \cdot 71)-71$$ $$=24 \cdot 216 - 73 \cdot 71$$

So one possible solution is $d = -73$ and $k = 24$. By some elementary number theory, (which you should have seen or at least been told about if you're doing this question,) all solutions are given by $d = -73+216 \cdot t$ and $k = 24- 71\cdot t$ where $t$ ranges through integers.

So $d \equiv -73 \equiv 143 \bmod 216$ is the inverse of $e \bmod 216$