# Are prime numbers relatively prime to every other number but itself?

Given two integers, to find if they are relatively prime (or coprime) is to use the division algorithm repeatedly until you get a remainder of zero... But what if you want to find if say, 5 and 25 are relatively prime? I was running on the assumption that if one of the numbers were prime themselves, then it was automatically coprime... but unless I did something wrong, it looks like their GCD is 5 after all.

• A prime is coprime to every no. except its multiples. – Shobhit Sep 27 '13 at 13:54

You're right, $(25,5)=5$. The correct general claim is that $(a,b)=1$ if and onl if $a$ and $b$ share no prime factors whatsoever, that is, if $a=p_1^{\ell_1}\cdots p_r^{\ell_r}$ and $b=q_1^{m_1}\ldots q_e^{m_e}$ then we must have $q_i\neq p_j$ for every pair $(i,j)$. Recall that $d=(a,b)$ is the unique positive number with the following two properties:
$(\rm i)$ The number $d$ divides both $a$ and $b$, that is $d$ is a common divisor of $a$ and $b$.
$(\rm ii)$ If $f$ is another common divisor of $a$ and $b$ then $f$ divides $d$, that is $d$ is the greatest common divisor of $a$ and $b$.