// Numbas version: finer_feedback_settings
{"name": "Find n such that $\\phi(n)$ is the given value", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"t6": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[6,1,[[3,2]],[[7,14],[9,18],[]]]", "description": "", "name": "t6"}, "valmess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\n\n\nif(abs(si[2])=0,'Looking at the table we see that there is no value in the table such that $ \\\\phi(p^\\\\alpha)=\\\\var{m}$.','Looking at the table we see that $ \\\\phi(\\\\var{si[2][0][0]}^{\\\\var{si[2][0][1]}})=\\\\var{m}$. \n\nHence we have $n=\\\\var{si[2][0][0]^si[2][0][1]}$ and $n=\\\\var{2*si[2][0][0]^si[2][0][1]}$ are solutions.')\n\n", "description": "", "name": "valmess"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "t[j][0]", "description": "", "name": "m"}, "j": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..6)", "description": "", "name": "j"}, "primess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\n\n\nif(si[1]=1,'Since $\\\\var{m}+1=\\\\var{m+1}$ is a prime number we have solutions, $n=\\\\var{m+1}$ and $n=2\\\\times \\\\var{m+1}=\\\\var{2*(m+1)}$. \\n Next we look to see if $\\\\var{m}$ is a value in the table.',\n\n'Since $\\\\var{m}+1=\\\\var{m+1}$ is not a prime number we next look to see if $\\\\var{m}$ is a value in the table.')\n\n", "description": "", "name": "primess"}, "solmess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\n\n\nif(j=4, 'Hence there are no solutions, and you would have entered $0$ and $0$',\n\n'Hence the solutions written in descending order are: $\\\\var{s}$.\\n\n\nSo you would enter $\\\\var{s[0]},\\\\;\\\\var{s[1]}$ in the answers.')\n\n", "description": "", "name": "solmess"}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[t6,t10,t12,t18,t14,t22,t28]", "description": "", "name": "t"}, "t12": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[12,1,[],[[13,26],[],t6]]", "description": "", "name": "t12"}, "m1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "m/2", "description": "", "name": "m1"}, "t18": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[18,1,[[3,3]],[[19,38],[27,54],[]]]", "description": "", "name": "t18"}, "factmess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\nif(abs(si[3][2])=0,if(2|m1,\n\n'The factorization $\\\\var{m} = 2 \\\\times \\\\var{m1}$ does not lead to any other solutions, even though $\\\\var{m1}$ is even, as $\\\\var{m1}+1=\\\\var{m1+1}$ is not prime and there is no value in the table such that $ \\\\phi(p^\\\\alpha)=\\\\var{m1}$.', \n\n'The factorization $\\\\var{m} = 2 \\\\times \\\\var{m1}$ does not lead to any other solutions as $\\\\var{m1}$ is odd.'),\n\n'The factorization $12=2 \\\\times 6$ does lead to more solutions as $6+1=7$ is prime and also we have $\\\\phi(3^2)=6$ from the table hence:\\\\[\\\\begin{eqnarray}12&=&2 \\\\times 6 = \\\\phi(2^2) \\\\times \\\\phi(7)=\\\\phi(28)\\\\\\\\12&=&2 \\\\times 6 = \\\\phi(3^1) \\\\times \\\\phi(7)=\\\\phi(21)\\\\\\\\12&=&2 \\\\times 6 = \\\\phi(2^2) \\\\times \\\\phi(14) \\\\textrm{ not allowed as 4 and 14 are not coprime.}\\\\\\\\12&=&2\\\\times 6 = \\\\phi(3^1)\\\\times \\\\phi(14)=\\\\phi(42)\\\\\\\\12&=&2\\\\times 6=\\\\phi(2^2)\\\\times \\\\phi(3^2)=\\\\phi(36)\\\\\\\\12&=&2 \\\\times 6 = \\\\phi(3^1) \\\\times \\\\phi(3^2) \\\\textrm{ not allowed as 3 and 9 are not coprime.}\\\\end{eqnarray}\\\\]')\n\n", "description": "", "name": "factmess"}, "si": {"templateType": "anything", "group": "Ungrouped variables", "definition": "t[j]", "description": "", "name": "si"}, "s": {"templateType": "anything", "group": "Ungrouped variables", "definition": "ls[j]", "description": "", "name": "s"}, "t14": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[14,0,[],[[],[],[]]]", "description": "", "name": "t14"}, "t10": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[10,1,[],[[11,22],[],[]]]", "description": "", "name": "t10"}, "t22": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[22,1,[],[[23,46],[],[]]]", "description": "", "name": "t22"}, "t28": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[28,1,[],[[29,58],[],[]]]", "description": "", "name": "t28"}, "ls": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[[18,14,9,7],[22,11],[42,36,28,26,21,13],[54,38,27,19],[0,0],[46,23],[58,29]]", "description": "", "name": "ls"}}, "ungrouped_variables": ["primess", "t6", "j", "m", "si", "t14", "t28", "s", "t10", "t", "t12", "m1", "valmess", "t22", "t18", "solmess", "factmess", "ls"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "name": "Find n such that $\\phi(n)$ is the given value", "functions": {}, "showQuestionGroupNames": false, "parts": [{"showCorrectAnswer": true, "marks": 0, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{s[0]}", "minValue": "{s[0]}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{s[1]}", "minValue": "{s[1]}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "prompt": "Find all $n \\in \\mathbb{N}$ such that $\\phi(n)=\\var{m}$ and if at least two exist, enter the largest and second largest here:
\nLargest=[[0]] Second largest=[[1]]
\nIf there are no solutions, enter 0 in both answer fields.
", "steps": [{"prompt": "\n\n\n$\\phi(n)$
\n\n\n\nThis is the Euler totient function and $\\phi(n)$ and it counts up the number of integers less than $n$ which are coprime to $n$.
\n\n\n\nSuppose \\[n = p_1^{\\beta_1}p_2^{\\beta_2}\\cdots p_r^{\\beta_r}\\]
\n\n\n\nThe formula we use for $\\phi(n)$ is given by:
\n\n\n\n\\[\\phi(n) = (p_1^{\\beta_1} - p_1^{\\beta_1-1})\\times (p_2^{\\beta_2} - p_2^{\\beta_2-1})\\times\\cdots \\times (p_r^{\\beta_r} - p_r^{\\beta_r-1})\\]
\n\n\n\nWe use the following table:
\n\n\n\n\n\n| $p$ | $p^\\alpha$ | $\\phi(p^\\alpha)$ | Value |
|---|
\n\n| $p=2$ | $2^1$ | $2^1-2^0$ | $1$ |
|---|
\n\n | $2^2$ | $2^2-2^1$ | $2$ |
|---|
\n\n | $2^3$ | $2^3-2^2$ | $4$ |
|---|
\n\n | $2^4$ | $2^4-2^3$ | $8$ |
|---|
\n\n | $2^5$ | $2^5-2^4$ | $16$ |
|---|
\n\n | too big! | | |
|---|
\n\n| $p=3$ | $3^1$ | $3^1-3^0$ | $2$ |
|---|
\n\n | $3^2$ | $3^2-3^1$ | $6$ |
|---|
\n\n | $3^3$ | $3^3-3^2$ | $18$ |
|---|
\n\n | too big! | | |
|---|
\n\n| $p=5$ | $5^1$ | $5^1-5^0$ | $5$ |
|---|
\n\n | $5^2$ | $5^2-5^1$ | $20$ |
|---|
\n\n | too big! | | |
|---|
\n\n| $p=7$ | $7^1$ | $7^1-7^0$ | $6$ |
|---|
\n\n | $7^2$ | $7^2-7^1$ | $42$ |
|---|
\n\n | too big! | | |
|---|
\n\n
\n\n\n\nSome useful facts:
\n\n\n\nFact 1. If $m \\neq 1$ is odd then no solution as $\\phi(p^{\\alpha})$ is even (except for $\\phi(2)=1)$.
\n\n\n\nFact 2. If $m+1$ is a prime number then $n=m+1$ is a solution as $\\phi(p)=p-1$ for a prime $p$.
\n\n\n\nFact 3. If $n=n_1$ is a solution, i.e. $ \\phi(n_1)=m$, and $n_1$ is odd then $n=2n_1$ is also a solution.
\n\n\n\nThis follows as since $2,\\;n_1$ are coprime then $\\phi(2n_1)=\\phi(2)\\times \\phi(n_1)=1 \\times \\phi(n_1)= m$
\n\n\n\nStep 1
\n\n\n\nIf $m\\neq 1$ is odd then stop. No solution.
\n\n\n\nIf $m$ even next step.
\n\n\n\nStep 2.
\n\n\n\nIs $m+1$ a prime number?
\n\n\n\nYes: \tThen $n=m+1$ is a solution as is $n=2(m+1)$. This follows from Facts 2 and 3 above. Go to Step 3.
\n\n\n\nNo: \tGo to Step 3
\n\n\n\nStep 3.
\n\n\n\nCan you find $m$ as a value in the table equal to $\\phi(p^\\alpha)$?
\n\n\n\nYes: \tThen $n=p^\\alpha$ is a solution.
\n\n\n\nIf $p$ is an odd prime then by Fact 3. above $n=2p^\\alpha$ is also a solution.
\n\n\n\n(If $p=2$ then $\\phi(2^{\\alpha+1})=2\\times\\phi(2^{\\alpha})=2\\times m $ so not a solution).
\n\n\n\nGo to Step 4.
\n\n\n\nNo:\t\tGo to Step 4.
\n\n\n\nStep 4. (Look at factorizations of $m$)
\n\n\n\nIn the examples you are given, you will find that they are of the form $m=2\\times s$, $s$ odd or $m= 4 \\times s$, $s$ odd.
\n\n\n\nThis means you need only look at factorizations of the form $m = 2 \\times m_1$ which simplifies the calculations.
\n\n\n\nFactorize $m=2 \\times m_1$. The idea is now to find $n_1$ so that $\\phi(n_1)=m_1$.
\n\n\n\nNote that $\\phi(2^2)=\\phi(3^1)=2$.
\n\n\n\nIt follows that if we can find $n_1$ we will have found at least one more solution depending on whether or not $n_1$ is coprime to $2$ and/or $3$, and we will find 2 more\tif coprime to both.
\n\n\n\nSo go back through Steps 1 and 3 for $m_1$.
\n\n\n\nSuppose you have found one or more $n_1$ so that $\\phi(n_1)=m_1$, then:
\n\n\n\nIf $2$ and $n_1$ are coprime then we have $\\phi(2^2 \\times n_1)=\\phi(2^2)\\times \\phi(n_1)=2\\times m_1=m$
\n\n\n\nHence $n=2^2n_1$ is a solution
\n\n\n\nIf $3$ and $n_1$ are coprime and we have $\\phi(3^1 \\times n_1)=\\phi(3^1)\\times \\phi(n_1)=2\\times m_1=m$
\n\n\n\nHence $n=3n_1$ is a solution.
\n\n\n\nLast Step:
\n\n\n\nYou will have assembled a list of solutions.
\n\n\n\nIf you have any which are odd then by Fact 3 above you can multiply it by $2$ to get another solution (if you do not have it already).
\n\n\n\nExample
\n\n\n\nFind $n$ such that $\\phi(n)=20$.
\n\n\n\nSteps 1 and 2: Note that $20$ is even, but that $20+1=21$ is not a prime. So straight to Step 3.
\n\n\n\nStep 3: We can find $\\phi(5^2) = 20$ from the table. Hence $n=25$ is a solution, which is odd and so $n=2\\times 25=50$ is also a solution.
\n\n\n\nStep 4: $20=2 \\times 10$ and so we look for solutions $n_1$ of $\\phi(n_1)=10$. Once we have found these we examine them to see if
\n\n\n\n$n=2^2 \\times n_1$ and $n=3^1 \\times n_1$ could also be solutions.
\n\n\n\nAs $10+1=11$ is prime we have $n_1=11$ is an solution as is $n_1=22$ as $11$ is odd.
\n\n\n\nThere are no other solutions for $\\phi(n_1)=10$ as $10$ does not appear on the table values and only factorization is
\n\n\n\n$10=2 \\times 5$ and $5$ does not appear on the table.
\n\n\n\nSo from this Step we have potential solutions given by
\n\n\n\n$n=2^2 \\times 11 =44,\\;\\; n= 3^1 \\times 11=33$
and
$n=2^2 \\times 22=88,\\;\\;n=3^1 \\times 22 = 66$
\n\n\n\nThe only one of these four not a solution is $88$ as $2^2$ and $22$ are not coprime, the others are fine.
\n\n\n\nSo bringing the solutions for $n$ together we have five:
\n\n\n\n\\[25,\\;\\; 50,\\;\\; 44,\\;\\; 33,\\;\\; 66\\]
\n\n", "scripts": {}, "type": "information", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "stepsPenalty": 0}], "statement": "", "tags": ["checked2015", "coprime", "euler totient function", "Euler totient function", "factor", "Factorisation", "factorisation", "factorization", "Number theory", "number theory", "phi(n)", "prime", "prime decomposition", "prime factorisation"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Given $m \\in \\mathbb{N}$, find all $n \\in \\mathbb{N}$ such that $\\phi(n)=m$ and enter the largest and second largest if they exist.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n\n\n{primess}
\n\n\n\n{valmess}
\n\n\n\n{factmess}
\n\n\n\n{solmess}
\n\n", "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}