Question

Discrete math and Mods: I need help with finding the inverse of 23 in Zmod95 using the Euclidean Algorithm.

Answer 1

\[23^{-1} \mod 95\]
So this is what you are trying to evaluate?

Answer 2

I don't know what the z means

Answer 3

I know how to do it in every possible way besides the Euclidean algorithm. Let me think about it.

Answer 4

The Z just mean real numbers. It's how my prof writes it :/

Answer 5

First of all, we need to find an \(x\) such that\[23x\equiv1(\text{mod }95).\]This implies that\[23x=1+95n,\]for some integer \(n\).

Answer 6

lol But I think we can do this euclidean way give me sec to remember

Answer 7

\[95=23\cdot4+3,\]\[23=3\cdot7+2,\]\[3=2\cdot1+1,\]\[2=1\cdot2+0.\]
\[3\cdot1-2\cdot1=1,\]\[3\cdot1-(23\cdot1-3\cdot7)\cdot1=1,\]\[3\cdot8-23\cdot1=1,\]\[(95\cdot1-23\cdot4)\cdot8-23\cdot1=1,\]\[95\cdot8-23\cdot33=1\implies23\cdot(-33)-95\cdot8=1.\]Therefore, the inverse of \(23\) mod \(95\) is \(-33\equiv62\).

Answer 8

You can check it because \(23\cdot62=1426\equiv1(\text{mod }95)\).

Answer 9

how did you get -33 to equal 62?

Answer 10

\[23x=1+95n, \]
He was looking for x here

Answer 11

\[23x-95n=1\]

Answer 12

That's because\[-33\equiv62(\text{mod }95).\]

Answer 13

He wrote in this form using euclidean algorithm \[23x-95n=1\]
\[23\cdot(-33)-95\cdot8=1.\]
This is in that form
Comparing the two x=-33 when n=8

Answer 14

ahh okay. Thanks guys :)