Using Euler’s Totient Function, how to find all values n such that, $\varphi(𝑛)=14$

elementary-number-theoryprime factorizationtotient-function

I just recently started working with Euler's Totient Function, and I came across the problem of solving for all possible integers $n$ such that $\varphi(n)=14$. I know there are similar questions with different numbers, I just wanted to verify if my approach was correct or I messed up since I could not find any $n$ satisfying that property.

We know $$\varphi(n)= \prod_{i=0}^{k} p_{i}^{a-1}(p_i-1)$$ From there we see $p_i \leq 15$ hence the primes are $p_i=\{2, 3, 5, 7, 11, 13 \}$. Ergo, we can write $n= 2^a\cdot3^b\cdot5^c\cdot7^d\cdot11^e\cdot13^f$. Using the fact that the Function is multiplicative, we can separate $$\varphi(2^a\cdot\ldots\cdot13^f)= \varphi(2^a)\cdot\ldots\cdot \varphi(13^f) = 2^{a-1}(2-1)\cdot3^{b-1}(3-1)\cdot\ldots\cdot13^{f-1}(13-1) $$

So I ended up with $\varphi(n)= 2^{a+6}\cdot3^{b+1}\cdot5^{c}\cdot7^{d-1}\cdot11^{e-1}\cdot13^{f-1}$. Then, since 14 has no factors $3, 5, 11, 13$ their exponents are at most $1$. Furthermore since $2$ and $7$ divide both divide $14$, I tried finding any combination with different multiplicities, but none yielded $14$ as a Totative.

Was my approach correct or did I miss something?

Best Answer

Regarding your method, you limit the primes of interest nicely, but you also need to eliminate from consideration any of those primes which do not pass the basic divisibility test of $\phi(p_i) \mid 14$. This would leave you with only $2$ and $3$ which clearly cannot produce the factor of $7$ needed to make $\phi(n)=14$.


Thinking about this problem separately from your approach, I would start with the key aspects:
a) $14+1 = 15$ is not a prime, and
b) $14=2\cdot 7$

So from (a) we do not arrive at $\phi(n)=14$ directly, and from (b) we need a factor of $7$. However that can only be supplied by a higher power of $7$ - which cannot be present as this would also include a factor of $6$ - or a larger prime (e.g. $29$), which would also include a larger factor not present.

So there is no number $n$ with $\phi(n)=14$.

The OEIS A005277 sequence gives even non-totients; $14$ is the smallest.

Related Question