Suppose that , p prime, find .
I'm guessing that is the answer to this thing, and surely it divides both and . But I'm having trouble afterward, thanks!
You can first look at prime divisors. If is a prime number dividing both and , then divides both and (because of primality), hence divides and (again because of primality of ).
So is a power of . It is at least , as you said, so it suffices to rule out the case . However, in the prime decomposition of , the exponents are even (twice what they are for ), so that implies (you could also simply say that and is prime, so that , which means ). And the same holds with , whereas does not divide both and (it is greater than their gcd). This concludes that can't be the gcd, hence it is .