1. ## 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)?

2. Originally Posted by geurrp the yard
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.

3. Originally Posted by aman_cc
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.

4. Originally Posted by geurrp 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.

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.

5. Originally Posted by aman_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.

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.

6. 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?

7. Originally Posted by Bingk
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?
@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

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.