Euler's Phi Function

[bigp0ppa1046]

Find at least 5 different numbers n with Φ(n)=160.

Φ(n)= #{a: 1≤ a ≥m and gcd(a,m)=1}

 

[soroban]

Hello, bigp0ppa1046!

A rather tricky problem . . .

Find at least 5 different numbers $\displaystyle n$ with: $\displaystyle \,\phi(n) \,=\,160$

For those unfamiliar with Euler's phi-function . . .

$\displaystyle \phi(n)$ is the number of positive integers less than $\displaystyle n$ and relatively prime to $\displaystyle n.$
. . $\displaystyle 1$ is included in the count.

For example: $\displaystyle \,\phi(42) \,=\,12$
. . $\displaystyle 1,\,5,\,11,\,13,\,17,\,19,\,23,\,25,\,29,\,31,\,37,\,41$ are relatively prime to $\displaystyle 42.$

Can't sleep? .Check out: $\displaystyle \,\phi(72)\,=\,24,\;\phi(120)\,=\,32$


Fortunately, there is a formula for $\displaystyle \phi(N).$

Write the prime factorization of \(\displaystyle N:\; N\:=\_{_1}^{^a}\cdot p_{_2}^{^b}\cdot p_{_3}^{^c}\cdot p_{_4}^{^d}\,\cdots\)

. . Then: $\displaystyle \:\phi(N)\;=\;p_1^{a-1}(p_1\,-\,1)\,\cdot\,p_2^{b-1}(p_2\,-\,1)\,\cdot\,p_3^{c-1}(p_3\,-\,1)\,\cdots$

Each pair is the product of the prime to the one-less power times one less than the prime.


For this problem, we must work backwards.
We are given: $\displaystyle \phi(N) \,=\,160$, and we must generate values of $\displaystyle N.$


I found five values:

\(\displaystyle \begin{array}{ccccc}1\cdot160 & \,=\, & 2^{^0}(2-1)\cdot161^{^0}(161-1) & \;\Rightarrow\; & 2^{^1}\cdot161^{^1} & \,=\, & 322 \\

4\cdot40 & = &5^{^0}(5-1)\cdot41^{^0}(41-1) & \;\Rightarrow\; & 5^{^1}\cdot41^{^1} & = & 205 \\

10\cdot16 & = & 11^{^0}(11-1)\cdot17^{^0}(17-1) & \;\Rightarrow\; & 11^{^1}\cdot17^{^1} & = & 187\\

1\cdot4\cdot40 & = & 2{^^}0(2-1)\cdot5^{^0}(5-1)\cdot41^0(41-1) & \;\Rightarrow\; & 2^{^1}\cdot5^1\cdot41^{^1} & = & 410 \\

1\cdot10\cdot16 & = & 2^{^0}(2-1)\cdot11^{^0}(11-1)\cdot17^0(17-1) & \;\Rightarrow\; & 2^{^1}\cdot11^{^1}\cdot17^1 & = & 374\end{array}\)