Relatively Prime

Date: 10/07/1999 at 02:23:38
From: Renee Dingus
Subject: Relative prime number

I am homeschooling my 13-year-old and we have come to factoring. It 
defines a relative prime number as "if 2 numbers have a greatest 
common factor of one, after prime factorization, it is a relative 
prime number."

My daughter and I just don't understand. Would you be able to explain 
this to us in a more detailed fashion?

Date: 10/07/1999 at 05:13:11
From: Doctor Joe
Subject: Re: Relative prime number

Dear Renee,

We shall look at some definitions.

(a) Factor

Let x and y be two integers (whole numbers). We say that x is a factor 
of y if y = kx for some integer k. We may also say x divides y.

If this sounds a bit abstract, let's look at a few examples:

     Example 1: 2 is a factor of 6 since 6 = 3 x 2.
     Example 2: 3 is a factor of 18 since 18 = 6 x 3.
     Example 3: 18 is a factor of 36 since 36 = 2 x 18.

It is also good to look at some non-examples:

     Example 4: 6 is not a factor of 11 since 11 leaves a remainder of 
                5 when divided by 6.

     Example 5: 9 is a factor of 18 but not 14.

From these examples, one can see that x is a factor of y if and only 
if y leaves no remainder when divided by x.


(b) Prime Numbers

The study of prime numbers has always been at the core of mathematics, 
especially the topic of number theory.

A positive integer p (larger than 1) is called a prime number (or 
simply prime) if the only factors of p are 1 and p (itself).

Let me make it clearer:

     Example 6: 2 is a prime number since 2 = 1 x 2. We see that 
                the only integer divisors of 2 are 1 and 2.

     Example 7: 3, 5, 7, 11, 13, 17, 19, 23 are examples of primes.

     Example 8: 12 is not a prime number, as 12 = 3 x 4. So besides 1 
                and 12, the integers 3 and 4 are factors of 12.


(c) Prime Factorization

It is a renowned theorem in elementary number theory that a positive 
integer may be factored into primes in an essentially unique way. This 
is called the Fundamental Theorem of Arithmetic. What this means in a 
nutshell is:

Say we pick the number 12. Then 12 = 2 x 2 x 3. But you may say that 
12 = 2 x 3 x 2. However, if you re-order them, you still get 
2 x 2 x 3. This is what I mean by "essentially" unique.

I shall not prove this theorem, but what we discuss will depend on 
some knowledge of this. I am confident that you know how prime 
factorization of an integer is performed, so I shall not review with 
you the technicalities.


(d) Relatively prime (the main topic of the discussion)

Definition (Common Factor):

The common factor of two integers x and y is an integer d such that 
d is a factor of both x and y. In other words, d divides x and d 
divides y.

     Example 9: 2 is a common factor of 4 and 6 since 4 = 2 x 2 and 
                6 = 3 x 2.

     Example 10: 12 is a common factor of 144 and 36.
     Example 11: 1 is the only common factor of 26 and 51.

From example 11, we see that two integers may have no common factors 
other than the trivial factor 1. This is this case that motivates the 
definition that follows.

Definition (Relative primes):

Two integers are relative primes (or termed as relatively prime or as, 
in some more technical books, co-prime) if they have no common factor 
other than 1.

     Example 12: 26 and 51 are relative primes.
     Example 13: 81 and 343 are relative primes.

Remarks:

(a) Note that one cannot say that a particular number is a relative 
prime. So there is some fundamental error in the way you phrased your 
question. The word "relative" indicates that there is some form of 
comparison. It takes at two integers to get the definition going.

(b) One can also say that 12, 121, 343 are relatively prime, as the 
only common factor of 12, 121 and 343 is 1. So the concept of relative 
primes is not just restricted to a comparison of 2 integers.

Now the natural question is: How do I know whether two given integers 
are relative primes?

To answer this question, we first take the naive approach (but this 
approach is important as it serves to clarify and internalize this 
concept.)

1) Naive Approach

Say we have 2 integers: 24 and 77. The only way to check whether 24 
and 77 are relative primes is to actually confirm that 1 is the only 
common factor of 24 and 77. All we need to do is to perform a prime 
factorization of 24 and 77 respectively: to list out all the prime 
divisors of 24 and 77, hoping that there is not even one common prime 
factor. This method would suffice. To set the picture clear:

     24 = 2 x 2 x 2 x 3 = 2^3 x 3
     77 = 7 x 11.

As we can see, there is no prime number that divides both 24 and 77. 
Thus, the only factor of 24 and 77 is 1; in other words, 24 and 77 are 
relatively prime.

You can try out a few examples:

     Example 14: 45 = 3 x 3 x 5
                 26 = 2 x 13

                 Therefore 45 and 26 are relative primes.

     Example 15: 34 = 2 x 17
                 99 = 3 x 3 x 11

                 Therefore 34 and 99 are relative primes.

     Example 16: 24 and 56 are not relative primes since 8 is a common 
                 factor of 24 and 56. (Of course, 2 is a common factor 
                 of 24 and 56. In fact this would suffice to conclude 
                 that 24 and 56 are not relative primes.)


2) Advanced Method

Let's take 24 and 77. Take the larger of the two: 77. Divide this by 
the smaller of the two, i.e. 77 divided by 24. We can see that 77 
leaves a remainder of 5 when divided by 24. This statement may be more 
precisely expressed as:

     77 = (24)(3) + 5   ......................................[Eq. 1]

Now we shall perform some sort of algorithm:

Take 24 to be divided by 5 and check the remainder. This time the 
remainder is 4.

     24 = (5)(4) + 4   .......................................[Eq. 2]

We continue to take 5 to be divided by 4, and we obtain the remainder 
as 1.

     5 = (4)(1) + 1   ........................................[Eq. 3]

We continue to take 4 to be divided by 1, and we shall have no 
remainder:

     4 = (1)(4) + 0   ........................................[Eq. 4]

The list of remainders we obtained so far is:

     {5, 4, 1, 0}

We note that the last non-zero remainder is 1.

Theorem: If the last non-zero remainder is 1, then the two integers we 
started off with are relative primes.

In this case, we can conclude that 24 and 77 are relative primes.

Let's apply this method to check the relative primality of 56 and 89.

     89 = (56)(1) + 33
     56 = (33)(1) + 23
     33 = (23)(1) + 10
     23 = (10)(2) + 3
     10 = (3)(3)  + 1
     3  = (3)(1)  + 0

Since the last non-zero remainder is 1, 56 and 89 are relative primes.

Note that this advanced method is indeed a general and efficient 
method, as it avoids the tedious task of factoring two integers (not 
to speak of seeking the common factors). It is extremely helpful 
whenever the two integers in question are large. However, for your 13-
year-old daughter, this method is a bit advanced, so you may use it as 
a secret algorithm to check her answers to such questions.

I hope what I have explained helps. 
Regards,

Doctor Joe, The Math Forum
http://mathforum.org/dr.math/