Math Is Fun Forum

parthenos

Member

Registered: 2008-08-25

Posts: 9

Euler's function problem

Prove for any give positive integer N there exists only finite many integers n with
φ(n) = N where φ denotes Euler’s function.  Conclude in particular that φ(n) tends to infinity as n tends to infinity.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Euler's function problem

Remember the fundamental theorem of arithmetic, especially uniqueness.  Also remember the formula for calculating phi(n).

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

athena

Guest

Re: Euler's function problem

please explain further

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Euler's function problem

Fundamental Theorm of Arithmetic (in my own words, not from a dictionary):

Every positive integer is either prime or composite.  If it is prime then its only factors are itself and 1.  If it is composite it can be uniquely represented by its prime factors.  For example, 11 is prime, meaning its only factors are 1 and 11.  12 is composite, and can be reduced to 2^2 * 3^1.  No other set of prime factors can represent the number 12.

Formula for calculating phi(n):

Reduce n to it's prime factors -

Now, let's consider these definitions as they relate to your question.  N can be uniquely represented by its prime factors.  Consider the relationship between prime factorization and the formula for phi(n).

Edit: As is generally the case in math, there is more than 1 way to solve this problem.  According to Wikipedia this function has a very simple lower bound:

Given this, it's trivial to prove phi(n) = N for only finitely many n and that phi(n) tends to infinity as n approaches infinity.  Of course, the hard work is actually proving that lower bound (which Wikipedia does not seem to provide), but it's another avenue for you to consider.

Last edited by TheDude (2008-08-27 03:55:07)

---

Wrap it in bacon

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Euler's function problem

Consider working the problem "backwards".  That is, given a number k, write k as a product of primes and then take a look at what the requirements are for phi(n) = k.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."