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}\)