Coprime Test

Two integers are coprime if and only if their highest common factor (HCF) is 1.
To put this another way, for any two integers A and B there is at least one integer n such that

an = A and bn = B
(where a and b are integers)

The highest such integer n for two integers is their HCF; for two coprime integers the highest (indeed only) value of n is 1.
So, a simple test for coprimeness is to see whether or not the HCF of the two candidate values is 1.
The Euclidean Algrithm is an efficient way to arrive at the HCF of two integers. It's based on the idea that the difference of two integers is divisible by their HCF. In other words:

A - B = an - bn = (a - b)n

Since a and b are integers, a - b is also an integer and hence A - B is divisible by n.
Repeatedly replacing the larger of A and B with the magnitude of their difference (we assume we're always dealing with positive integers) will eventually yield zero (when A = B) at which point the remaining non-zero number is the pair's HCF. In algebraic terms:

if A = B then an = bn or a = b

Which is the definition of the HCF.

---

This is a great way of finding the HCF but its efficiency can be improved; repeatedly subtracting B from A until B > A and then switching to subtract A from B is equivalent to taking A mod B and then switching each time, but this second method is more efficient on a machine that supports modular division as a native operation (x86 assembly language's div instruction yields quotient and remainder).
Putting this into code:

typedef unsigned int uint;

uint hcf( uint a, uint b )
{
  while ( a * b )
  {
    if ( a > b )
      a %= b;
    else
      b %= a;
  }

  return ( a > b ) ? a : b;
}

bool coprime( uint a, uint b )
{
  return hcf( a, b ) == 1;
}


Or in Python:

def hcf( n1, n2 ):
  while n1*n2:
    if n1 > n2:
      n1 %= n2
    else:
      n2 %= n1
  return max( n1, n2 )

def coprime( n1, n2 ):
  return hcf( n1, n2 ) == 1


Determining whether two numbers are coprime is important in numerous applications, including cryptography.

---

Update
Here's a recursive one-liner in Python:


hcf = lambda n1, n2: n1 if n2 == 0 else hcf( n2, n1 % n2 )


This looks might look like it relies on n1 > n2 but as a mod b = a when b > a, the function will automatically transpose the parameters if n1 < n2.