0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

I suppose you mean $67^{+1}\mod 119$. You only have to find a Bézout's relation between $67$ and $119$: $$u\cdot 67+v\cdot 119=1.$$ The inverse is $u\bmod119$. You can get $u$ and $v$ with the extended Euclidean algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.