For any $n=p_{1}^{r_{1}}\cdot\ldots\cdot p_{k}^{r_{k}}$ I know that $$ \varphi\left(n\right)=\prod_{i=1}^{k}p_{i}^{r_{i}}\left(1-\frac{1}{p_{i}}\right) $$ and from that we can get that $$ n=\frac{\varphi\left(n\right)}{\prod\left(p_{i}-1\right)}\prod p_{i} $$ Therefore I was looking for primes $p_{i}$ such that $p_{i}-1\mid\varphi\left(n\right)$ but it seems to be not enough. As written here we also need to make sure that all primes in $\frac{\varphi\left(n\right)}{\prod\left(p_{i}-1\right)}$ are also in $\prod p_{i}$ but I don't understand why. Any explanation please?


What I was looking for specifically are some solutions to $\varphi\left(n\right)=2^{32}$ by using the first Fermat's numbers $F_n=2^{2^n}+1$ as primes and apparently I had to add also $2$ as another prime.

For example: $$ n_{0}=\frac{2^{32}}{F_{0}-1}\cdot F_{0}=\frac{2^{32}}{2^{2^{0}}}\left(2^{2^{0}}+1\right)=3\cdot2^{31}\notin\varphi^{-1}\left(2^{32}\right) $$ But $$ n'_{0}=\frac{2^{32}}{\left(2-1\right)\left(F_{0}-1\right)}\cdot2\cdot F_{0}=3\cdot2^{32}\in\varphi^{-1}\left(2^{32}\right) $$


Not sure if I understand you completely. Write $n=p_1^{a_1}\cdots p_k^{a_k}$. In other words, $n$ fixes the primes $p_i$. Since $\prod_{i=1}^k p_i$ divides $n$, it follows from your second equation that $\phi(n)/\prod_{i=1}^n(p_i-1)$ must divide $n$, so that its prime factors must be a subset of $\{p_1,\cdots,p_n\}$.


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.