Results 1 to 4 of 4

Math Help - prove this Highest Common Factor property

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    321

    prove this Highest Common Factor property

    (m,n)=(m+kn,n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by szpengchao View Post
    (m,n)=(m+kn,n)
    Let d=gcd(m,n) and d'=gcd(m+kn,n)

    1st part
    d divides m.
    It also divides n.
    So it divides every linear combination of the two, and in particular m+kn.

    Therefore, d divides both m+kn and n.
    We can conclude that d divides d' (because d' is the highest common factor)

    2nd part
    d' divides n.
    d' also divides m+kn.
    So it divides every linear combination of the two, and in particular m+kn+(-k)n=m.

    Therefore, d' divides both m and n.
    We can conclude that d' divides d.



    ----> d=d'
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    321

    can u prove this

    p is an odd prime
    prove:

    1^k+2^k+3^k+....(p-1)^k = 0 mod p if p-1 doesnt divid k
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by szpengchao View Post
    p is an odd prime
    prove:

    1^k+2^k+3^k+....(p-1)^k = 0 mod p if p-1 doesnt divid k
    Hint: p has a primitive root r note, r,r^2,...,r^p ranges over 1,2,...,(p-1). Now use geometric series.
    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: 2
    Last Post: March 14th 2009, 03:56 AM
  5. Highest Common Factor using Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 29th 2007, 04:28 PM

Search Tags


/mathhelpforum @mathhelpforum