In a previous problem, I was able to deduce that if you have φ(n)/n = a/b where gcd(a,b) = 1 then the largest prime factor of b must also be the largest prime factor of n.
I found the prime factorization of both integers:
7680 = 2^9*3*5
12121 = 17*23*31
I believe that in the prime factorization of n we must have the following numbers: 31, 4, 2 since
φ(n)/n = {(p1-1)(p2-1)...(pr-1)}/p1*p2*...*pr
I'm not sure where to go from this. Thanks for your help!
On
Let $F$ be a finite subset of prime numbers. Write $n$ as $\prod_{p \in F} p^{\alpha(p)}$. Then $\phi(n)/n = \prod_{p \in F} (1-1/p)$. From OP's factorisation, $17,23,31\in F$. Observe that the factor $11$ should not be present in $\frac{16×22×30}{17×23×31}$, so we add $11$ to $F$. Repeat the same step to see that $n=5×11×17×23×31$.
From "previous problem", you know that $31$ is the largest prime factor of $n$. If $n=31^km$ with $31\nmid m$ and $k\ge 1$, then $\phi(n)/n=\frac{30}{31}\phi(m)/m$ does not depend on $k$, so we take $k=1$ in order to minimize. This leaves us with the new (simpler) problem to find the minimal $m$ with $$ \frac{\phi(m)}{m}=\frac{256}{391}.$$ As before, the largest orime factor of the denominator, $23$, must be the largest prime factor of $m$. We rinse and repeat: To minimize, we take $23$ only to first power, so $m=23r $ with $$\frac{\phi(r)}r=\frac{256}{391}\cdot \frac {23}{22}=\frac{128}{187}.$$ As before, we find $17$ as next factor and arrive at the new problem $$\frac{\phi(s)}s=\frac{128}{187}\cdot\frac{17}{16}=\frac8{11},$$ then after finding $11$ at $$\frac{\phi(t)}t=\frac8{11}\cdot \frac{11}{10}=\frac45,$$ where the journey ends with the last factor $5$.