Natural Numbers Coprime to 6

Date: 02/16/98 at 20:21:24
From: Jaime Pushcar
Subject: Natural numbers coprime to 6

Hi there!

I'm a grade 13 student in Ontario in an advanced algebra class, and 
we've been given a question by our teacher.  It's a university caliber 
question and whoever gets it first gets bonus marks.  Nobody has any 
clue how to do it, so I was hoping maybe someone there could help me. 
The question says:

Let N(x) denote the number of natural numbers less than x which are 
coprime to 6.  Show that 

lim as x goes to infinity of [N(x)/x] = 1/3

We all think our professor is crazy and just likes torturing students, 
but I thought I'd give it a shot.  I'd love to shove a proof in his 
face.  In a nice way, of course.

Thanks so much for your time.

Jaime

Date: 02/18/98 at 21:54:18
From: Doctor Nick
Subject: Re: Natural numbers coprime to 6

Hello Jaime -

For starters, let's really think about what numbers are coprime to 6.  
Starting with 1, these are 

        1,5,7,11,13,17,19,23,25,29,31, etc.

One thing to notice here is that between every multiple of 6, there
are exactly 2 numbers that are coprime to 6: between 0 and 6, there 
are 1 and 5; between 6 and 12 there are 7 and 11; etc.

I'll let you give a little proof of this fact. What this means for 
this proof is that if we let y be the largest multiple of 6 less than 
or equal to x, then the number of numbers coprime to 6 which are less 
than or equal to y is 2*(y/6) = y/3. Let's look at an example: 

      if x is 33, then y is 30, and y/3 is 10.
      Those ten numbers are 1,5,7,11,13,17,19,23,25,29.

Now, to finish this off, notice that x is at most y+6. Therefore, 
there are at most 2 numbers coprime to 6 between x and y. On the other 
hand, there may be no numbers coprime to 6 between  x and y. Hence we 
have the inequality

      y/3 <= N(x) <= y/3 + 2.

We need to get this inequality in terms of x. 

Notice first that y <= x. Also, y >= x-6, since there is definitely 
a multiple of 6 between x and x-6.  Using these inequalities in the 
one above we get

  (x-6)/3 <= N(x) <= x/3 + 2.

I'll let you take it from here (there's just a little more to do).

If you want to really impress your teacher, try to generalize
this result to numbers other than 6!  For instance, 
if you use 10, the limit will be 2/5; if 8 the limit is 1/4.

Have fun,

-Doctor Nick,  The Math Forum
Check out our web site http://mathforum.org/dr.math/