Math Is Fun Forum

Fred245

Guest

Help with number theory proof please

Find all the values of n that solve the following equation
φ(n) = n/6

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Help with number theory proof please

Well, I don’t think there is a solution.

From the way the equation is given, n must be divisible by 6. So let n = 6k. Hence 2 and 3 are distinct prime factors of n. Using the formula for the totient function,

where X is either 1 or the product of 1-1⁄p for all the distinct primes p≠2,3 of k. ∴

The only way this can be satisfied is if X = 1−1⁄2 – which is impossible since there is already a 1−1⁄2 in the formula.

Hence (if my working is correct) the equation has no solution.

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Help with number theory proof please

You still need to prove that it's impossible for X = 1/2.

To do this, consider that

Now we need to prove that

It's important to note that

Knowing this, we also know that

is always even, since all prime numbers after 2 are odd.  This means that the prime factorization of the numberator will always have at least one 2 in it.  We also know that obviously the denominator will never have a 2 in it's prime factorization, since all the denominators are prime numbers greater than 2.  Since we have a prime factor in the numerator that can never be cancelled by the denominator we know that X can never reach 1/2, so that should complete your proof.

---

Wrap it in bacon