# In RSA, why does Alice's $N$ need to be relatively prime to Bob's $N$?

I was asked this by my professor and I didn't understand the reasoning behind it. If Alice has a the key pair $(p_a, n_a)$ and Bob has the key pair $(p_b, n_b)$, why do $n_a$ and $n_b$ have to be relatively prime?

In RSA, the modulus is computed as $n=pq$ where $p$ and $q$ are prime. Given two moduli, if they have no primes in common, then the GCD is $1$ and they are relatively prime. If they share a prime factor, then the GCD will reveal that prime factor. Therefore, anyone who knows the two public keys can factorize the moduli and break security.
• Ahh that makes total sense. So that means p and q need to be unique to everyone? Surely there will be some people who choose similar primes between themselves. I guess there is a sort of "herd protection"? – n0pe Nov 5 '14 at 12:57