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

Printable View

- Oct 18th 2009, 02:10 PMgeurrp the yardGcd/Prime ProblemIf 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)?

- Oct 19th 2009, 12:31 AMaman_cc
- Oct 19th 2009, 08:44 AMgeurrp the yard

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. - Oct 19th 2009, 08:52 AMaman_cc

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. - Oct 19th 2009, 09:19 AMgeurrp the yard

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. - Oct 19th 2009, 08:13 PMBingk
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 $\displaystyle a=p_1p_2 \cdot \cdot \cdot p \cdot \cdot \cdot p_n$ be the prime factorization of $\displaystyle a$ and $\displaystyle b=q_1q_2 \cdot \cdot \cdot p \cdot \cdot \cdot q_n$ be the prime factorization of $\displaystyle b$ with $\displaystyle 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? - Oct 19th 2009, 08:21 PMaman_cc
- Oct 20th 2009, 06:01 AMBingk
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.