# Math Help - Find all positive integers n such that euler's phi equals 6

1. ## Find all positive integers n such that euler's phi equals 6

I haven't the faintest idea how to do this. The homework question reads:

Find all positive integer n such that $\varphi(n) = 6$. Briefly explain why.

I know that:
1. if $n$ is prime, then $\varphi(n)=n-1$.
2. if $n=pq$, where $p$ and $q$ are distinct primes, then $\varphi(n)=(p-1)(q-1)$.
3. if $n=p^e$ then $\varphi(n)=p^e-p^{e-1}$.
4. if $n=p_1^{e_1}, p_2^{e_2},...p_r^{e_r}$, where $p_i$ are distinct primes, then $\varphi(n)=N(1-1/p_1)(1-1/p_2)...(1-1/p_r)$ (which is really just a generalization of step 3).

I can't find any other info about $phi(n)$ in my notes or in the chapters we've done this semester.

I only come up with the answer $n=7$. But the question wants all values of $n$ which result in $\varphi(n) = 6$.

How do I do this please?
Thanks

2. ## Re: Find all positive integers n such that euler's phi equals 6

Originally Posted by MSUMathStdnt
I haven't the faintest idea how to do this. The homework question reads:

Find all positive integer n such that $\varphi(n) = 6$. Briefly explain why.

I know that:
1. if $n$ is prime, then $\varphi(n)=n-1$.
2. if $n=pq$, where $p$ and $q$ are distinct primes, then $\varphi(n)=(p-1)(q-1)$.
3. if $n=p^e$ then $\varphi(n)=p^e-p^{e-1}$.
4. if $n=p_1^{e_1}, p_2^{e_2},...p_r^{e_r}$, where $p_i$ are distinct primes, then $\varphi(n)=N(1-1/p_1)(1-1/p_2)...(1-1/p_r)$ (which is really just a generalization of step 3).
I can't find any other info about $phi(n)$ in my notes or in the chapters we've done this semester.

I only come up with the answer $n=7$. But the question wants all values of $n$ which result in $\varphi(n) = 6$.

How do I do this please?
Thanks
Let's start from definition...

$\varphi(n)= n\ \prod_{p|n} \frac{p-1}{p}$ (1)

If $\varphi(n)=6$ then from (1) it is evident that n=7 and n=14 both satisfy the requirement. For n<7 but a simple exaustive search shows that there are no n<7 satisfying the requirement. For n>7 we can observe that n=9 satisfies the requirement and the same is for n=18. No possibilities for n>18...

Kind regards

$\chi$ $\sigma$

3. ## Re: Find all positive integers n such that euler's phi equals 6

How did you find that n=9? There isn't any obvious algebra which gets me to that answer. What do you mean by it is "evident" that n=7 (I agree) and that we can "observe" that n=9?
Thanks.

4. ## Re: Find all positive integers n such that euler's phi equals 6

Originally Posted by MSUMathStdnt
How did you find that n=9? There isn't any obvious algebra which gets me to that answer. What do you mean by it is "evident" that n=7 (I agree) and that we can "observe" that n=9?
Thanks.
Let's write again...

$\varphi (n)= n\ \prod_{p|n} \frac{p-1}{p}$ (1)

Two properties are evident...

a) if n prime then $\varphi(n)=n-1$...

b) if n odd then $\varphi(2 n)= \varphi(n)$ ...

On the basis of a) and b) You find immediately that for n=7 and n=14 is $\varphi(n)=6$. In order to find other n satisfying the equation You can observe that 6=2 x 3, so that on the basis of (1) this n must contain 3. Effectively n=9 satisfies the reqirement and because 9 is odd, also 18 does...

Kind regards

$\chi$ $\sigma$

5. ## Re: Find all positive integers n such that euler's phi equals 6

another way is to use the multiplicative property of φ, that is, if:

$n = p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$ where the $p_i$ are distinct primes, then

$\varphi(n) = \varphi(p_1^{k_1})\varphi(p_2^{k_2})\dots \varphi(p_r^{k_r})$

$= (p_1 - 1)p_1^{k_1 - 1}(p_2 - 1)p_2^{k_2 - 1}\dots(p_r - 1)p_r^{k_r-1}$.

now if φ(n) = 6, and p is a prime dividing n, then p^k|n for some k.

if p^3|n, then φ(p^3) divides φ(n) = 6. but φ(p^3) = (p-1)p^2, and 6 is square-free.

so n can only have single primes, or squares of primes in its factorization.

suppose p|n, but p^2∤n. then p-1|6, so p can only be 2,3,or 7.

if p^2|n then (p-1)p|6, so p can only be 2, or 3.

let's look at the last case first. suppose p^2|n, so p = 2 or 3. if p = 2, then n = 4m, for some m co-prime to 2. so 6 = φ(n) = φ(4m) = φ(4)φ(m) = 2φ(m), so φ(m) = 3.

but there are no positive integers m for which φ(m) = 3. because if a prime q|m, then q-1|3, and hence q = 2. but φ(2) = 1, and φ(2^t) = 2^(t-1) which certainly does not divide 3 for t > 1.

so n is not a multiple of 4. thus if p^2|n, p = 3 is the only possibility. so n = 9m, for some m co-prime to 3. thus 6 = φ(n) = φ(9)φ(m) = 6φ(m), which means that φ(m) = 1, so m = 1 or 2. this means that if n is not square-free, then n = 9 or 18.

so now we consider when n IS square-free: so n = 2,3,7,2*3,2*7,or3*7. that's only 6 cases to check:

φ(2) = 1.
φ(3) = 2.
φ(7) = 6.
φ(2*3) = φ(2)φ(3) = 1*2 = 2.
φ(2*7) = φ(2)φ(7) = 1*6 = 6.
φ(3*7) = φ(3)φ(7) = 2*6 = 12.

this gives us n = 7,9,14 and 18 as the only possibilities.