Question: is gcd a prime number?
Answer: Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18, 84), we find the prime factorizations 18 = 2 · 32 and 84 = 22 · 3 · 7 and the "overlap" of the two expressions is 2 · 3; so gcd(18, 84) ...