Find solutions to $\varphi\left(n\right)=2^{32}$

Question

I'm looking for some solutions to $\varphi\left(n\right)=2^{32}$ where $\varphi$ is the Euler's totient function. I know that if $n=p_{1}^{r_{1}}\cdot\ldots\cdot p_{k}^{r_{k}}$ satisfies $\varphi\left(n\right)=2^{32}$ then \begin{align*} & 2^{32}=\varphi\left(n\right)=\prod_{i=1}^{k}p^{r_{i}}\left(1-\frac{1}{p_{i}}\right)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right)\\ \Rightarrow\quad & n=\frac{2^{32}}{\prod\left(p_{i}-1\right)}\prod p_{i} \end{align*} So I was looking to compute solutions by finiding primes $p_{i}$ such that $p_{i}-1\mid2^{32}$ and plug them into the last equation. Those are $p_{i}-1\in\left\{ 2^{l}\mid1\leq l\leq32\right\} $ and for example $p_{i}-1=2$ is good because then $p_{i}=3$ is a prime. Plugging it into the equation gives $$ n=\frac{2^{32}}{\left(3-1\right)}\cdot3=3\cdot2^{31} $$

But then $\varphi\left(3\cdot2^{31}\right)=\varphi\left(3\right)\varphi\left(2^{31}\right)=2\left(2^{31}-2^{30}\right)=2^{31}\boldsymbol{\neq}2^{32}$

What am I missing here?

Answer 1

In your equation for $n$ that number is also a multiple of $2$, so you must include $p_1=2$ in your product expressions. This forces tbe extra factor of $2$ into $n$ as other answers point out.

Incidentally, $3×2^{32}$ is not the minimal solution. The number $5×2^{31}$ is less, and you should experiment with other possible Fermat prime factors. Why should you use Fermat primes (along with $2$) here?

Answer 2

Another way to look at the totient function is $$\varphi(n)=p_1^{r_1-1}(p_1-1)\cdot p_2^{r_2-1}(p_2-1)...p_k^{r_k-1}(p_k-1)=2^{32}$$ Assuming (wlog) $p_1<p_2<...<p_k$, Euclid's lemma will restrict solutions to $p_1=2$ or $r_i=1,i=\overline{2..k}$ and $p_i=2^{m_i}+1$ (aka Fermat primes)(simply because if we assume $r_i>1$, then $p_i \mid 2^{32}$ and due to Euclid's lemma this is possible for $p_i=2>p_1$). Let's see a few examples (totient function is multiplicative, this is important!) $$\varphi(2^{33})=2^{32}$$ $$\varphi(3\cdot2^{32})=\varphi(3)\cdot\varphi(2^{32})=2^{32}$$ $$\varphi(17\cdot2^{29})=\varphi(17)\cdot\varphi(2^{29})=2^{32}$$ $$\varphi(3\cdot17\cdot2^{28})=\varphi(3)\cdot\varphi(17)\cdot\varphi(2^{28})=2^{32}$$ $$\varphi(3\cdot5\cdot17\cdot2^{26})=\varphi(3)\cdot\varphi(5)\cdot\varphi(17)\cdot\varphi(2^{26})=2^{32}$$ and so on ... There are $5$ Fermat primes less than $2^{32}$: $\left\{ 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^{16}+1\right\}$. You will have to look at all the combinations $\binom{5}{0}+\binom{5}{1}+...+\binom{5}{5}=2^5$ and complement with some $\varphi(2^{n})=2^{n-1}$ to obtain $2^{32}$.

Answer 3

Let $n=2^k \prod_{j=1}^m p_j{ }^{r_j},$ where $p_j$’s are distinct odd primes.

Then $$\displaystyle \phi\left(2^k\right) \prod_{j=1}^m\left(p_j-1\right) p_j^{r_j-1}=2^{32}\tag*{} $$ Since there is no odd factor on the right, $r_j$ is forced to be $1$ and $p_j-1=2^{s_j}$ for some integer $s_j$. However, $s_j$ has no odd factors, i.e. a power of $2$, for otherwise $s_j=hk$ for some odd integer $k$ implies $p_j=(2^{h})^k+1=\left[\left(2^h\right)^k+1\right]\left[\left(2^h\right)^{k-1}-\left(2^h\right)^{k-2}+\cdots+1\right] $ is NOT a prime. Hence

$$p_j=2^{2^j}+1 \textrm{ is a Fermat prime.} $$ Since there are ONLY $5$ Fermat primes less than $2^{32}, $ we let the set of Fermat primes less than $2^{32}$ be

$$F=\left\{2^{2^{j-1}}+1: j \in\{1,2,3,4,5\}\right\}$$

Therefore, other than the trivial solution $2^{33}$, there are totally $32$ solutions of $\phi(n)=2^{32}$ and the solution set S is $$ S= \left\{2^{33}\right\} \cup \left\{2^{(33-\sum_{j=1}^5 2^{j-1} r_j )}q_1^{r_1} q_2^{r_2} q_3^{r_3} q_4^{r_4} q_5^{r_5}: r_i \in\{0,1\} \wedge q_i \in F\right\}. $$

The second greatest solution is $$n=4\prod_{j=1}^5 (2^{2^{j-1}}+1)=4\cdot 4294967295=17179869180$$