1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ And how did you find those solutions? $\endgroup$ – Henning Makholm Apr 8 '16 at 11:52
  • $\begingroup$ (Note that $4294967296=2^{32}$). $\endgroup$ – Henning Makholm Apr 8 '16 at 11:56
  • $\begingroup$ @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. $\endgroup$ – Moo Apr 8 '16 at 13:10
2
$\begingroup$

$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.)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Apr 8 '16 at 12:05
  • $\begingroup$ Yeah, I meant "coincidence" in the sense that "$\phi(n) = 2^k$ has $k$ solutions when $k = 32$". $\endgroup$ – Patrick Stevens Apr 8 '16 at 12:06
  • 1
    $\begingroup$ (Ignore that $+30$ in my previous comment; I was not thinking clearly). $\endgroup$ – Henning Makholm Apr 8 '16 at 12:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.