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.

  • 2
    $\begingroup$ A prime is coprime to every no. except its multiples. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ Sorry if i am wrong but haven't you changed your profile name. $\endgroup$ – Shobhit Sep 27 '13 at 13:58
  • $\begingroup$ Verdad, mi amigo Pedro. Porque? (Lo siento, pero no tengo <a proper keyboard for accenting>)! Me gusto tu nombre! $\endgroup$ – amWhy Sep 27 '13 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.