1
$\begingroup$

Two numbers $n, m$ are coprime, or relatively prime, iff $\operatorname{ggT}(n,m) = 1$ iff $1 = kn + lm$ for some $k, l \in \mathbb Z$ iff $1 \equiv kn \pmod{m}$ for some $k \in \mathbb Z$ (i.e. $n$ is invertible mod $m$).

For example it is easy to see that $1 \equiv n \pmod{m}$ then implies that $n$ and $m$ are coprime, but not the converse for example for $n = 3$ and $m = 5$. This is obvious from the third criterion. Now generalising, if $p \equiv n \pmod{m}$ for some prime $p$ which does not divide $n$ or $m$, then $n$ and $m$ are coprime as $p = kn + lm$ would imply that every common divisor would also divide $p$, hence must be $1$ or $p$, the last case excluded [or maybe with congruence arithmetic if $p$ does not divide $m$, then by the above $1 \equiv pk \pmod{m}$ for some $k$, hence $1 \equiv pk \equiv nk \pmod{m}$, which show they are coprime; do you know any congruence arithmetic proof in the case $n$ does not divide $p$?].

So do you know any useful criteria to see if two number are coprime? I am not that much into number theory, maybe the above criteria do not appear very useful to you, but I just wanted to give some examples.

$\endgroup$
  • 3
    $\begingroup$ Surely Euclid's algorithm is the best way to determine whether two numbers are relatively prime. $\endgroup$ – Théophile Dec 6 '15 at 21:35
  • 3
    $\begingroup$ More generally, if $n\equiv q \mod m$, where $q$ is coprime to $m$, then $n$ is also coprime to $m$. So for example, $5 \equiv 2 \mod 3$, and $3 \equiv 1 \mod 2$. The latter shows $3$ is coprime to $2$, which in turn shows that $5$ is coprime to $3$. But really, this is just the Euclidean algorithm written as mods. $\endgroup$ – Paul Sinclair Dec 6 '15 at 22:58
1
$\begingroup$

As noted in the comments, by far the most useful algorithm (or criterion) to determine whether two integers $m,n\in\Bbb{Z}$ are coprime is the Euclidean algorithm. This allows one to compute the greatest common divisor of $m$ and $n$ very effectively.

$\endgroup$

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.