LinkBack URL
About LinkBacksIf 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)?
Originally Posted by aman_cc
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.
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.
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:
letbe the prime factorization of
and
be the prime factorization of
with
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.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
For e.g. gcd[a^2,b] can be p^2, if b=p^2k
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.
  |
