Gcd/Prime Problem

geurrp the yard · #1 $Old$ October 18th, 2009, 03:10 PM

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)?

aman_cc · #2 $Old$ October 19th, 2009, 01:31 AM

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.

geurrp the yard · #3 $Old$ October 19th, 2009, 09:44 AM

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.

aman_cc · #4 $Old$ October 19th, 2009, 09:52 AM

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.

geurrp the yard · #5 $Old$ October 19th, 2009, 10:19 AM

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.

Bingk · #6 $Old$ October 19th, 2009, 09:13 PM

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?

aman_cc · #7 $Old$ October 19th, 2009, 09:21 PM

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

Bingk · #8 $Old$ October 20th, 2009, 07:01 AM

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.