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

### Fractions between 0 and 1

```
Date: 07/29/2001 at 12:45:17
From: Courtney Allison
Subject: Way to find number of fractions between 0 and 1 with
denominators from 2 to 100

Dear Dr. Math,

Is there a way to find the number of different (no equivalent
fractions) fractions between 0 and 1 with denominators from 2 to 100
without writing out every fraction and counting them? Or is this
information already charted somewhere on the Web?

Thanks,

Courtney
```

```
Date: 07/30/2001 at 13:14:40
From: Doctor Greenie
Subject: Re: Way to find number of fractions between 0 and 1 with
denominators from 2 to 100

Hi, Courtney -

I don't see a way to come up with a formula that will tell you
explicitly how many different fractions there will be with
denominators less than or equal to some integer n. That is, I can't
come up with an explicit formula that will give the answer to the
question "how many irreducible fractions are there with denominators
less than or equal to 123?"

(Note that there is a huge amount of work that has been done in number
theory with which I am not familiar. It is quite conceivable to me
that there might be a way to develop an explicit formula using some of

But there at least appears to be a way to determine the number of
irreducible fractions for any denominator n without writing out all
the proper fractions with that denominator and counting the ones which
can't be reduced.

Let's think first of counting the fractions with denominator n which
CAN be reduced. These are the fractions whose numerators have a factor
in common with the denominator.

Suppose the prime factorization of the denominator contains the prime
factors (p1, p2, p3, p4, ...).  Let A, B, C, D, ... be the sets
consisting of all the numbers less than the denominator n which are
multiples of the prime factors p1, p2, p3, p4, ..., respectively. The
number of fractions with denominator n that CAN be reduced is the
number of elements in the union of sets A, B, C, D, ....

Recognizing that for a large denominator n the list of distinct prime
factors can be large, I will sipmlify the discussion from this point
on by describing the case where the prime factorization contains only
(at most) four distinct primes.

The inclusion/exclusion principle tells us how to count the number of
elements in the union of sets A, B, C, and D.  If I use the notation
that "a" is the number of elements in set A, "ab" is the number of
elements in the intersection of sets A and B, ..., and "abcd" is the
number of elements in the intersection of sets A, B, C, and D, then
the number of elements in the union of sets A, B, C, and D is

(a+b+c+d) - (ab+ac+ad+bc+bd+cd) + (abc+abd+acd+bcd) - (abcd)  (*)

Then the number of fractions with denominator "n" that can NOT be
reduced is the total number of numerators less than n (i.e., n-1),
minus the number given by the preceding equation (*).

So we have the following for the number of irreducible fractions with
denominator n:

(n-1) - [(a+b+c+d) - (ab+ac+ad+bc+bd+cd) + (abc+abd+acd+bcd) - (abcd)]

or

(n-1) - (a+b+c+d) + (ab+ac+ad+bc+bd+cd) - (abc+abd+acd+bcd) + (abcd)

Here, in words, is a description of this method (following this
description, I will show several examples).

Number of irreducible fractions with denominator n =

(number of numerators less than n)

- (number of numerators less than n that are divisible by some
prime factor of n)

+ (number of numerators less than n that are divisible by two
different prime factors of n)

- (number of numerators less than n that are divisible by three
different prime factors of n)

+ (number of numerators less than n that are divisible by four
different prime factors of n)

... and, in the general case, there may be more terms to be added or
subtracted, depending on the number of different prime factors in the
prime factorization of the denominator....

Here are some examples...

n = 51: prime factorization is 51 = 3*17

The number of numerators less than 51 is 51-1 = 50
The number of numerators less than 51 and divisible by 3 is
(51/3)-1 = 16
The number of numerators less than 51 and divisible by 17 is
(51/17)-1 = 2

The number of irreducible fractions with denominator 51 is

(50) - (16+2) = 50-18 = 32

n = 52:  prime factorization is 52 = 2*2*13

The number of numerators less than 52 is 52-1 = 51
The number of numerators less than 52 and divisible by 2 is
(52/2)-1 = 25
The number of numerators less than 52 and divisible by 13 is
(52/13)-1 = 3
The number of numerators less than 52 and divisible by both 2 and 13
is (52/26)-1 = 1

The number of irreducible fractions with denominator 52 is

(51) - (25+3) + (1) = 51-28+1 = 24

n = 53:

53 is prime; all 52 numbers less than 53 are relatively prime to 53;
the number of irreducible fractions with denominator 53 is 52.

n = 54:  prime factorization is 2*3*3*3

The number of numerators less than 54 is 54-1 = 53
The number of numerators less than 54 and divisible by 2 is
(54/2)-1 = 26
The number of numerators less than 54 and divisible by 3 is
(54/3)- 1= 17
The number of numerators less than 54 and divisible by both 2 and 3
is (54/6)-1 = 8

The number of irreducible fractions with denominator 54 is

(53) - (26+17) + (8) = 53-43+8 = 18

There are only a few denominators less than 100 where the prime
factorization contains enough factors to make the process more
complicated than the examples above. Here is one of them...

n = 60:  prime factorization is 2*2*3*5

The number of numerators less than 60 is 60-1 = 59
The number of numerators less than 60 and divisible by 2 is
(60/2)-1 = 29
The number of numerators less than 60 and divisible by 3 is
(60/3)-1 = 19
The number of numerators less than 60 and divisible by 5 is
(60/5)-1 = 11
The number of numerators less than 60 and divisible by both 2 and 3
is (60/6)-1 = 9
The number of numerators less than 60 and divisible by both 2 and 5
is (60/10)-1 = 5
The number of numerators less than 60 and divisible by both 3 and 5
is (60/15)-1 = 3
The number of numerators less than 60 and divisible by 2, 3, and 5
is (60/30)-1 = 1

The number of irreducible fractions with denominator 60 is

(59) - (29+19+11) + (9+5+3) - (1) = 59-59+17-1 = 16

Thanks for sending us this problem.  I got a lot of good mental
exercise from it.

Please write back if you have further questions on this problem.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

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