Relatively Prime Numbers
What is Relatively Prime?
By definition, two numbers are relatively prime if and only if
the greatest common divisor of both numbers is 1.
A Few Loose Ends
Question: Are there numbers greater than x
that are relatively prime to x ?
Sure. Relatively prime is a pairwise relationship. It takes
two numbers to be relatively prime. Certainly 15 is relatively
prime to 32, but also 32 is relatively prime to 15.
Question: Is there a number that is
relatively prime to every postive number?
Yup! That number is 1. Remember, by definition, two numbers
are relatively prime if their greatest common divisor is 1. The
GCD of 1 and x for all x is 1.
Question: Is there any other use of
relatively prime? Oh yeah! The one important use that comes to
mind quickly is finding out how many proper fractions are reduced
to lowest terms with a given denominator. If you have a fraction
that is not reduced to lowest terms, then there is some number
(other than 1) that will divide both the numerator and
denominator evenly. That number, then, is a common divisor (from
which you can find a greatest common divisor, but the gcd
won’t be 1). So, the problems “How many positive
numbers less than or equal to x are relatively prime to x ?”
and “How many positive proper fraction with a denominator of
x; ( x  2) are reduced to lowest terms?” are
the same.
The Sum of Relatively Prime Integers
A new question that has come up is “What is the sum of
the positive integers that are less than x and relatively prime
to x ”? Using the information from section 2, let N =  be the number of positive integers less than x that
are relatively prime to x . Then, the sum of the positive
integers that are less than x and relatively prime to x is  .
Example:
What is the sum of the positive integers that are less than 12
and relatively prime to 12?
Since 12 = 2 2 · 3, we know N = [(2 - 1) · 2
1 ] · [(3 - 1) · 3 0 ] = [1 · 2] · [2 · 1]
= 4. Therefore, the sum of the positve integers that are less
than 12 and relatively prime to 12 is
|
