Associated Topics || Dr. Math Home || Search Dr. Math

### 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.)

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/
```
Associated Topics:
High School Definitions
High School Number Theory
Middle School Definitions
Middle School Factoring Numbers
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search