1. ## Euler function proof

Show that $\phi(n) = 14$ is impossible.

My guess would be to start by assuming $\phi(n) = 14$ and try to find a contradiction.

$\phi(15) = 14$ would be true if 15 is prime. But it is not. $\phi(15) = \phi(3)\phi(5) = (2)(4) = 8$.

Not sure where to go after this. Any help is appreciated.

2. ## Re: Euler function proof

Originally Posted by Zalren
Show that $\phi(n) = 14$ is impossible.

My guess would be to start by assuming $\phi(n) = 14$ and try to find a contradiction.

$\phi(15) = 14$ would be true if 15 is prime. But it is not. $\phi(15) = \phi(3)\phi(5) = (2)(4) = 8$.

Not sure where to go after this. Any help is appreciated.
Let $n=\prod p_i^{\alpha}$

$\phi(n)=n\prod(1-\frac{1}{p_i})$

$\phi(n)=\frac{n}{\prod p_i}\prod (p_i-1)$

Clearly, the factor 7 in 14 cannot come from $p_i-1$ because 8 and 15 are not prime. Edit: On second thoughts, I guess there could be a $p_i$ like 29, so this proof is no longer valid.

So n must be divisible by 49 and $p_i=7$

But then $\phi(n)$ would be divisible by 7-1 = 6, which is a contradiction.

3. ## Re: Euler function proof

Originally Posted by Zalren
Show that $\phi(n) = 14$ is impossible.

My guess would be to start by assuming $\phi(n) = 14$ and try to find a contradiction.

$\phi(15) = 14$ would be true if 15 is prime. But it is not. $\phi(15) = \phi(3)\phi(5) = (2)(4) = 8$.

Not sure where to go after this. Any help is appreciated.
If $n= p_{1}\ p_{2}\ ... p_{k}$ , each $p_{i}, i=1,2,...,k$ prime, then is...

$\varphi(n)= (p_{1}-1)\ (p_{2}-1)\ ... (p_{k}-1)$ (1)

But the only possible factorisation of $\varphi(n)$ is $\varphi(n)=14 = 2*7$ and it exists a prime $p_{1}$ for which is $p_{1}-1=2$ but no prime $p_{2}$ for which is $p_{2}-1=7$...

Kind regards

$\chi$ $\sigma$

4. ## Re: Euler function proof

Originally Posted by chisigma
If $n= p_{1}\ p_{2}\ ... p_{k}$ , each $p_{i}, i=1,2,...,k$ prime, then is...

$\varphi(n)= (p_{1}-1)\ (p_{2}-1)\ ... (p_{k}-1)$ (1)

But the only possible factorisation of $\varphi(n)$ is $\varphi(n)=14 = 2*7$ and it exists a prime $p_{1}$ for which is $p_{1}-1=2$ but no prime $p_{2}$ for which is $p_{2}-1=7$...

Kind regards

$\chi$ $\sigma$
What if n is of the form $\prod p_i^{\alpha}$ where all the powers are not 1?

5. ## Re: Euler function proof

Originally Posted by alexmahone
What if n is of the form $\prod p_i^{\alpha}$ where all the powers are not 1?
In this case is...

$n= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}}\ ...\ p_{k}^{\alpha_{k}}$ (1)

... and...

$\varphi(n) = p_{1}^{\alpha_{1}-1}\ (p_{1}-1)\ p_{2}^{\alpha_{2}-1}\ (p_{2}-1)\ ...\ p_{k}^{\alpha_{k}-1}\ (p_{k}-1)$ (2)

Also in this case is $\varphi(n)= 2*7$ and it exists a couple of numbers $p_{1},\alpha_{1}$ for which is $p_{1}^{\alpha_{1}-1}\ (p_{1}-1)=2$ but no couple of numbers $p_{2},\alpha_{2}$ for which is $p_{2}^{\alpha_{2}-1}\ (p_{2}-1)=7$...

Kind regards

$\chi$ $\sigma$