Results 1 to 3 of 3

Math Help - Euclidean Algorithm Proof

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    36

    Euclidean Algorithm Proof

    Hello, I'm really confused about how to show the following proof.

    * Let a,b,n∈Z(all real integers) .Prove that if n>0,then gcd(an,bn)= n·gcd(a,b).

    I'm confused on how to start this proof, and would greatly appreciate any help/tips.

    Thanks,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    Since n divides an and bn, you know that n divides gcd(an,bn). So gcd(an,bn)=nk for some k. Clearly k must divide a and b, and the largest k that does is gcd(a,b).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,720
    Thanks
    1473
    If m= gcd(a,b) then b= pm and a= qm for some integers p and q. Then an= qmn and bn= pmn so that nm is a divisor of both an and bn. Suppose there were a larger common divisor. That is, suppose there exist integer u such that u> n and an= ux, bn= uy for integers x and y. Can you show that u is a common divisor of a and b as well?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  2. Euclidean algorithm proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 28th 2009, 07:03 PM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM
  4. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 05:46 AM
  5. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 7th 2006, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum