1. Euler function proof

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

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

$\displaystyle \phi(15) = 14$ would be true if 15 is prime. But it is not. $\displaystyle \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 $\displaystyle \phi(n) = 14$ is impossible.

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

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

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

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

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

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

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

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

3. Re: Euler function proof

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

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

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

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

4. Re: Euler function proof

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
What if n is of the form $\displaystyle \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 $\displaystyle \prod p_i^{\alpha}$ where all the powers are not 1?
In this case is...

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

... and...

$\displaystyle \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 $\displaystyle \varphi(n)= 2*7$ and it exists a couple of numbers $\displaystyle p_{1},\alpha_{1}$ for which is $\displaystyle p_{1}^{\alpha_{1}-1}\ (p_{1}-1)=2$ but no couple of numbers $\displaystyle p_{2},\alpha_{2}$ for which is $\displaystyle p_{2}^{\alpha_{2}-1}\ (p_{2}-1)=7$...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$