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.
[Math] Are prime numbers relatively prime to every other number but itself
elementary-number-theoryprime numbers
Best Answer
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$.