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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.