# (Useful) sufficient criteria to conclude that two numbers are coprime

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.

• Surely Euclid's algorithm is the best way to determine whether two numbers are relatively prime. – Théophile Dec 6 '15 at 21:35
• 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. – Paul Sinclair Dec 6 '15 at 22:58

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.