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 
these more advanced techniques.)

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/