Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By HallsofIvy
  • 1 Post By SlipEternal

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

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    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



    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,455
    Thanks
    2892

    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.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    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...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    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.
    Last edited by SlipEternal; Sep 14th 2017 at 08:30 AM.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division Algorithm or Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Apr 10th 2013, 02:10 PM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 14th 2010, 07:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 5th 2010, 07:45 PM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jan 19th 2010, 12:13 PM
  5. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jan 3rd 2010, 04:20 AM

/mathhelpforum @mathhelpforum