Find all natural numbers $n$ such that $\\phi(n)=\\simplify[std]{{tp1}/{bp1}}n$
\nYou are given that the general form of $n$ is \\[n = p_1^{\\alpha_1} p_2^{\\alpha_2}\\cdots p_s^{\\alpha_s}\\]
\nfor a fixed set of primes $p_1,\\;p_2,\\ldots,p_s$ where $\\alpha_j \\ge 1\\;\\;j=1,\\ldots,\\;s$.
\nSelect the primes involved from these choices.
\n[[0]]
\nNote that you are deducted one mark for every wrong choice. The minimum mark is 0.
", "steps": [{"type": "information", "prompt": "\n\n\nUse the formula for $\\phi(n)$:
\n\n\n\n\\[\\phi(n)= n\\left(1-\\frac{1}{p_1}\\right)\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)\\]
\n\n\n\nwhere $n = p_1^{\\alpha_1} p_2^{\\alpha_2}\\cdots p_s^{\\alpha_s},\\;\\;\\;\\alpha_j \\ge 1\\;\\;j=1,\\ldots,\\;s$
\n\n", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "coprime", "euler totient function", "factors", "MAS3214", "number theory", "prime decomposition", "prime factorisation", "primes"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Given $\\frac{a}{b} \\in \\mathbb{Q}$ for suitable choices of $a$ and $b$, find all $n \\in \\mathbb{N}$ such that $\\phi(n)=\\frac{a}{b}n$.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n\n\nWe can write the formula for the Euler Totient Function for \\[n = p_1^{\\alpha_1} p_2^{\\alpha_2}\\cdots p_s^{\\alpha_s},\\;\\;\\;\\alpha_j \\ge 1\\;\\;j=1,\\ldots,\\;s\\] as
\n\n\n\n\\[\\phi(n)= n\\left(1-\\frac{1}{p_1}\\right)\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)\\]
Hence we have:
\\[ \\begin{eqnarray*}\n\n\\phi(n)= n\\left(1-\\frac{1}{p_1}\\right)\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)&=&\\simplify[std]{{tp1}/{bp1}}n \\Rightarrow\\\\\n\n\\left(1-\\frac{1}{p_1}\\right)\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)&=&\\simplify[std]{{tp1}/{bp1}}\n\n\\end{eqnarray*}\n\n\\]
It is clear from the denominator of $\\frac{\\var{tp1}}{\\var{bp1}}$ that the prime $\\var{ordp[1]}$ must be in the factorization of $n$.
We can assume that $p_1=\\var{ordp[1]}$.
Substituting these values in the identity above gives:
\\[ \\begin{eqnarray*}\n\n\\left(1-\\frac{1}{\\var{ordp[1]}}\\right)\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)&=&\\simplify[std]{{tp1}/{bp1}}\\Rightarrow\\\\\n\n\\left(\\frac{\\var{ordp[1]-1}}{\\var{ordp[1]}}\\right)\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)&=&\\simplify[std]{{tp1}/{bp1}}\\Rightarrow\\\\\n\n\\left(1-\\frac{1}{p_2}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)&=&\\frac{\\var{ordp[0]-1}}{\\var{ordp[0]}}\n\n\\end{eqnarray*}\n\n\\]
Hence we see that $\\var{ordp[0]}$ is also in the prime decomposition of $n$ and putting $p_2=\\var{ordp[0]}$ we find:
\\[\\begin{eqnarray*}\n\n\\left(\\simplify[std]{{ordp[0]-1}/{ordp[0]}}\\right)\\left(1-\\frac{1}{p_3}\\right)\\cdots \\left(1-\\frac{1}{p_s}\\right)&=&\\frac{\\var{ordp[0]-1}}{\\var{ordp[0]}}\\\\\n\n\\end{eqnarray*}\n\n\\]
But the only way that can happen is when there are only the two primes we have already found.
\n\n\n\nHence we see that $\\var{ordp[0]}$ and $\\var{ordp[1]}$ are the only two primes in the factorization of $n$ and that:
\\[n =\\var{ordp[0]}^{\\alpha_1}\\var{ordp[1]}^{\\alpha_2},\\;\\;\\alpha_1,\\;\\;\\alpha_2 \\ge 1\\]