Hello I am wondering if any one can help me I am trying to figure out how to
Calculate 67−1 (mod 119) and use this to calculate 43/67 (mod 119).
I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? I know I need to use the extended Euclidean GCD algorithm but don't know how
119 = 67 + 52
67 = 52 + 15
52 = (3 × 15) + 7
15 = (2 × 7) + 1
52 = 119 − 67
15 = 67 − 52 = 67 − 119 + 67 = (2 × 67) − 119
7 = 52 − (3 × 15) = 119 − 67 − (6 × 67) + (3 × 119) = (4 × 119) − (7 × 67)
1 = 15 − (2 × 7) = (2 × 67) − 119 − (8 × 119) + (14 × 67) = (16 × 67) − (9 × 119)
I cant figure out how to get passed this pont
I think you meant $67^{-1} \mod 119$. If we denote the inverse of $67 \mod 119$ by $a$, then by definition we wish to find $a$ such that $67\cdot a\equiv 1 \mod 119$, or, find an integer solution $(a,n)$ to $67a+119x=1$. We will first find the GCD of $67$ and $119$ by Euclid's algorithm. \begin{align} 119&=67\cdot 1+52\\ 67&=52\cdot 1+15\\ 52&=15\cdot 3+7\\ 15&=7\cdot 2+1\\ 7&=1\cdot 7+0 \end{align} Now we can retrace our steps to find the solution to $67a+119x=1$. We write $1=15-7\cdot 2$ (from the fourth line). By substituting $7=52-15\cdot 3$ (from the third line), we obtain $1=15-(52-15\cdot 3)\cdot 2=15\cdot 7-52\cdot 2$. Substituting again, this time $15=67-52\cdot 1$ (from the second line), we get $1=(67-52\cdot 1)\cdot 7-52\cdot 2=67\cdot 7-52\cdot 9$. Substituting the last time, $52=199-67\cdot 1$ (from the first line), we finally get $1=67\cdot 7-(119-67\cdot 1)\cdot 9=67\cdot 16-119\cdot 9$. We find the solution $(a,x)$ is $(16,-9)$, and so $a=16$, making $67^{-1}\equiv 16\mod 119$. To now get $43/67\mod 119$, we just need to multiply by $43$; we see $43/67\equiv 43\cdot 16\equiv 688\equiv 93\mod 119$.
Hope this helped!