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

### 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/
```
Associated Topics:
College Linear Algebra
High School Basic Algebra
High School Linear Algebra

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