Encontrar soluciones al $\varphi\left(n\right)=2^{32}$

Question

Estoy buscando algunas soluciones al $\varphi\left(n\right)=2^{32}$ $\varphi$ Dónde está la función φ de Euler. Sé que si satisface a $n=p{1}^{r{1}}\cdot\ldots\cdot p{k}^{r{k}}$ $\varphi\left(n\right)=2^{32}$ entonces \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} por lo que estaba buscando para calcular soluciones finiding primes $p{i}$ tal que $p{i}-1\mid2^{32}$ y enchúfelos en la última ecuación. Ésos son los $p{i}-1\in\left{ 2^{l}\mid1\leq l\leq32\right} $ y por ejemplo $p{i}-1=2$ es bueno porque entonces $p_{i}=3$ es una privilegiada. \Cdot3=3\cdot2^ enchufarlo en la ecuación da $$ n=\frac{2^{32}}{\left(3-1\right)} {31} $$

Pero entonces $\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}$

¿Qué me falta aquí?

Answer 1

Otra manera de mirar el totient funciónes $$\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}$$ Suponiendo (wlog) $p_1<p_2<...<p_k$, Euclides del lema restringirá soluciones a $p_1=2$ o $r_i=1,i=\overline{2..k}$ $p_i=2^k+1$ (aka los números primos de Fermat)(simplemente porque si asumimos $r_i>1$, $p_i \mid 2^{32}$ y por Euclides del lema que esto es posible para $p_i=2>p_1$). Vamos a ver un par de ejemplos (totient función multiplicativa, esto es importante!) $$\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}$$ y así sucesivamente ... Hay $5$ números primos de Fermat menos de $2^{32}$: $\left\{ 2^1+1, 2^2+1, 2^4+1, 2^8+1, 2^{16}+1\right\}$. Usted tendrá que buscar en todas las combinaciones de $\binom{5}{0}+\binom{5}{1}+...+\binom{5}{5}=2^5$ y complementar con algunos $\varphi(2^{n})=2^{n-1}$ obtener $2^{32}$.

Answer 2

En su ecuación $n$ ese número es también múltiplo de $2$, por lo que debe incluir $p_1=2$ en sus expresiones de producto. Esto obliga a tbe señalar el factor extra de $2$ $n$ como otras respuestas.

Por cierto, $3×2^{32}$ no es la solución mínima. El número $5×2^{31}$ es menor, y usted debe experimentar con otros posibles factores primeros de Fermat. ¿Porqué usar números primos de Fermat (junto con $2$) aquí?