# Thread: Euclidean algorithm I'm not sure if this is right ,going off lecture slides.

1. ## Euclidean algorithm I'm not sure if this is right ,going off lecture slides.

Solve the equation 65x 5 (mod 279) by using the extended Euclidean algorithm.

To find the reciprocal of 65 (mod 279) we must first ensure it exists by finding if they have 1 as their greatest common denominator.

gcd(279,65): 279= 65 ⋅ 4+ 19

from here not sure what to do
hmm any help would be appreciated thanks

2. ## Re: Euclidean algorithm I'm not sure if this is right ,going off lecture slides.

65= 5*13 and 279= 3*93= 3*3*31 so the greatest common factor (not "denominator"- there is no fraction here) is 1.

3. ## Re: Euclidean algorithm I'm not sure if this is right ,going off lecture slides.

Thanks HallsofIvy I think I was having a bit f trouble with the 5(mod 279) does that 5 just mean that we multiply it by something to get what ever it is on the LHS ie 65 then break the mod 279 down if that makes sense...

4. ## Re: Euclidean algorithm I'm not sure if this is right ,going off lecture slides.

$279 = 65\cdot 4 + 19 \Longrightarrow 19 = 279-65 \cdot 4$
$65 = 19\cdot 3 + 8 \Longrightarrow 8 = 65 - 19\cdot 3$
$19 = 8\cdot 2 + 3 \Longrightarrow 3 = 19-8\cdot 2$
$8 = 3\cdot 2 + 2 \Longrightarrow 2 = 8 - 3\cdot 2$
$3 = 2\cdot 1 + 1 \Longrightarrow 1 = 3 - 2\cdot 1$

Now, we work backwards:

$1 = 3-2\cdot 1$
$1 = 3-(8 - 3\cdot 2) \cdot 1 = 3 \cdot 3- 8$
$1 = (19-8\cdot 2)\cdot 3 - 8 = 19\cdot 3 - 8\cdot 7$
$1 = 19\cdot 3 - (65 - 19\cdot 3)\cdot 7 = 19\cdot 24 - 65\cdot 7$
$1 = (279-65\cdot 4)\cdot 24 - 65\cdot 7 = 279\cdot 24 - 65\cdot 103$

So, $65\cdot (-103) \equiv 1 \pmod{279}$

$-103 \equiv 279 - 103 = 176 \pmod{279}$

So,
$65x \equiv 5 \pmod{279}$
$176\cdot 65x \equiv 176\cdot 5 \pmod{279}$
$1x \equiv 176\cdot 5 \pmod{279}$
$176\cdot 5 = 279\cdot 3 + 43$
$x \equiv 43 \pmod{279}$

Now, we test this out:

$65\cdot 43 = 279\cdot 10 + 5$

So, it is correct.