5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How about $\varphi(17)=2^4$ case? $\endgroup$ – rtybase Jul 13 '18 at 8:07
  • $\begingroup$ @rtybase What about it? $\endgroup$ – Jon Jul 13 '18 at 8:09
  • $\begingroup$ And any Fermat prime in fact ... What about it? You have quite a few cases to look at ... $\endgroup$ – rtybase Jul 13 '18 at 8:11
  • $\begingroup$ @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}$ $\endgroup$ – Jon Jul 13 '18 at 8:24
  • $\begingroup$ Jon, see my answer ... with a few examples $\endgroup$ – rtybase Jul 13 '18 at 8:26
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jon Jul 13 '18 at 10:22
  • $\begingroup$ Yes, that's how it works. $\endgroup$ – Oscar Lanzi Jul 13 '18 at 11:46
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why we are considering Fermat primes specially? $\endgroup$ – tarit goswami Aug 11 '18 at 19:20
  • 1
    $\begingroup$ @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. $\endgroup$ – rtybase Aug 11 '18 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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