Modular arithmetic

**Migotek84** · June 20th 2010, 11:05 AM

Hello,

How can I compute:

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

Regards.

**undefined** · June 20th 2010, 11:09 AM

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.

**tonio** · June 20th 2010, 01:14 PM

Originally Posted by Migotek84

Hello,

How can I compute:

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

Regards.

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

Tonio

**simplependulum** · June 20th 2010, 09:43 PM

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 .

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

**Bacterius** · June 28th 2010, 05:53 AM

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

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

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

**Soroban** · June 29th 2010, 04:06 PM

Hello, Migotek84!

Here's a very primitive method . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

**Bacterius** · June 29th 2010, 07:51 PM

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 ?

Thread: Modular arithmetic

LinkBack

Thread Tools

Display