# Modular arithmetic

• Jun 20th 2010, 11:05 AM
Migotek84
Modular arithmetic
Hello,

How can I compute:

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

Regards.
• Jun 20th 2010, 11:09 AM
undefined
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.
• Jun 20th 2010, 01:14 PM
tonio
Quote:

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
• Jun 20th 2010, 09:43 PM
simplependulum
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]$
• Jun 28th 2010, 05:53 AM
Bacterius
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).
• Jun 29th 2010, 04:06 PM
Soroban
Hello, Migotek84!

Here's a very primitive method . . .

Quote:

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)}$

• Jun 29th 2010, 07:51 PM
Bacterius
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 ? (Worried)