Results 1 to 5 of 5

Math Help - Highest Common Factor using Euclidean Algorithm

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    10

    Highest Common Factor using Euclidean Algorithm

    SOLVED, THANKS!


    Hi,

    Supposedly by remainder theorem that
    a=a' mod n
    and
    a+b = a'+b' mod n
    and possibly
    a.b = a' . b' mod n

    I need to calculate the remainder when
    4901^10 + 3^5 is divided by 7

    As I had to prove the above formulae, I am sure I have to use them however I dont have much of an idea to actually use them.



    BELOW IS SORTED

    I am having problems finding the highest common factor using the Euclidean Algorithm and then representing hcf(a,b)=x.a+y.b

    I have been able to calculate hcf(483,315) to find that the highest common factor is 21 and represented it as 21=2.483-3.315


    However I have come across a problem when trying to calculate hcf(882,112) as from the first iteration I get:
    882=112.6+210
    The remainder is bigger than the multiplier, thus preventing me from carrying on?


    Also I have had a problem calculating the representation of hcf(493,103). I have calculated the highest common factor to be 1 but when I work out the representation I get 1=2.493-7.103 which is clearly wrong.

    I can post any additional working if required.

    Thank you very much in advance for any help or tips.
    Last edited by BlueEagle; August 29th 2007 at 04:29 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, BlueEagle!

    Don't kick yourself too hard . . .



    I have come across a problem when trying to calculate HCF(882,112).

    From the first iteration I get: . 882\:=\:112\cdot6 + 210
    The remainder is bigger than the multiplier. . . . . Of course it is!
    112 goes into 882 seven times . . .

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2007
    Posts
    10
    Ha ha yeah, just figured, I deleted my previous reply to solving the previous question and was just about to delete the topic.
    How foolish of me lol!
    Thank you very much for helping out though!

    I would like to ask another question here if possible:

    Supposedly by remainder theorem that
    a=a' mod n
    and
    a+b = a'+b' mod n
    and possibly
    a.b = a' . b' mod n

    I need to calculate the remainder when
    4901^10 + 3^5 is divided by 7

    As I had to prove the above formulae, I am sure I have to use them however I dont have much of an idea to actually use them.
    Last edited by BlueEagle; August 29th 2007 at 03:11 PM. Reason: Added question
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    The last 3 digits of 4901^{10}+243 is 244.

    What is the reaminder when it is divided by 7?. That's your answer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2007
    Posts
    10
    I solved it a different way:
    a=b mod n
    a^m=b^m mod n

    Therefore
    4901 = 1 mod 7
    4901^10 = 1^10 mod 74901^10 = 1 mod 7

    3=3 mod 7
    3^5=5 mod 7

    Adding the remainder is 6!

    Thanks for the advice though!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 25th 2011, 04:38 AM
  2. Highest common factor, Polynomial division
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: January 22nd 2010, 08:58 AM
  3. Highest Common Factor help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 27th 2009, 01:37 AM
  4. Replies: 1
    Last Post: June 23rd 2009, 05:44 AM
  5. Replies: 2
    Last Post: March 14th 2009, 03:56 AM

Search Tags


/mathhelpforum @mathhelpforum