1. ## Modular arithmetic

Hello,

How can I compute:

$\displaystyle 17^{-1}$ mod $\displaystyle 23$ ?

Regards.

2. The two ways I know of are: (1) Extended Euclidean algorithm (2) Modular exponentiation. See here for some discussion. If you'd like an example, just ask, and I or someone else will provide one.

3. Originally Posted by Migotek84
Hello,

How can I compute:

$\displaystyle 17^{-1}$ mod $\displaystyle 23$ ?

Regards.
$\displaystyle 17=-6=(-2)\cdot 3\!\!\pmod {23}\,,\,\,2^{-1}=12\!\!\pmod {23}\Longrightarrow -2^{-1}=-12=11\!\!\pmod {23}$ , $\displaystyle 3^{-1}=8\!\!\pmod {23}\Longrightarrow 17^{-1}=(-2)^{-1}\cdot 3^{-1}=11\cdot 8=19\!\!\pmod{23}$

Tonio

4. There is a general method to find the inverse , you know , it is Euclidean Algorithm , but i promise once you have practised a lot , it would be very easy for you to solve , without Euclidian Algorithm .

$\displaystyle [17^{-1}] = [ \frac{1}{17} ] = \frac{[-1]}{[6]} = \frac{[ - 4 ] }{[24]} = [-4 ] = [19]$

5. Also, without going too deeply in the number theoretical realm, if you know the Euler totient of the modulus, you can efficiently compute :

$\displaystyle 17^{\varphi{(23)} - 1} \equiv 17^{-1} \pmod{23}$

In order to do this you use the modular exponentiation (square and multiply) algorithm, and $\displaystyle \varphi{(23)}$ is the Euler totient of 23 (which incidentally equals 22).

6. Hello, Migotek84!

Here's a very primitive method . . .

Compute: .$\displaystyle 17^{-1}\text{ (mod 23)}$

Let: .$\displaystyle x \:\equiv\:17^{-1}\text{ (mod 23)}$

Multiply by 17: .$\displaystyle 17x \:\equiv\:1\text{ (mod 23)}$

Then: .$\displaystyle 17x \:=\:23a + 1\:\text{ for some integer }a.$

$\displaystyle \text{Solve for }x\!:\;\;x \:=\:\dfrac{23a+1}{17} \:=\:a + \dfrac{6a+1}{17}$ .[1]

Since $\displaystyle x$ is an integer, $\displaystyle 6a+1$ is a multiple of 17.

. . $\displaystyle 6a+1 \:=\:17b\:\text{ for some integer }b.$

$\displaystyle \text{Solve for }a\!:\;\;a \:=\:\dfrac{17b-1}{6} \:=\:2b + \dfrac{5b-1}{6}$ .[2]

Since $\displaystyle a$ is an integer, $\displaystyle 5b-1$ is a multiple of 6.

. . $\displaystyle 5b-1 \:=\:6c\:\text{ for some integer }c.$

$\displaystyle \text{Solve for }b\!:\;\;b \:=\:\dfrac{6c+1}{5} \:=\:c + \dfrac{c+1}{5}$ .[3]

Since $\displaystyle b$ is an integer, $\displaystyle c+1$ is a multiple of 5.
. . The first time this happens is when .$\displaystyle c = 4$

Substitute into [3]: .$\displaystyle b \:=\:4 + \frac{4+1}{5} \quad\Rightarrow\quad b \:=\:5$

Substitute into [2]: .$\displaystyle a \:=\:2(5) + \frac{5(5)-1}{6} \quad\Rightarrow\quad a \:=\:14$

Substitute into [1]: .$\displaystyle x \:=\:14 + \frac{6(14)+1}{17} \quad\Rightarrow\quad x \:=\:19$

Therefore: .$\displaystyle 19\:\equiv\:17^{-1}\text{ (mod 23)}$

7. Hey Soroban,
I remember having seen this method on some Wikipedia article, when I first discovered modular arithmetic (nearly a year ago). I really liked it, if I recall correctly this is the Euclidian Algorithm backwards, right ?