Results 1 to 8 of 8

Math Help - Gcd/Prime Problem

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    7

    Gcd/Prime Problem

    If gcd(
    a, b) = p, a prime, what are the possible values of each

    of gcd(
    a^2, b^2), gcd(a^2, b) and gcd(a^3, b^2)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by geurrp the yard View Post
    If gcd(
    a, b) = p, a prime, what are the possible values of each

    of gcd(
    a^2, b^2), gcd(a^2, b) and gcd(a^3, b^2)?
    Hint - Start working with (an assumed) prime factorization of a,b. Given gcd(a,b)=p, what can you say about the primefactorization? Once you answer this question everything will follow.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    7
    Quote Originally Posted by aman_cc View Post
    Hint - Start working with (an assumed) prime factorization of a,b. Given gcd(a,b)=p, what can you say about the primefactorization? Once you answer this question everything will follow.

    Hi im not sure on what you mean. Ill show you my attempet but to be honest im not sure where to even start.

    So we have gcd(a,b)=p

    a=np and b=mp where n and m are elements of Integers.
    a^2=(np)^2 and b^2=(mp)^2

    So (A^2)/(N^2)=P^2 subbing this into b^2=(mp)^2

    we b^2.n^2=A^2.m^2

    A^2.m^2 -b^2.n^2=0

    Now I dont know if im even on the right track. This is for the first part of the question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by geurrp the yard View Post
    Hi im not sure on what you mean. Ill show you my attempet but to be honest im not sure where to even start.

    So we have gcd(a,b)=p

    a=np and b=mp where n and m are elements of Integers.
    a^2=(np)^2 and b^2=(mp)^2

    So (A^2)/(N^2)=P^2 subbing this into b^2=(mp)^2

    we b^2.n^2=A^2.m^2

    A^2.m^2 -b^2.n^2=0

    Now I dont know if im even on the right track. This is for the first part of the question.

    Well no, this is not what I meant. Can you write down the prime-factorization of a,b?

    Only common prime they can have is 'p'. Why?
    Power of 'p' in the prime-factorization of at-least one of them is =1. Why?

    If you understand the statements above - you will get all the answers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    7
    Quote Originally Posted by aman_cc View Post
    Well no, this is not what I meant. Can you write down the prime-factorization of a,b?

    Only common prime they can have is 'p'. Why?
    Power of 'p' in the prime-factorization of at-least one of them is =1. Why?

    If you understand the statements above - you will get all the answers.

    Ok so they have a common factor of p since p divides a and b as gcd(a,b)=p

    Im struggling to understand this prime factorization with refrence to variables.

    Like I know that prime factorization is something along the lines of 60=2*2*3*5.

    And I thought P cannot equal one as p is prime.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Here's the answers: gcd(a^n,b^m)=p^k, where k=min(n,m)

    You were along the right track for gcd(a^2,b^2)

    we have that a^2 = (np)^2, and b^2 = (mp)^2 => p^2|a^2 and p^2|b^2. Now we just have to show that p^2 is the greatest common divisor, and you can do this by contradiction. Say there is an integer c>p^2 such that c|a^2 and c|b^2 => a^2 = sc and b^2 = tc => a = sqrt(sc) and b = sqrt(tc) => sqrt(c)|a and sqrt (c)|b. Also, from our assumption that c>p^2 => sqrt(c)>p. This is a contradiction since p is our gcd, so sqrt(c) should be less than or equal to p. So there can't exist an integer greater than p^2 that divides a^2 and b^2.

    Here's how the other way (using prime factorization) works:

    let a=p_1p_2 \cdot \cdot \cdot p \cdot \cdot \cdot p_n be the prime factorization of a and b=q_1q_2 \cdot \cdot \cdot p \cdot \cdot \cdot q_n be the prime factorization of b with p_i \neq q_j for all i,j. So only p is common, and it's the greatest common divisor. So if you raise a or b to any power, then the gcd between them would be the lowest power of p, can you see how that works?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Bingk View Post
    Here's the answers: gcd(a^n,b^m)=p^k, where k=min(n,m)

    You were along the right track for gcd(a^2,b^2)

    we have that a^2 = (np)^2, and b^2 = (mp)^2 => p^2|a^2 and p^2|b^2. Now we just have to show that p^2 is the greatest common divisor, and you can do this by contradiction. Say there is an integer c>p^2 such that c|a^2 and c|b^2 => a^2 = sc and b^2 = tc => a = sqrt(sc) and b = sqrt(tc) => sqrt(c)|a and sqrt (c)|b. Also, from our assumption that c>p^2 => sqrt(c)>p. This is a contradiction since p is our gcd, so sqrt(c) should be less than or equal to p. So there can't exist an integer greater than p^2 that divides a^2 and b^2.

    Here's how the other way (using prime factorization) works:

    let a=p_1p_2 \cdot \cdot \cdot p \cdot \cdot \cdot p_n be the prime factorization of a and b=q_1q_2 \cdot \cdot \cdot p \cdot \cdot \cdot q_n be the prime factorization of b with p_i \neq q_j for all i,j. So only p is common, and it's the greatest common divisor. So if you raise a or b to any power, then the gcd between them would be the lowest power of p, can you see how that works?
    @Bingk: Thanks. But gcd(a^n,b^m)=p^k, where k=min(n,m) might just be wrong.

    For e.g. gcd[a^2,b] can be p^2, if b=p^2k
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    You are indeed correct ... and that would cause some problems ... to simplify it, basically, gcd(p,p^n) = p, so gcd(p^2,p^n) = p^2 (assuming n>1). I was (wrongly) assuming that b also has a power of 1 to it's p. But that isn't necessarily the case. So, gcd(a^2,b) could be p or p^2. As for gcd(a^3,b^2), it could be p^2 or p^3 ... So ... gcd(a^n,b^m) = p^n or p^m, and we're not sure which ... but the idea is still correct, it will be the lowest power of p in the prime factorization (but I wrongly assumed that a and b start with a power of 1, which is not always true) ... so maybe this is better
    gcd(a^n,b^m) = p^k, where k = min(rn,sm), where r is the power of p in the prime factorization of a (i.e. a = ...p^r...) and s is the power of p in the prime factorization of b. Also, in this case, at least one of the powers (r or s) should equal 1 since gcd(a,b) = p.
    Last edited by Bingk; October 20th 2009 at 06:04 AM. Reason: correction/addition
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Birthday Problem; Prime Number Problem
    Posted in the Algebra Forum
    Replies: 9
    Last Post: January 8th 2012, 11:35 AM
  2. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  3. relatively prime problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 30th 2009, 06:13 AM
  4. Prime problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 21st 2008, 12:17 PM
  5. Another relatively prime problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 18th 2006, 04:13 PM

Search Tags


/mathhelpforum @mathhelpforum