0
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ A prime is coprime to every no. except its multiples. $\endgroup$
    – Shobhit
    Sep 27, 2013 at 13:54

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Sorry if i am wrong but haven't you changed your profile name. $\endgroup$
    – Shobhit
    Sep 27, 2013 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, 2013 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .