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 .