# Euler's $\phi(n)$ function and solutions of $\phi(n) = 4294967296=2^{32}$ [duplicate]

Find all $n \in \mathbb{N}$ such that $\phi(n) = 4294967296=2^{32}$.

I managed to find that $16106127360$, $8589934592$, $10737418240$ and $12884901888$ are solutions for the equation, but I do not know how to find all of them.

## marked as duplicate by Martin Sleziak, Namaste, Delta-u, Mostafa Ayaz, SomosJul 13 '18 at 23:04

• And how did you find those solutions? – Henning Makholm Apr 8 '16 at 11:52
• (Note that $4294967296=2^{32}$). – Henning Makholm Apr 8 '16 at 11:56
• @arm46: $17179869180$, $11453246120$, $13743895344$, $9162596896$, $16169288640$, $10779525760$, $12935430912$, $8623620608$, $17113021440$, $11408680960,13690417152$, $9126944768$, $16106373120$, $10737582080$, $12885098496$, $8590065664$, $17179607040$, $11453071360$, $13743685632$, $9162457088$, $16169041920$, $10779361280$, $12935233536$, $8623489024$, $17112760320$, $11408506880$, $13690208256$, $9126805504$, $16106127360$, $10737418240$, $12884901888$, $8589934592$$,$there are 32 of them. – Moo Apr 8 '16 at 13:10

$4294967296 = 2^{32}$.

Recall that $\phi(a b) = \phi(a) \phi(b)$ if $a, b$ are coprime; and that $\phi(p^n) = (p-1) p^{n-1}$.

Therefore if $\phi(p_1^{n_1} \dots p_m^{n_m}) = 2^{32}$ then $\phi(p_i^{n_i}) = 2^{k_i}$, some $k_i$; that is $(p_i-1) p_i^{n_i - 1}$.

That is, $p_i = 2$, or $p_i$ is one more than a power of $2$ and it appears only to the power $1$.

Also if $p_i = 2$ then we can't have $n_i > 32$.

Now it's a fairly horrible case-bash, I think, to find the 32 solutions. (I think that number of solutions is a coincidence.)

• Depends on what you mean by coincidence -- each solution corresponds to a subset of $\{3,5,17,257,65536\}$ (the only known odd Fermat primes), which doesn't look particularly horrible to me. It is coincidence in the sense that $\phi(n)=2^k$ has exactly $32$ solutions whenever $31\le k\le 2^{33}+30$, and likely also higher $k$ too unless there are more Fermat primes. – Henning Makholm Apr 8 '16 at 12:05
• Yeah, I meant "coincidence" in the sense that "$\phi(n) = 2^k$ has $k$ solutions when $k = 32$". – Patrick Stevens Apr 8 '16 at 12:06
• (Ignore that $+30$ in my previous comment; I was not thinking clearly). – Henning Makholm Apr 8 '16 at 12:11