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.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ A prime is coprime to every no. except its multiples. $\endgroup$– ShobhitSep 27, 2013 at 13:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
