Show that the set of numbers whose Euler function is less than a certain value has an upper bound

Question

Let $S = \{n \in \mathbb{Z} \mid \varphi(n) \le 12 \}$ be the set of number whose Euler function is less or equal 12. Prove that $S$ has an upper bound.

In the example $S= \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28, 30, 36, 42\}$ and I'd like to show formally that no $k > 42 \in S$.

I've demostrated some particular cases:

• if $k > 13$ is prime, then $\varphi(k) = k - 1 > 12$, thus $k \notin S$.
• if $k^\alpha$ is a power of a prime $k > 13$, then $\varphi(k^\alpha) = \varphi(k^{\alpha-1})\cdot(k-1) > (k-1) > 12$, thus $k^\alpha \notin S$.

For the general case, I've thought about factorization. So $k = p_1^{\alpha_1} \cdot \ldots \cdot p_n^{\alpha_n}$, where each $p_i$ must be in $\{2, 3, 5, 7, 11, 13\}$. I can't however conclude my proof.

Answer 1

The Fundamental theorem of arithmetic allows to write $k = p_1^{\alpha_1} \cdot \ldots \cdot p_n^{\alpha_n}$. As $\varphi(p) = p-1$, $p$ must be less than 13. So the only primes allowed are $\{2,3,5,7,11,13\}$. Consider every possibile combination:

• $p_1 = 13$ gives $13$ and $13 \cdot 2 = 26$
• $p_1 = 11$ gives $11$ and $11 \cdot 2 = 22$
• $p_1 = 7$ gives $7$, $7 \cdot 2 = 14$, $7 \cdot 2^2 = 28$, $7 \cdot 3 = 21$, $7 \cdot 2 \cdot 3 = 42$
• $p_1 = 5$ gives $5$, $5 \cdot 2 = 10$, $5 \cdot 2^2 = 20$, $5 \cdot 3 = 15$, $5 \cdot 2 \cdot 3 = 30$
• $p_1 = 3$ gives $3$, $3^2 = 9$, $3 \cdot 2 = 6$, $3 \cdot 2^2 = 12$, $3 \cdot 2^3 = 24$, $3^2 \cdot 2 = 18$, $3^2 \cdot 2^2 = 36$
• $p_1 = 2$ gives $2$, $2^2 = 4$, $2^3=8$, $2^4 = 16$

By definition we also have $\varphi(1) = 1$.

Every combination has been explored, so the list provided above is complete.