Relatively Prime Numbers

Two numbers are said to be relatively prime if they have no prime factors in common and their only common factor is \(1\)

• If \(GCD(a,b) = 1\) then \(a\) and \(b\) relatively prime numbers.

Mathematica GCD

GCD[4, 13]
GCD[15,21]

Examples

• \(4\) and \(13\) are relatively prime

  \[\displaylines{ \begin{array}{|l|l|l|} \hline Numbers & 4 & 13\\ \hline Divisors & 1,2,4 & 1,13\\ \hline \end{array} \\ \begin{array}{|l|l|} \hline \text{Common Divisors} & 1\\ \hline \text{Greatest Common Divisor} & 1\\ \hline \end{array} }\]

• 15 and 21 are not relatively prime

  \[\displaylines{ \begin{array}{|l|l|l|} \hline Numbers & 15 & 21\\ \hline Divisors & 1,3,5,15 & 1,3,7,21\\ \hline \end{array} \\ \begin{array}{|l|l|} \hline \text{Common Divisors} & 1, 3\\ \hline \text{Greatest Common Divisor} & 3\\ \hline \end{array} }\]

Euclidian Algorithm and Relatively Prime

• We can use Euclidian Algorithm to see if the GCD is not \(1\). For example we can get \(GCD(12, 33)\)

  \[\displaylines{ \begin{array}{|c|c|c|c|} \hline \text{Quotient} & a & b & Remainder\\ \hline 2 & 33 & 12 & 9\\ \hline 1 & 12 & 9 & 3\\ \hline 3 & 9 & 3 & 0\\ \hline \unicode{x2718} & \color{green}3 & 0 & 0\\ \hline \end{array} }\]