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

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?

• How about $\varphi(17)=2^4$ case? – rtybase Jul 13 '18 at 8:07
• @rtybase What about it? – Jon Jul 13 '18 at 8:09
• And any Fermat prime in fact ... What about it? You have quite a few cases to look at ... – rtybase Jul 13 '18 at 8:11
• @rtybase Yes true all first five Fermat's numbers $F_n$ are primes such that $F_n -1 \mid 2^{32}$ but what i'm looking for is to compute solutions to $\varphi\left(n\right)=2^{32}$, and not just for primes $p$ that satisfy $p-1 \mid 2^{32}$ – Jon Jul 13 '18 at 8:24
• Jon, see my answer ... with a few examples – rtybase Jul 13 '18 at 8:26

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?
• At last! Thanks! Can i conclude from that it is sufficient to demand for every prime factor of $\frac{\varphi\left(n\right)}{\prod\left(p_{i}-1\right)}$ to be one of the $p_{i}$'s? – Jon Jul 13 '18 at 10:22
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}$.
• @taritgoswami because, as per the comments in brackets, $p_i=2^{m_i}+1 \Rightarrow p_i-1=2^{m_i}$ which may divide $2^{32}$, otherwise it's not true. – rtybase Aug 11 '18 at 19:27