Interesting number theory problem

This is an interesting problem I ran into last week. I thought I might post it as I have very little clue about how to actually solve it. The proof I turned in concluded with "lots of arm waving... QED" (which actually got a fair amount of credit since no one solved it).

Let o(n) denote the Euler totient function. That is, o(n) is the number of integers relatively prime to n that are less than n.

What is the infimum limit as n approached infinity of o(n)/n ?

I reasoned that it is 0 because if you take the k = p1*p2*...*pm (where the p's are primes to the first power), then o(k)/k = (p1 - 1)*(p2 - 1)*...*(pm - 1)/(p1*p2*...*pm), which looks somewhat like 1*2*3*4...*(n-1)/(2*3*5*...*n) which clearly goes to 0 as n approaches infinity... though most of the terms are missing, so I am not sure.

The other thought was products of n*log(n) [roughly the nth prime], though I was unable to get anywhere with this.

Anyways... an interesting problem... anyone got any ideas on it?

Quote:

---

Originally posted by Zach L.
This is an interesting problem I ran into last week. I thought I might post it as I have very little clue about how to actually solve it. The proof I turned in concluded with "lots of arm waving... QED" (which actually got a fair amount of credit since no one solved it).

Let o(n) denote the Euler totient function. That is, o(n) is the number of integers relatively prime to n that are less than n.

What is the infimum limit as n approached infinity of o(n)/n ?

I reasoned that it is 0 because if you take the k = p1*p2*...*pm (where the p's are primes to the first power), then o(k)/k = (p1 - 1)*(p2 - 1)*...*(pm - 1)/(p1*p2*...*pm), which looks somewhat like 1*2*3*4...*(n-1)/(2*3*5*...*n) which clearly goes to 0 as n approaches infinity... though most of the terms are missing, so I am not sure.

The other thought was products of n*log(n) [roughly the nth prime], though I was unable to get anywhere with this.

Anyways... an interesting problem... anyone got any ideas on it?

---

It certainly looks interesting, and I'd like to be able to give it more of a "go," but I don't know anything about the Euler totient function, sadly. Could you elaborate on it?

You might also want to post it on artofproblemsolving.com under advanced topics or other problem solving... there are some geniuses there.

Hmm.. good idea.

The Euler totient function is this (usually it is phi, but I'm using o).

o(n) = # of integers < n and relatively prime to n

o(p^n) for prime p = p^n - p^(n-1)
For n = 1, this is o(p) = p - 1

o(a*b) for relatively prime a and b = o(a) * o(b)

Quote:

---

Originally posted by Zach L.

I reasoned that it is 0 because if you take the k = p1*p2*...*pm (where the p's are primes to the first power), then o(k)/k = (p1 - 1)*(p2 - 1)*...*(pm - 1)/(p1*p2*...*pm), which looks somewhat like 1*2*3*4...*(n-1)/(2*3*5*...*n) which clearly goes to 0 as n approaches infinity... though most of the terms are missing, so I am not sure.

---

Your resoning here sounds plausible. What makes you unsure?

But 'infinity' is hard to work with, OTOH. I'm not sure one can divide infinity into prime numbers like that, it could just as well be one single infinitely large prime number, then the answer would be 1.

Alright, the professor presented the solution in class. Its a really cool solution too. My reasoning was along the right track, but far from fully developed.

Take the product of all primes to the first power: n = p1*p2*p3*... (all of thesw are really limits, of course).

Now, looking at o(n)/n we have (p1-1)*(p2-2)*.../n.

To show that lim inf (n->infinity) of o(n)/n, we can show that the above limit is 0. It will be zero if its reciprocal is infinite, of course.

So now look at the infinite product of all terms of the form: p[i]/(p[i] - 1). This can be rewritten as 1/(1-1/p[i]). Remembering that 1/(1-x) is the value of the infinite sum 1+x+x^2+... for abs(x) < 1 (which is the case for inverses of integers), we end up with an infinite product of all of the power series of the inverse of every prime (an infinite product of infinite sums... gee why did I see that :rolleyes: )

Well, as every power of every prime is in there exactly once, and will be multiplied once with every power of every other prime, etc, this product comes out to 1+1/2+1/3+1/4+1/5+... (the harmonic series) which diverges, so the limit of o(n)/n for the given n is 0, and consequently, so is the infimum as n goes to infinity.

Anyways... I thought that was kind of cool.