If you use the extended Euclidean Algorithm as shown in the course then you will obtain the required values of $x$ and $y$.
\n');\nfunction disp(s){\n return Numbas.jme.display.exprToLaTeX(s,['unitFactor','zeroFactor','zeroTerm','basic'],scope);\n}\n\nfunction mdescextgcd(a,b,c1,c2,d1,d2){\n table.append('| $\\\\var{'+a+'}$ | $\\\\var{'+b+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |
');\n if((a%b==0) || (b%a==0)) {\n return;\n }\n else {\n if(a$\\\\var{'+a+'}$ | $\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$ | ');\n mdescextgcd(a,b%a,c1,c2,d1-fl*c1,d2-fl*c2);\n }\n else {\n var fl1=Math.floor(a/b);\n table.append('| $\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$ | $\\\\var{'+b+'}$ | $'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |
');\n mdescextgcd(a%b,b,c1-fl1*d1,c2-fl1*d2,d1,d2);}\n }\n}\nmdescextgcd(a,b,c1,c2,d1,d2);\n\nreturn table;\n", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "Let $h=(\\var{sa},\\var{sb})$.
", "tags": ["checked2015"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": ".extended-gcd td:nth-child(2) {\n border-right: 1px solid black;\n}\n.extended-gcd td {\n padding-left: 1em;\n padding-right: 1em;\n}\n.extended-gcd tr.state:not(:last-child) td {\n border-bottom: 1px dashed #ccc;\n}", "js": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Find gcd g of two positive integers x, y and also find integers a, b such that ax+by=g with prescribed intervals for a and b.
"}, "advice": "We use the extended Euclidean Algorithm to get:
\n{mdescextGCD(sa,sb,1,0,0,1)}
\nHence $h=\\var{hcf}$ and we have
\n\\[ x= \\var{csa}, \\quad y=\\var{csb}\\]
\nThat is,
\n\\[ \\simplify[!basic]{{sa}*{csa}+{sb}*{csb} = {hcf}} \\]
"}, {"name": "Factorise four numbers", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "parts": [{"customName": "", "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "prompt": "$\\var{numbers[0]} =$ [[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{numbers[0]}", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "checkingType": "absdiff", "vsetRangePoints": 5, "failureRate": 1, "customName": "", "checkVariableNames": false, "unitTests": [], "valuegenerators": [], "vsetRange": [0, 1], "showFeedbackIcon": true, "scripts": {"constructor": {"script": "question.createFactorisePart(this);", "order": "after"}, "mark": {"script": "question.markFactorisePart(this);", "order": "instead"}}, "extendBaseMarkingAlgorithm": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "useCustomName": false, "checkingAccuracy": 0.001, "showPreview": true, "variableReplacements": [], "marks": "0.25"}], "type": "gapfill", "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customName": "", "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "prompt": "$\\var{numbers[1]} =$ [[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{numbers[1]}", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "checkingType": "absdiff", "vsetRangePoints": 5, "failureRate": 1, "customName": "", "checkVariableNames": false, "unitTests": [], "valuegenerators": [], "vsetRange": [0, 1], "showFeedbackIcon": true, "scripts": {"constructor": {"script": "question.createFactorisePart(this);", "order": "after"}, "mark": {"script": "question.markFactorisePart(this);", "order": "instead"}}, "extendBaseMarkingAlgorithm": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "useCustomName": false, "checkingAccuracy": 0.001, "showPreview": true, "variableReplacements": [], "marks": "0.25"}], "type": "gapfill", "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customName": "", "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "prompt": "$\\var{numbers[2]} =$ [[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{numbers[2]}", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "checkingType": "absdiff", "vsetRangePoints": 5, "failureRate": 1, "customName": "", "checkVariableNames": false, "unitTests": [], "valuegenerators": [], "vsetRange": [0, 1], "showFeedbackIcon": true, "scripts": {"constructor": {"script": "question.createFactorisePart(this);", "order": "after"}, "mark": {"script": "question.markFactorisePart(this);", "order": "instead"}}, "extendBaseMarkingAlgorithm": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "useCustomName": false, "checkingAccuracy": 0.001, "showPreview": true, "variableReplacements": [], "marks": "0.25"}], "type": "gapfill", "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"customName": "", "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "prompt": "$\\var{numbers[3]} =$ [[0]]
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"answer": "{numbers[3]}", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "checkingType": "absdiff", "vsetRangePoints": 5, "failureRate": 1, "customName": "", "checkVariableNames": false, "unitTests": [], "valuegenerators": [], "vsetRange": [0, 1], "showFeedbackIcon": true, "scripts": {"constructor": {"script": "question.createFactorisePart(this);", "order": "after"}, "mark": {"script": "question.markFactorisePart(this);", "order": "instead"}}, "extendBaseMarkingAlgorithm": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "useCustomName": false, "checkingAccuracy": 0.001, "showPreview": true, "variableReplacements": [], "marks": "0.25"}], "type": "gapfill", "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "sortAnswers": false}], "variables": {"numbers": {"group": "Ungrouped variables", "templateType": "anything", "definition": "shuffle(list(1900..2015))[0..4]", "description": "", "name": "numbers"}}, "ungrouped_variables": ["numbers"], "functions": {"list": {"type": "number", "language": "javascript", "definition": "return r.slice(3);", "parameters": [["r", "range"]]}}, "variable_groups": [], "preamble": {"css": "", "js": "question.createFactorisePart = function(p) {\n var n = parseInt(p.settings.correctAnswer);\n var factors = Numbas.math.factorise(n);\n\n p.settings.correctAnswer = p.display.correctAnswer = factors.map(function(pow,i){\n if(pow==1) {\n return Numbas.math.primes[i];\n } else if(pow>0){\n return Numbas.math.primes[i]+'^'+pow;\n } else {\n return '';\n }\n }).filter(function(x){return x}).join(' * ');\n\n p.display.correctAnswerLaTeX = factors.map(function(pow,i){\n if(pow==1) {\n return Numbas.math.primes[i];\n } else if(pow>0){\n return Numbas.math.primes[i]+'^{'+pow+'}';\n } else {\n return '';\n }\n }).filter(function(x){return x}).join(' \\\\times ');\n}\n\nquestion.markFactorisePart = function(p) {\n var m = Numbas.jme.display.matchExpression('m_all(m_any(m_number,m_number^m_number));factors*??',p.studentAnswer,true);\n\n function onlyPrimes(tree) {\n var number;\n if(tree.tok.type=='op' && tree.tok.name=='*') {\n return onlyPrimes(tree.args[0]) && onlyPrimes(tree.args[1]);\n } else if(tree.tok.type=='op' && tree.tok.name=='^') {\n number = tree.args[0].tok.value;\n } else {\n number = tree.tok.value;\n }\n return Numbas.math.primes.contains(number);\n }\n\n if(!onlyPrimes(m.factors)) {\n p.setCredit(0,'Your answer is not completely factorised.');\n return ;\n }\n Numbas.parts.JMEPart.prototype.mark.apply(p);\n}"}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "Factorize completely the following numbers.
\nFor example if you are factorizing $1998$ then we have $1998 = 2 \\times 3^3 \\times 37$ and you would enter 2 * 3^3 * 37.
", "tags": ["checked2015"], "rulesets": {}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Pick four numbers from $1900\\dots 2015$ and ask the student to factorise them.
\nCustom marking scripts make sure the student has entered a complete factorisation.
"}, "advice": ""}, {"name": "Factorise numbers into products of prime powers", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"e2": {"group": "Ungrouped variables", "templateType": "anything", "definition": "if(e1>1,0,2)", "description": "", "name": "e2"}, "lgp": {"group": "Ungrouped variables", "templateType": "anything", "definition": "[59,61,67,73,79]", "description": "", "name": "lgp"}, "e1": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2,3)", "description": "", "name": "e1"}, "p1": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(sgp)", "description": "", "name": "p1"}, "e3": {"group": "Ungrouped variables", "templateType": "anything", "definition": "1", "description": "", "name": "e3"}, "p3": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(mgp)", "description": "", "name": "p3"}, "e5": {"group": "Ungrouped variables", "templateType": "anything", "definition": "1", "description": "", "name": "e5"}, "p5": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(lgp)", "description": "", "name": "p5"}, "sgp": {"group": "Ungrouped variables", "templateType": "anything", "definition": "[2,2,2,3,3,3,5,5,5,7,7,7,11,11,13]", "description": "", "name": "sgp"}, "p2": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(sgp)", "description": "", "name": "p2"}, "mgp": {"group": "Ungrouped variables", "templateType": "anything", "definition": "[17,19,23,29,31,37,41,43,47]", "description": "", "name": "mgp"}, "ntbf": {"group": "Ungrouped variables", "templateType": "anything", "definition": "p1^e1 * p2^e2 * p3^e3 * p5^e5", "description": "", "name": "ntbf"}}, "ungrouped_variables": ["p2", "p3", "p1", "p5", "sgp", "ntbf", "mgp", "e5", "lgp", "e1", "e3", "e2"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "showQuestionGroupNames": false, "functions": {}, "parts": [{"scripts": {}, "gaps": [{"answer": "{p1^e1*p2^e2*p3^e3*p5^e5}", "musthave": {"message": "Split into factors, each factor a power of a prime number and include the multiplication sign * between the factors
", "showStrings": false, "partialCredit": 0, "strings": ["*", "^"]}, "vsetrange": [0, 1], "scripts": {"constructor": {"script": "question.createFactorisePart(this);", "order": "after"}, "mark": {"script": "question.markFactorisePart(this);", "order": "instead"}}, "answersimplification": "unitPower,zeroPower,unitFactor", "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "checkingaccuracy": 0.001, "minlength": {"length": 7, "message": "", "partialCredit": 0}, "type": "jme", "checkvariablenames": false, "showCorrectAnswer": true, "marks": 3, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "\n\n\nFactorize completely $\\var{ntbf}$.
\n\n\n\nInput your answer in the form p^r * q^s * ... where $p, q, \\dots$ are distinct primes and $r, s, \\dots$ are their powers.
\n\n\n\n$\\var{ntbf}=\\;\\;$[[0]]
\n\n\n\n(There is a Maple function $\\mathrm{ifactor}(n)$ which factorizes integers.)
\n\n", "showCorrectAnswer": true, "marks": 0}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "", "tags": ["Arithmetic", "arithmetic", "checked2015", "factorisation", "factorization", "integers", "MAS3214", "number theory", "prime factorisation", "prime factorization", "prime factors", "prime numbers", "prime powers"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": "question.createFactorisePart = function(p) {\n var n = parseInt(p.settings.correctAnswer);\n var factors = Numbas.math.factorise(n);\n\n p.settings.correctAnswer = p.display.correctAnswer = factors.map(function(pow,i){\n if(pow==1) {\n return Numbas.math.primes[i];\n } else if(pow>0){\n return Numbas.math.primes[i]+'^'+pow;\n } else {\n return '';\n }\n }).filter(function(x){return x}).join(' * ');\n\n p.display.correctAnswerLaTeX = factors.map(function(pow,i){\n if(pow==1) {\n return Numbas.math.primes[i];\n } else if(pow>0){\n return Numbas.math.primes[i]+'^{'+pow+'}';\n } else {\n return '';\n }\n }).filter(function(x){return x}).join(' \\\\times ');\n}\n\nquestion.markFactorisePart = function(p) {\n var m = Numbas.jme.display.matchExpression('m_all(m_any(m_number,m_number^m_number));factors*??',p.studentAnswer,true);\n\n function onlyPrimes(tree) {\n var number;\n if(tree.tok.type=='op' && tree.tok.name=='*') {\n return onlyPrimes(tree.args[0]) && onlyPrimes(tree.args[1]);\n } else if(tree.tok.type=='op' && tree.tok.name=='^') {\n number = tree.args[0].tok.value;\n } else {\n number = tree.tok.value;\n }\n return Numbas.math.primes.contains(number);\n }\n\n if(!onlyPrimes(m.factors)) {\n p.setCredit(0,'Your answer is not completely factorised.');\n return ;\n }\n JMEPart.prototype.mark.apply(p);\n}"}, "type": "question", "metadata": {"notes": "16/08/2012:
\n Added tags.
\n Added description.
\n No advice given.
", "licence": "Creative Commons Attribution 4.0 International", "description": "Factorising 5 to 7 digit numbers into a product of prime powers.
\nUses the marking algorithms from question 1 of this CBA
"}, "advice": "\n\n\n\n\n"}, {"name": "Find all solutions of a quadratic in Z_n, given one", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"q": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(p=11,2,random(2,3))", "description": "", "name": "q"}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(a+p-m*q>=0,mod(a+p-m*q,n),n+mod(a+p-m*q,n))", "description": "", "name": "b"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a+b,n)", "description": "", "name": "c"}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(a-m*q>=0,mod(a-m*q,n),n+mod(a-m*q,n))", "description": "", "name": "b1"}, "b2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "max(a1,b1)", "description": "", "name": "b2"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a+p,n)", "description": "", "name": "a1"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(ar=p or ar=q, ar+1, ar)", "description": "", "name": "a"}, "m1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..2)", "description": "", "name": "m1"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sort([b,a2,b2])", "description": "", "name": "ans"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "p*q", "description": "", "name": "n"}, "ar": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(round(n/2)..n-1)", "description": "", "name": "ar"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a*b,n)", "description": "", "name": "d"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5,7,11)", "description": "", "name": "p"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "min(a1,b1)", "description": "", "name": "a2"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(mod(a+p-m1*q,n)=0,m1+1,m1)", "description": "", "name": "m"}}, "ungrouped_variables": ["a", "a1", "a2", "ans", "ar", "b", "b1", "b2", "c", "d", "m", "m1", "n", "p", "q"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans[0]}", "minValue": "{ans[0]}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans[1]}", "minValue": "{ans[1]}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans[2]}", "minValue": "{ans[2]}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "prompt": "Enter the three other roots in increasing order below:
\n $x_2 = \\;$ [[0]]
\n $x_3 = \\;$ [[1]]
\n $x_4 = \\;$ [[2]]
", "showCorrectAnswer": true, "marks": 0}], "statement": "$x = x_1 = \\var{a}$ is a solution of this quadratic equation in $\\mathbb{Z}_{\\var{n}}$:
\n\\[\\simplify[std]{x^2 -{c}x+{d} = 0}\\]
\nThere are three other solutions $x_2$, $x_3$, $x_4$ in $\\mathbb{Z}_{\\var{n}}$ of this quadratic equation, where $0\\le x_2 \\lt x_3 \\lt x_4 \\le \\var{n-1}$ .
", "tags": ["checked2015", "MAS3214"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Given one solution of the quadratic equation in $\\mathbb{Z}_n$ where $n=pq$ is a product of two primes find the other 3 solutions.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "Putting $x=\\var{a}$ gives:
\n\\begin{align}
\\simplify[std]{x^2 -{c}x+{d}} & = \\simplify[std]{{a}^2-{c}*{a} + {d}} \\\\
&= \\simplify[std]{{a^2-c*a+d}} \\\\
& \\equiv 0 \\bmod{\\var{n}}
\\end{align}
\nHence $x=\\var{a}$ is a solution of the quadratic equation in $\\mathbb{Z}_{\\var{n}}$.
\nWe can use this to factorize the quadratic equation, giving $b$, which will also be a solution, such that:
\n\\[ \\simplify[std]{x^2 -{c}x+{d}} = (x-\\var{a})(x-b) \\]
\nWe see that $b$ has to satisfy:
\n\\begin{align}
\\var{a} b & \\equiv \\var{d} \\bmod{\\var{n}}, \\\\
\\var{a} + b & \\equiv \\var{c} \\bmod{\\var{n}}.
\\end{align}
\nBy rearranging the second equation, we see that $b = \\simplify[std]{{c}-{a}} =\\var{c-a} \\equiv \\var{b} \\bmod{\\var{n}}$ satisfies the second equation. You can check that it also satisfies the first equation.
\nSo $\\simplify[std]{x^2 -{c}x+{d} = (x-{a})(x-{b})}$ expresses the quadratic as the product of two factors and we have found another solution $x=\\var{b}$.
\nBut there are two other roots.
\nThe strategy is to try values of $x$ such that substituting a value of $x$ in one of the factors gives a multiple of $\\var{p}$, and substituting the same value into the other factor gives a multiple of $\\var{q}$.
\nTogether they give a multiple of $\\var{n} = \\var{p} \\times \\var{q} = 0 \\bmod{\\var{n}}$ and so will give a solution in $\\mathbb{Z}_{\\var{n}}$.
\nWe see that trying $x = \\var{a1}$ gives
\n\\[ \\simplify[std]{(x-{a})(x-{b}) = ({a1}-{a})({a1}-{b}) = {a1-a}*{a1-b} = {(a1-a)(a1-b)}} \\equiv 0 \\bmod{\\var{n}}. \\]
\nFor the other we see that trying $x = \\var{b1}$ gives
\n\\[ \\simplify[std]{(x-{a})(x-{b}) = ({b1}-{a})({b1}-{b}) = {b1-a}*{b1-b} = {(b1-a)(b1-b)}} \\equiv 0 \\bmod{\\var{n}}. \\]
\nHence, apart from the solution $x = \\var{a}$, the other solutions are, in increasing order: $\\var{ans[0]}$, $\\var{ans[1]}$, $\\var{ans[2]}$.
\nHence $x_2 = \\var{ans[0]}$, $x_3 = \\var{ans[1]}$, $x_4 = \\var{ans[2]}$.
"}, {"name": "Perform arithmetic in Z_n", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"a5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..9)", "description": "", "name": "a5"}, "ans2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a2*b2", "description": "", "name": "ans2"}, "ans3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a3*(b3+g3)", "description": "", "name": "ans3"}, "b4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(6..9)", "description": "", "name": "b4"}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..4)", "description": "", "name": "b1"}, "b2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..5)", "description": "", "name": "b2"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "a1"}, "g5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..9)", "description": "", "name": "g5"}, "h5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..9)", "description": "", "name": "h5"}, "ans4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a4*b4", "description": "", "name": "ans4"}, "g3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..6)", "description": "", "name": "g3"}, "b5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..9)", "description": "", "name": "b5"}, "s5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a5+b5,9)", "description": "", "name": "s5"}, "a3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..6)", "description": "", "name": "a3"}, "ans1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1+b1", "description": "", "name": "ans1"}, "a4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(6..9)", "description": "", "name": "a4"}, "b3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..6)", "description": "", "name": "b3"}, "ans5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(a5+b5)*(g5+h5)", "description": "", "name": "ans5"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..5)", "description": "", "name": "a2"}, "t5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g5+h5,9)", "description": "", "name": "t5"}}, "ungrouped_variables": ["a1", "g5", "ans3", "g3", "ans1", "ans2", "t5", "ans4", "ans5", "s5", "h5", "b4", "b5", "a3", "a2", "a5", "b1", "b2", "b3", "a4"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans1,2)}", "minValue": "{mod(ans1,2)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans1,9)}", "minValue": "{mod(ans1,9)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans1,10)}", "minValue": "{mod(ans1,10)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans2,2)}", "minValue": "{mod(ans2,2)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans2,9)}", "minValue": "{mod(ans2,9)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans2,10)}", "minValue": "{mod(ans2,10)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans3,2)}", "minValue": "{mod(ans3,2)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans3,9)}", "minValue": "{mod(ans3,9)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans3,10)}", "minValue": "{mod(ans3,10)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans4,2)}", "minValue": "{mod(ans4,2)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans4,9)}", "minValue": "{mod(ans4,9)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans4,10)}", "minValue": "{mod(ans4,10)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans5,2)}", "minValue": "{mod(ans5,2)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans5,9)}", "minValue": "{mod(ans5,9)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mod(ans5,10)}", "minValue": "{mod(ans5,10)}", "correctAnswerFraction": false, "marks": 0.2, "showPrecisionHint": false}], "type": "gapfill", "prompt": "\n \n \n Perform the following calculations in $\\mathbb{Z}_{2},\\;\\;\\mathbb{Z}_{9},\\;\\;\\mathbb{Z}_{10}$.
\n \n \n \n \n \n \n \n | \n \n $\\mathbb{Z}_{2}$ | \n \n $\\mathbb{Z}_{9}$ | \n \n $\\mathbb{Z}_{10}$ | \n \n
\n \n \n \n | $\\var{a1}+\\var{b1}$ | \n \n [[0]] | \n \n [[1]] | \n \n [[2]] | \n \n
\n \n \n \n | $\\var{a2}\\times\\var{b2}$ | \n \n [[3]] | \n \n [[4]] | \n \n [[5]] | \n \n
\n \n \n \n | $\\var{a3}\\times(\\var{b3}+\\var{g3})$ | \n \n [[6]] | \n \n [[7]] | \n \n [[8]] | \n \n
\n \n \n \n | $\\var{a4}\\times\\var{b4}$ | \n \n [[9]] | \n \n [[10]] | \n \n [[11]] | \n \n
\n \n \n \n | $(\\var{a5}+\\var{b5})\\times (\\var{g5}+\\var{h5})$ | \n \n [[12]] | \n \n [[13]] | \n \n [[14]] | \n \n
\n \n
\n \n ", "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "MAS3214", "Modular arithmetic", "modular arithmetic"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "16/08/2012:
\n
Added tags.
\n Added description.
", "licence": "Creative Commons Attribution 4.0 International", "description": "Calculations in $\\mathbb{Z_n}$ for three values of $n$.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "In the the last part, working out $(\\var{a5}+\\var{b5})\\times (\\var{g5}+\\var{h5}) \\bmod{X}$, it is sometimes easier to work out $(\\var{a5}+\\var{b5}) \\bmod{X}$ and $(\\var{g5}+\\var{h5}) \\bmod{X}$ separately, giving two numbers in the range $[0 \\dots X-1]$, and then to multiply them together.
\nFor example, working $\\bmod{9}$ we have:
\n\\begin{align}
\\var{a5}+\\var{b5}&\\equiv \\var{mod(a5+b5,9)} \\bmod{9}, \\\\
\\var{g5}+\\var{h5}&\\equiv \\var{mod(g5+h5,9)} \\bmod{9}. \\\\ \\\\
(\\var{a5}+\\var{b5})\\times (\\var{g5}+\\var{h5}) &\\equiv \\var{s5} \\times \\var{t5} \\bmod{9} \\\\
&\\equiv \\var{mod(ans5,9)} \\bmod{9}
\\end{align}
"}, {"name": "Simplify integers and rationals in Z_n", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"s1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1,-1)", "name": "s1", "description": ""}, "b3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2,4,8,13,16,17)", "name": "b3", "description": ""}, "ans1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*b1 + c1*d1 - f1", "name": "ans1", "description": ""}, "f1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..9)", "name": "f1", "description": ""}, "inv5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(rinv5, 5)", "name": "inv5", "description": ""}, "ans13": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,3)", "name": "ans13", "description": ""}, "p3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(3,b3),min(3,b3))", "name": "p3", "description": ""}, "inv11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(rinv11, 11)", "name": "inv11", "description": ""}, "s2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1=1,-1,1)", "name": "s2", "description": ""}, "rinv3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<3,q3,p3)", "name": "rinv3", "description": ""}, "q7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(7,b3),min(7,b3))", "name": "q7", "description": ""}, "ans15": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,5)", "name": "ans15", "description": ""}, "inv3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos( rinv3, 3)", "name": "inv3", "description": ""}, "rinv7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<7,q7,p7)", "name": "rinv7", "description": ""}, "c3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(17,19,23,29,31,37,41,43,47)", "name": "c3", "description": ""}, "q5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(5,b3),min(5,b3))", "name": "q5", "description": ""}, "minv3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv3,3)", "name": "minv3", "description": ""}, "ans111": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,11)", "name": "ans111", "description": ""}, "minv7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv7,7)", "name": "minv7", "description": ""}, "ans211": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,11)", "name": "ans211", "description": ""}, "minv5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv5,5)", "name": "minv5", "description": ""}, "ans27": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,7)", "name": "ans27", "description": ""}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "s2*random(3..4)", "name": "b1", "description": ""}, "q11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(11,b3),min(11,b3))", "name": "q11", "description": ""}, "ans23": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,3)", "name": "ans23", "description": ""}, "p7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(7,b3),min(7,b3))", "name": "p7", "description": ""}, "d1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(4..9)", "name": "d1", "description": ""}, "p5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(5,b3),min(5,b3))", "name": "p5", "description": ""}, "p11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(11,b3),min(11,b3))", "name": "p11", "description": ""}, "q3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(3,b3),min(3,b3))", "name": "q3", "description": ""}, "inv7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(rinv7, 7)", "name": "inv7", "description": ""}, "c1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(4..9)", "name": "c1", "description": ""}, "rinv11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<11,q11,p11)", "name": "rinv11", "description": ""}, "rinv5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<5,q5,p5)", "name": "rinv5", "description": ""}, "ans17": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,7)", "name": "ans17", "description": ""}, "ans25": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,5)", "name": "ans25", "description": ""}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)", "name": "a2", "description": ""}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "s1*random(3..9)", "name": "a1", "description": ""}, "minv11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv11,11)", "name": "minv11", "description": ""}}, "ungrouped_variables": ["f1", "p7", "ans1", "inv11", "b1", "b3", "ans27", "ans25", "ans23", "d1", "q3", "rinv11", "q5", "ans211", "s2", "s1", "ans111", "minv11", "a1", "ans13", "a2", "q11", "ans17", "ans15", "c3", "c1", "rinv3", "rinv5", "rinv7", "p3", "q7", "p11", "inv7", "inv5", "p5", "inv3", "minv3", "minv7", "minv5"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "showQuestionGroupNames": false, "functions": {"extendedgcd1": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n1\n\n,\n\nextendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n\n)\n\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "makepos": {"type": "number", "language": "jme", "definition": "mod(a,b)", "parameters": [["a", "number"], ["b", "number"]]}}, "parts": [{"scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans13}", "maxValue": "{ans13}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans15}", "maxValue": "{ans15}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans17}", "maxValue": "{ans17}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans111}", "maxValue": "{ans111}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans23}", "maxValue": "{ans23}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans25}", "maxValue": "{ans25}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans27}", "maxValue": "{ans27}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans211}", "maxValue": "{ans211}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv3}", "maxValue": "{inv3}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv5}", "maxValue": "{inv5}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv7}", "maxValue": "{inv7}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv11}", "maxValue": "{inv11}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv3}", "maxValue": "{minv3}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv5}", "maxValue": "{minv5}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv7}", "maxValue": "{minv7}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv11}", "maxValue": "{minv11}", "marks": 0.25, "showPrecisionHint": false}], "type": "gapfill", "prompt": "
\n\n\n| | $\\mathbb{Z}_{3}$ | $\\mathbb{Z}_{5}$ | $\\mathbb{Z}_{7}$ | $\\mathbb{Z}_{11}$ |
|---|
\n\n| $\\simplify[!basic]{{a1}*{b1}+{c1}*{d1}-{f1}}$ | \n[[0]] | \n[[1]] | \n[[2]] | \n[[3]] | \n
\n\n| $\\var{a2}$ | \n[[4]] | \n[[5]] | \n[[6]] | \n[[7]] | \n
\n\n| $ \\displaystyle{ \\frac{1}{\\var{b3}} } $ | \n[[8]] | \n[[9]] | \n[[10]] | \n[[11]] | \n
\n\n| $ \\displaystyle{ \\frac{\\var{c3}}{\\var{b3}} } $ | \n[[12]] | \n[[13]] | \n[[14]] | \n[[15]] | \n
\n\n
", "showCorrectAnswer": true, "marks": 0}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "Simplify the following in each of $\\mathbb{Z}_{3}, \\; \\mathbb{Z}_{5}, \\; \\mathbb{Z}_{7}$ and $\\mathbb{Z}_{11}$.
\nFor the last two questions, recall that for a prime $p$, $\\displaystyle{\\frac{1}{b} \\bmod{p}}$ is the unique solution to $bx \\equiv 1 \\bmod{p}$.
\nYou must input all values as positive integers; negative integers are not accepted.
", "tags": ["checked2015", "MAS3214"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Express various integers and rationals mod $\\mathbb{Z}_3, \\;\\mathbb{Z}_5,\\;\\mathbb{Z}_7,\\;\\mathbb{Z}_{11}$
"}, "advice": "For the first row, it may help to simplify each of the numbers modulo the number corresponding to each column, and then perform the calculation.
\nFor example,
\n\\begin{align}
\\simplify[!basic]{{a1}*{b1}+{c1}*{d1}-{f1}} &\\equiv \\simplify[!basic]{{mod(a1,3)}*{mod(b3,3)}+{mod(c1,3)}*{mod(d1,3)}-{mod(f1,3)}} \\mod{3} \\\\
&\\equiv \\var{ans13} \\mod{3}
\\end{align}
\nIn the second row, you just have to work out the remainder when dividing $\\var{a2}$ by each of $3$, $5$, $7$ and $11$.
\nIn the third row we have to find the inverse of $\\var{b3}$ in each of $\\mathbb{Z}_{3}$, $\\mathbb{Z}_{5}$, $\\mathbb{Z}_{7}$ and $\\mathbb{Z}_{11}$.
\nIt should be clear to you that $\\var{b3}$ is coprime to each of $3$, $5$, $7$ and $11$, hence we can find an inverse in each of $\\mathbb{Z}_{3}$, $\\mathbb{Z}_{5}$, $\\mathbb{Z}_{7}$ and $\\mathbb{Z}_{11}$.
\nYou can do this in $\\mathbb{Z}_{3}$ by finding $x$ such that $\\var{b3}x \\equiv 1 \\bmod{3}$, similarly for $5$, $7$, $11$.
\nYou can do this by trying values to find one that works; this is easy for $\\mathbb{Z}_{3}$ since there are only two cases to check, and you will find that
\n$b = \\var{inv3}$ satisfies $\\var{inv3} \\times \\var{b3} = \\var{inv3*b3} \\equiv 1 \\bmod{3}.$
\nInverse in $\\mathbb{Z}_{5}$
\nIf you cannot immediately find an inverse in $\\mathbb{Z}_{5}$, you can use the Euclidean algorithm to find $a$ and $b$ such that
\n\\[\\var{b3}b +5a = \\operatorname{gcd}(\\var{b3},5) = 1\\]
\nas $\\var{b3}$ and $5$ are coprime.
\nIt follows that $\\var{b3}b \\equiv 1 \\bmod{5}$, and hence $b \\bmod{5}$ is the inverse of $\\var{b3}$ in $\\mathbb{Z}_{5}$.
\nUsing the Euclidean algorithm I find that
\n\\[\\simplify[!basic]{ {max(5,b3)}*{p5} + {min(5,b3)}*{q5} = 1 }.\\]
\nHence the inverse is
\n\\[ b = \\var{rinv5} \\equiv \\var{inv5} \\bmod{5}.\\]
\nInverse in $\\mathbb{Z}_{7}$
\nOnce again if you cannot spot the solution:
\nUsing the Euclidean algorithm I find that
\n\\[\\simplify[!basic]{ {max(7,b3)}*{p7} + {min(7,b3)}*{q7} = 1 }.\\]
\nHence the inverse of $\\var{b3}$ in $\\mathbb{Z}_{7}$ is
\n\\[b = \\var{rinv7} \\equiv \\var{inv7} \\bmod{7}.\\]
\nInverse in $\\mathbb{Z}_{11}$
\nUsing the Euclidean algorithm I find that
\n\\[\\simplify[!basic]{ {max(11,b3)}*{p11} + {min(11,b3)}*{q11} = 1}. \\]
\nHence the inverse of $\\var{b3}$ in $\\mathbb{Z}_{11}$ is
\n\\[ b = \\var{rinv11} \\equiv \\var{inv11} \\bmod{11}.\\]
\nLast Question
\nThe last question's answers are found by, for example in $\\mathbb{Z}_{7}$, considering (all $\\bmod 7$)
\n\\[\\frac{\\var{c3}}{\\var{b3}} = \\var{c3} \\times \\frac{1}{\\var{b3}} \\equiv \\var{c3} \\times \\var{inv7} \\equiv \\var{c3*inv7} \\equiv \\var{minv7} \\bmod{7}.\\]
"}, {"name": "True/false statements on modular arithmetic", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Bill Foster", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/6/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variablesTest": {"condition": "", "maxRuns": 100}, "variables": {"s1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1,-1)", "name": "s1", "description": ""}, "d3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..8)", "name": "d3", "description": ""}, "b3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2,4,8,13,16,17)", "name": "b3", "description": ""}, "v": {"templateType": "anything", "group": "Ungrouped variables", "definition": "par[ch][2]", "name": "v", "description": ""}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1<0,u+m1+mod(a3,m1),mod(a3,m1)-m1-u)", "name": "a", "description": ""}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "q*random(1..m3-1)+mod(b3,m3)+s*m3", "name": "c", "description": ""}, "u": {"templateType": "anything", "group": "Ungrouped variables", "definition": "par[ch][0]", "name": "u", "description": ""}, "s2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1=1,-1,1)", "name": "s2", "description": ""}, "g3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g4+ v*random(1..5),m2)", "name": "g3", "description": ""}, "m3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..13)", "name": "m3", "description": ""}, "torf1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(u=0,'true','false')", "name": "torf1", "description": ""}, "noe": {"templateType": "anything", "group": "Ungrouped variables", "definition": "4-p-u-v-t", "name": "noe", "description": ""}, "c3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(17,19,23,29,31,37,41,43,47)", "name": "c3", "description": ""}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "k3-t*random(1..m2-1 except k3/t)", "name": "b", "description": ""}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "par[ch][3]", "name": "p", "description": ""}, "d4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d3+s1*random(1..3)", "name": "d4", "description": ""}, "q": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0,1)", "name": "q", "description": ""}, "ch": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..11)", "name": "ch", "description": ""}, "torf4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(v=0, 'true','false')", "name": "torf4", "description": ""}, "m4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..13)", "name": "m4", "description": ""}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..13)", "name": "m", "description": ""}, "h3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(k3^d4+p*random(1..3),m2)", "name": "h3", "description": ""}, "h4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(k3^d4,m2)", "name": "h4", "description": ""}, "g4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(k3^d3,m2)", "name": "g4", "description": ""}, "torf3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(t=0, 'true','false')", "name": "torf3", "description": ""}, "m1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..13)", "name": "m1", "description": ""}, "k3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3,m2)", "name": "k3", "description": ""}, "par": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0],[0,0,1,1],[0,1,0,1],[0,1,1,0],[1,0,0,1],[1,0,1,0],[1,1,0,0],[0,1,0,0],[1,0,0,0]]", "name": "par", "description": ""}, "m2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(m1=m,m+1,m)", "name": "m2", "description": ""}, "torf2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(q=0, 'true','false')", "name": "torf2", "description": ""}, "s": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-2,-1,2,3)", "name": "s", "description": ""}, "a3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "s1*random(19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)", "name": "a3", "description": ""}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "par[ch][1]", "name": "t", "description": ""}, "torf5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(p=0, 'true','false')", "name": "torf5", "description": ""}}, "ungrouped_variables": ["a", "a3", "b", "b3", "c", "c3", "ch", "d3", "d4", "g3", "g4", "h3", "h4", "k3", "m", "m1", "m2", "m3", "m4", "noe", "p", "par", "q", "s", "s1", "s2", "t", "torf1", "torf2", "torf3", "torf4", "torf5", "u", "v"], "variable_groups": [], "functions": {}, "parts": [{"layout": {"type": "all", "expression": ""}, "displayType": "radiogroup", "showCellAnswerState": true, "prompt": "Mark each of the statements below as either true or false.
\nYou will be penalised one mark for each answer you get wrong.
\nHowever, the minimum mark you can get for this question is $0$.
", "type": "m_n_x", "maxAnswers": 0, "shuffleChoices": true, "warningType": "none", "minAnswers": 0, "minMarks": 0, "shuffleAnswers": false, "variableReplacements": [], "showCorrectAnswer": true, "choices": ["$\\var{a3} \\equiv \\var{a} \\pmod{\\var{m1}}$", "$\\var{c3} \\equiv \\var{b} \\pmod{\\var{m2}}$", "$\\var{b3} \\equiv \\var{c} \\pmod{\\var{m3}}$", "$\\;\\;\\;\\var{c3}^{\\var{d3}} \\equiv \\var{g3} \\pmod{\\var{m2}}$", "$\\var{c3}^{\\var{d4}} \\equiv \\var{h3} \\pmod{\\var{m2}}$"], "extendBaseMarkingAlgorithm": true, "matrix": [["1-2*u", "2*u-1"], ["1-2*t", "2*t-1"], ["1-2*q", "2*q-1"], ["1-2*v", "2*v-1"], ["1-2*p", "2*p-1"]], "customMarkingAlgorithm": "", "unitTests": [], "answers": ["True
", "False
"], "scripts": {}, "maxMarks": 0, "variableReplacementStrategy": "originalfirst", "marks": 0, "showFeedbackIcon": true}], "statement": "", "tags": ["checked2015"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Modular arithmetic
"}, "advice": "$\\var{a3} \\equiv \\var{a} \\pmod{\\var{m1}}$
\n
\n\\begin{align}
\\var{a3} &\\equiv \\var{a} \\pmod{\\var{m1}} \\\\
\\iff \\simplify[std]{{a3} - {a}} &\\equiv 0 \\pmod{\\var{m1}} \\\\
\\iff \\simplify[std]{{a3-a}} &\\equiv 0 \\pmod{\\var{m1}}
\\end{align}
\nSo the statement is {torf1}.
\n$\\var{c3} \\equiv \\var{b} \\pmod{\\var{m2}}$
\n
\nWe have
\n\\begin{align}
&& \\var{c3} &\\equiv \\var{b} \\pmod{\\var{m2}} \\\\
\\iff && \\simplify[std]{{c3} - {b}} &\\equiv 0 \\pmod{\\var{m2}} \\\\
\\iff &&\\simplify[std]{{c3-b}} &\\equiv 0 \\pmod{\\var{m2}}
\\end{align}
\nSo the statement is {torf3}.
\n$\\var{b3} \\equiv \\var{c} \\pmod{\\var{m3}}$
\n
\n\\begin{align}
&& \\var{b3} &\\equiv \\var{c} \\pmod{\\var{m3}} \\\\
\\iff && \\simplify[]{{b3}-{c}} &\\equiv 0 \\pmod{\\var{m3}} \\\\
\\iff && \\simplify[std]{{b3-c}} &\\equiv 0 \\pmod{\\var{m3}}
\\end{align}
\nWhich is {torf2}.
\n$\\var{c3}^{\\var{d3}} \\equiv \\var{g3} \\pmod{\\var{m2}}$
\n
\nWe have $\\var{c3} \\equiv \\var{k3} \\pmod{\\var{m2}}$.
\nHence $\\var{c3}^{\\var{d3}} \\equiv \\var{k3}^{\\var{d3}} \\equiv \\var{k3^d3} \\equiv \\var{g4} \\pmod{\\var{m2}}$.
\nSo this statement is {torf4}.
\n$\\var{c3}^{\\var{d4}} \\equiv \\var{h3} \\pmod{\\var{m2}}$
\n
\nWe have $\\var{c3} \\equiv \\var{k3} \\pmod{\\var{m2}}$
\nHence $\\var{c3}^{\\var{d4}} \\equiv \\var{k3}^{\\var{d4}}\\equiv \\var{k3^d4}\\equiv \\var{h4} \\pmod{\\var{m2}}$
\nHence this statement is {torf5}.
"}, {"name": "Solve a pair of congruences", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"s1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sd-1)", "description": "", "name": "s1"}, "r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sb-1)", "description": "", "name": "r1"}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(10..20)", "description": "", "name": "sb"}, "csc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sc,sd)", "description": "", "name": "csc"}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*sd*invd+a2*sb*invb", "description": "", "name": "pans"}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sd,sd,3,sd-1)", "description": "", "name": "sc"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(s*ansp2,sd)", "description": "", "name": "a2"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(r*ansp1,sb)", "description": "", "name": "a1"}, "sd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,sb-5,sb+5)", "description": "", "name": "sd"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(pans,sd*sb)", "description": "", "name": "ans"}, "invd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sd,sb)", "description": "", "name": "invd"}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(r1=sa,r1-1,r1)", "description": "", "name": "r"}, "temp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sd*sb", "description": "", "name": "temp"}, "csd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,sd)", "description": "", "name": "csd"}, "s": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1=sc,s1-1,s1)", "description": "", "name": "s"}, "csb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,sb)", "description": "", "name": "csb"}, "csa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sa,sb)", "description": "", "name": "csa"}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,5,sb-1)", "description": "", "name": "sa"}, "ansp2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(csc>0, mod(csc,sd),sd+mod(csc,sd))", "description": "", "name": "ansp2"}, "ansp1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(csa>0, mod(csa,sb),sb+mod(csa,sb))", "description": "", "name": "ansp1"}, "invb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sb,sd)", "description": "", "name": "invb"}}, "ungrouped_variables": ["pans", "ansp1", "sb", "r1", "temp", "csd", "s1", "csa", "csc", "csb", "a1", "s", "r", "ans", "sc", "ansp2", "sa", "invd", "invb", "a2", "sd"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"mdescext1gcd": {"type": "string", "language": "jme", "definition": "\n \n \n if(a$\\var{a}$ | $\\var{b}-\\var{floor(b/a)}\\times\\var{a}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify[std,noleadingMinus]{{d1}a+{d2}b-{floor(b/a)}*({c1}a+{c2}b)}$ | \\n'+mdescextGCD(a,mod(b,a),c1,c2,d1-floor(b/a)*c1,d2-floor(b/a)*c2,1)\n \n ,\n \n '| $\\var{a}-\\var{floor(a/b)}\\times\\var{b}$ | $\\var{b}$ | $\\simplify[std,noleadingMinus]{{c1}a+{c2}b-{floor(a/b)}*({d1}a+{d2}b)}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescextGCD(mod(a,b),b,c1-floor(a/b)*d1,c2-floor(a/b)*d2,d1,d2,1)\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 0\n \n ,\n \n extendedgcd2(b,mod(a,b))\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(p..q),p,q))", "parameters": [["a", "number"], ["b", "number"], ["p", "number"], ["q", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 1\n \n ,\n \n extendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "string", "language": "jme", "definition": "\n \n \n if (t=0, \n \n '\\n\\n\\n'+mdescextGCD(a,b,c1,c2,d1,d2,1)\n \n ,\n \n if(a|b,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n \n \n \n $\\var{a} | \\var{b}$ and so $(\\var{sa},\\var{sb})=\\var{a}$. Note that $\\simplify[std]{{c1}*{sa}+{c2}*{sb} = {a}}$\\n\\n '\n \n ,\n \n if(b|a,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n \n \n \n $\\var{b} | \\var{a}$ and so $(\\var{sa},\\var{sb})=\\var{b}$. Note that $\\simplify[std]{{d1}*{sa}+{d2}*{sb} = {b}}$\\n\\n '\n \n ,\n \n '$ x \\mod\\; n_1=a_1 \\times 1+0=a_1 \\mod\\;n_1$ as $n_2 y_2 = 1 \\mod \\;n_1,\\;\\;a_2 n_1 y_1=0\\mod\\;n_1$
\n \n \n \n $ x \\mod\\; n_2=0+a_2 \\times 1=a_2 \\mod\\;n_2$ as $n_1 y_1 = 1 \\mod \\;n_2,\\;\\;a_1 n_2 y_2=0\\mod\\;n_2$
\n \n ", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "congruences", "coprime", "euclidean algorithm", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving a pair of congruences", "solving equations", "Solving equations"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Solving a pair of congruences of the form \\[\\begin{align}x &\\equiv b_1\\;\\textrm{mod} \\;n_1\\\\x &\\equiv b_2\\;\\textrm{mod}\\;n_2 \\end{align}\\] where $n_1,\\;n_2$ are coprime.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n \n \n Since $\\var{sb}$ and $\\var{sd}$ are coprime we find by using the Extended Euclidean Algorithm that:
\n \n \n \n (You may get different values, but they should be the same as those above $\\mod\\;\\var{sd}$ and $\\mod\\;\\var{sb}$ respectively.)
\n \n \n \n So $x=\\simplify[std]{{mod(a1,sb)}* {sd} * {invd}+{mod(a2,sd)}*{sb}*{invb}}=\\var{pans}=\\var{ans} \\;\\mod\\;\\var{sb*sd}$
\n \n "}, {"name": "Solve a pair of congruences", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"s1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sd-1)", "description": "", "name": "s1"}, "r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sb-1)", "description": "", "name": "r1"}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(10..20)", "description": "", "name": "sb"}, "csc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sc,sd)", "description": "", "name": "csc"}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*sd*invd+a2*sb*invb", "description": "", "name": "pans"}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sd,sd,3,sd-1)", "description": "", "name": "sc"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(s*ansp2,sd)", "description": "", "name": "a2"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(r*ansp1,sb)", "description": "", "name": "a1"}, "sd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,sb-5,sb+5)", "description": "", "name": "sd"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(pans,sd*sb)", "description": "", "name": "ans"}, "invd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sd,sb)", "description": "", "name": "invd"}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(r1=sa,r1-1,r1)", "description": "", "name": "r"}, "temp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sd*sb", "description": "", "name": "temp"}, "csd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,sd)", "description": "", "name": "csd"}, "s": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1=sc,s1-1,s1)", "description": "", "name": "s"}, "csb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,sb)", "description": "", "name": "csb"}, "csa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sa,sb)", "description": "", "name": "csa"}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,5,sb-1)", "description": "", "name": "sa"}, "ansp2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(csc>0, mod(csc,sd),sd+mod(csc,sd))", "description": "", "name": "ansp2"}, "ansp1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(csa>0, mod(csa,sb),sb+mod(csa,sb))", "description": "", "name": "ansp1"}, "invb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sb,sd)", "description": "", "name": "invb"}}, "ungrouped_variables": ["pans", "ansp1", "sb", "r1", "temp", "csd", "s1", "csa", "csc", "csb", "a1", "s", "r", "ans", "sc", "ansp2", "sa", "invd", "invb", "a2", "sd"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"mdescext1gcd": {"type": "string", "language": "jme", "definition": "\n \n \n if(a$\\var{a}$ | $\\var{b}-\\var{floor(b/a)}\\times\\var{a}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify[std,noleadingMinus]{{d1}a+{d2}b-{floor(b/a)}*({c1}a+{c2}b)}$ | \\n'+mdescextGCD(a,mod(b,a),c1,c2,d1-floor(b/a)*c1,d2-floor(b/a)*c2,1)\n \n ,\n \n '| $\\var{a}-\\var{floor(a/b)}\\times\\var{b}$ | $\\var{b}$ | $\\simplify[std,noleadingMinus]{{c1}a+{c2}b-{floor(a/b)}*({d1}a+{d2}b)}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescextGCD(mod(a,b),b,c1-floor(a/b)*d1,c2-floor(a/b)*d2,d1,d2,1)\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 0\n \n ,\n \n extendedgcd2(b,mod(a,b))\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(p..q),p,q))", "parameters": [["a", "number"], ["b", "number"], ["p", "number"], ["q", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 1\n \n ,\n \n extendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "string", "language": "jme", "definition": "\n \n \n if (t=0, \n \n '\\n\\n\\n'+mdescextGCD(a,b,c1,c2,d1,d2,1)\n \n ,\n \n if(a|b,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n \n \n \n $\\var{a} | \\var{b}$ and so $(\\var{sa},\\var{sb})=\\var{a}$. Note that $\\simplify[std]{{c1}*{sa}+{c2}*{sb} = {a}}$\\n\\n '\n \n ,\n \n if(b|a,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n \n \n \n $\\var{b} | \\var{a}$ and so $(\\var{sa},\\var{sb})=\\var{b}$. Note that $\\simplify[std]{{d1}*{sa}+{d2}*{sb} = {b}}$\\n\\n '\n \n ,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescext1GCD(a,b,c1,c2,d1,d2)\n \n )\n \n )\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"], ["t", "number"]]}}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans}", "minValue": "{ans}", "correctAnswerFraction": false, "marks": 4, "showPrecisionHint": false}], "type": "gapfill", "prompt": "\n \n \n Solve the equations:
\\[\\begin{eqnarray*}\n \n \\var{sa}x\\;&\\equiv&\\;\\var{r}\\;\\mod\\;\\var{sb}\\\\\n \n \\\\\n \n \\var{sc}x\\;&\\equiv&\\;\\var{s}\\;\\mod\\;\\var{sd}\n \n \\end{eqnarray*}\n \n \\]
$x=\\;\\;$ [[0]]
\n \n \n \n Your value of $x$ should satisfy $0 \\leq x \\lt \\var{sb*sd}$
\n \n ", "steps": [{"type": "information", "prompt": "If we have two simultaneous congruences:
\\[\\begin{eqnarray*} c_1x\\;&\\equiv&\\;b_1\\;&\\mod&\\;n_1\\\\ \\\\ c_2x\\;&\\equiv&\\;b_2\\;&\\mod&\\;n_2\\\\ \\end{eqnarray*} \\]
where $\\operatorname{gcd}(c_1,n_1)=1$ and $\\operatorname{gcd}(c_2,n_2)=1$
\nThen we can find the inverse $d_1$ of $c_1$ in $\\mathbb{Z}_{n_1}$ and the inverse $d_2$ of $c_2$ in $\\mathbb{Z}_{n_2}$ using the Extended Euclidean Algorithm or by inspection.
\nMultiplying both sides of the first equation by $d_1$ and multiplying both sides of the second equation by $d_2$ gives the equations in the form:
\n\\[\\begin{eqnarray*} x\\;&\\equiv&\\;a_1\\;&\\mod&\\;n_1\\\\ \\\\ x\\;&\\equiv&\\;a_2\\;&\\mod&\\;n_2\\\\ \\end{eqnarray*} \\]
\nSince $n_1$ and $n_2$ are coprime there is a simple formula to find a solution $\\mod\\;n$ where $n=n_1n_2$
\nThis is given by:
\\[x=a_1 n_2 y_2+a_2 n_1 y_1 \\mod\\;n\\]
where $y_2 = n_2^{-1} \\mod\\;n_1$ and $y_1= n_1^{-1} \\mod\\;n_2$.
\nThis works as we have:
\n$ x \\mod\\; n_1=a_1 \\times 1+0=a_1 \\mod\\;n_1$ as $n_2 y_2 = 1 \\mod \\;n_1,\\;\\;a_2 n_1 y_1=0\\mod\\;n_1$
\n$ x \\mod\\; n_2=0+a_2 \\times 1=a_2 \\mod\\;n_2$ as $n_1 y_1 = 1 \\mod \\;n_2,\\;\\;a_1 n_2 y_2=0\\mod\\;n_2$
", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "congruences", "coprime", "euclidean algorithm", "gcd", "hcf", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving equations", "Solving equations", "udf"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Solving two simultaneous congruences:
\n\\[\\begin{eqnarray*} c_1x\\;&\\equiv&\\;b_1\\;&\\mod&\\;n_1\\\\ c_2x\\;&\\equiv&\\;b_2\\;&\\mod&\\;n_2\\\\ \\end{eqnarray*} \\] where $\\operatorname{gcd}(c_1,n_1)=1,\\;\\operatorname{gcd}(c_2,n_2)=1,\\;\\operatorname{gcd}(n_1,n_2)=1$
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n \n \n Using the method given in Steps:
\n \n \n \n First we find:
\n \n \n \n The inverse of $\\var{sa}$ in $\\mathbb{Z}_{\\var{sb}}$ is $\\var{ansp1}$, the inverse of $\\var{sc}$ in $\\mathbb{Z}_{\\var{sd}}$ is $\\var{ansp2}$.
\n \n \n \n (You can use the Extended Euclidean Algorithm to do this, and and your answers may differ from those above, but must be the same $\\mod\\;\\var{sb}$ and $\\mod\\;\\var{sd}$ respectively.)
\n \n \n \n Then multiplying both sides of the first equation by $\\var{ansp1}$ and both sides of the second equation by $\\var{ansp2}$ gives the pair of equations:
\n \n \n \n \\[\\begin{eqnarray*}\n \n x\\;&\\equiv&\\;\\var{a1}\\;\\mod\\;\\var{sb}\\\\\n \n \\\\\n \n x\\;&\\equiv&\\;\\var{a2}\\;\\mod\\;\\var{sd}\n \n \\end{eqnarray*}\n \n \\]
\n \n \n \n Now we use the formula given in Steps.
\n \n \n \n Let $n=\\var{sb}\\times \\var{sd}=\\var{sb*sd}$
\n \n \n \n Since $\\var{sb}$ and $\\var{sd}$ are coprime we find by using the Extended Euclidean Algorithm that:
\n \n \n \n 1) The inverse of $\\var{sb}\\;\\mod\\;\\var{sd}$ is $y_1=\\var{invb}$
\n \n \n \n 2) The inverse of $\\var{sd}\\;\\mod\\;\\var{sb}$ is $y_2=\\var{invd}$
\n \n \n \n (You may get different values, but they should be the same as those above $\\mod\\;\\var{sd}$ and $\\mod\\;\\var{sb}$ respectively.)
\n \n \n \n So $x=\\simplify[std]{{a1}* {sd} * {invd}+{a2}*{sb}*{invb}}=\\var{pans}=\\var{ans} \\;\\mod\\;\\var{sb*sd}$
\n \n "}, {"name": "Solve an equation in modular arithmetic", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(30..60)", "description": "", "name": "sb"}, "r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(10..sb-1)", "description": "", "name": "r1"}, "ans3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(r*ans2,sb)", "description": "", "name": "ans3"}, "ans2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(csa,sb)", "description": "", "name": "ans2"}, "mess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\n\n\nif(csa<0,\n\n'A positive inverse of $\\\\var{sa} \\\\; \\\\mod\\\\;\\\\var{sb}$ in the range $0\\\\le x \\\\le \\\\var{sb-1}$ is given by $\\\\simplify[]{{csa}+{sb}}\\\\;\\\\mod\\\\;\\\\var{sb}\\=\\\\var{mod(csa,sb)}\\\\;\\\\mod\\\\;\\\\var{sb}$\\n\\n.'\n\n,\n\n'Hence the inverse of $\\\\var{sa}$ in $\\\\mathbb{Z}_{\\\\var{sb}}$ is give by $x=\\\\var{mod(csa,sb)}$.'\n\n)\n\n\n", "description": "", "name": "mess"}, "csb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,sb)", "description": "", "name": "csb"}, "csa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sa,sb)", "description": "", "name": "csa"}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb)", "description": "", "name": "sa"}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(r1=sa,r1-1,r1)", "description": "", "name": "r"}}, "ungrouped_variables": ["r1", "mess", "ans2", "ans3", "csa", "csb", "r", "sb", "sa"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "showQuestionGroupNames": false, "functions": {"extendedgcd1": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(10..a-1)))", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n1\n\n,\n\nextendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n\n)\n\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "html", "language": "javascript", "definition": "var table=$('');\nfunction disp(s){\n return Numbas.jme.display.exprToLaTeX(s,['all'],scope);\n}\n\nfunction mdescextgcd(a,b,c1,c2,d1,d2){\nif((a%b==0) || (b%a==0)){\n table.append('| $\\\\var{'+a+'}$ | $\\\\var{'+b+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |
');\n}\nelse {\n if(a$\\\\var{'+a+'}$ | $\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$ | ');\n mdescextgcd(a,b%a,c1,c2,d1-fl*c1,d2-fl*c2);\n }\n else {\nvar fl1=Math.floor(a/b);\ntable.append('| $\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$ | $\\\\var{'+b+'}$ | $'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |
');\nmdescextgcd(a%b,b,c1-fl1*d1,c2-fl1*d2,d1,d2);}\n}\n}\nmdescextgcd(a,b,c1,c2,d1,d2);\n\nreturn table;\n", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}}, "parts": [{"showCorrectAnswer": true, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{ans3}", "minValue": "{ans3}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "prompt": "Solve the equation:
\\[ \\var{sa}x\\;\\equiv\\;\\var{r}\\;\\mod\\;\\var{sb}\\]
$x=\\;\\;$ [[0]]
\nYour value of $x$ should satisfy $0 \\leq x \\leq \\var{sb-1}$
", "variableReplacements": [], "marks": 0}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "", "tags": ["checked2015", "euclidean algorithm", "inverse in a ring", "Modular arithmetic", "modular arithmetic", "solving an equation", "udf", "units in a ring"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Solving an equation of the form $ax \\equiv b\\;\\textrm{mod}\\;n$ where $a$ and $n$ are coprime.
"}, "advice": "We use the extended Euclidean Algorithm to get:
\n{mdescextgcd(sa,sb,1,0,0,1)}
\nIt follows then that we have $\\var{csa}\\times \\var{sa}\\;\\equiv\\;1\\;\\mod \\var{sb}$
\n{mess}
\nWe are asked to solve
\n\\[ \\var{sa}x\\;\\equiv\\;\\var{r}\\;\\mod\\;\\var{sb}\\]
\nSince
\\[ \\begin{eqnarray*} \\var{ans2}\\times\\var{sa}\\;&\\equiv&\\;1\\;\\mod\\;\\var{sb} \\Rightarrow\\\\ \\var{ans2}\\times \\var{r} \\times \\var{sa}\\;&\\equiv&\\;\\var{r}\\;\\mod\\;\\var{sb}\\Rightarrow\\\\ \\var{ans2*r}\\times \\var{sa}&\\equiv&\\;\\var{r}\\;\\mod\\;\\var{sb} \\end{eqnarray*} \\]
\nHence
\n\\[ x=\\var{ans2*r}\\; \\equiv\\;\\var{ans3}\\;\\mod\\;\\var{sb} \\]
\nis the solution in the range $0\\le x \\le \\var{sb-1}$.
"}, {"name": "Solve congruence in given range", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"showPrecisionHint": false, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{al}", "showCorrectAnswer": true, "marks": 1, "maxValue": "{al}"}, {"showPrecisionHint": false, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{diff}", "showCorrectAnswer": true, "marks": 1, "maxValue": "{diff}"}, {"showPrecisionHint": false, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{leans}", "showCorrectAnswer": true, "marks": 1, "maxValue": "{leans}"}, {"showPrecisionHint": false, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{mans}", "showCorrectAnswer": true, "marks": 1, "maxValue": "{mans}"}], "type": "gapfill", "prompt": "Find all the solutions in the range $0 \\leq x \\lt \\var{sb}$ of the following equation by answering the following questions :
\\[ \\var{sa}x \\equiv \\var{r}\\mod\\var{sb}\\]
\nNote that it is advisable to read Steps the first one or two times you try this exercise.
\nNumber of solutions $\\;=\\;$ [[0]]
\nWhat is the difference between successive solutions?
\nDistance $\\;=\\;$ [[1]]
\nInput here the least solution in the range $0 \\leq x \\lt \\var{sb}$
\n$x=\\;\\;$[[2]]
\nInput here the greatest solution in the range $0 \\leq x \\lt \\var{sb}$
\n$x=\\;\\;$[[3]]
", "steps": [{"type": "information", "prompt": "\n \n \n Given an equation $ax\\;\\equiv\\;r \\;\\mod\\; n$ then the first step is to see if $a$ and $n$ are coprime.
\n \n \n \n If they are then you simply multiply both sides of the equation by the inverse of $a$ in $\\mathbb{Z}_n$ and this gives the unique solution.
\n \n \n \n However if not coprime with $\\operatorname{gcd}(a,n) = \\alpha \\gt 1$ then the Extended Euclidean Algorithm gives:
\\[\\lambda a+\\mu n = \\alpha,\\;\\;\\lambda,\\;\\mu \\in \\mathbb{Z}.\\]
\n \n \n \n Now if $\\alpha | r$ and $r=\\beta \\times \\alpha$ then on multiplying the last equation by $\\beta$ we get:
\\[\\lambda \\times \\beta a + \\mu \\times \\beta n=\\alpha \\times \\beta = r\\]
\n \n \n \n Hence we see that $x= \\lambda \\times \\beta \\mod \\;n$ is a solution of our original equation.
\n \n \n \n Also note that we can get other values of $\\lambda$ and $\\mu$ for $\\lambda a+\\mu n = \\alpha $ :
\\[\\left(\\lambda+i\\frac{n}{\\alpha}\\right) a+\\left(\\mu-i\\frac{a}{\\alpha}\\right) n = \\alpha,\\;\\;\\;i=0,1,\\ldots,\\alpha-1\\]
\n \n \n \n We see that there are $\\alpha$ possible values, $\\displaystyle{ \\lambda+i\\frac{n}{\\alpha},\\;\\;i=0,1,\\ldots,\\alpha-1}$ for the coefficient of $a$.
\n \n \n \n At first sight we could multiply by $\\beta$ to get other solutions to our original equation, just as we did above.
\n \n \n \n But if we look at $\\displaystyle{ \\left(\\lambda+i\\frac{n}{\\alpha}\\right)\\beta = \\lambda \\beta+i\\frac{n\\beta}{\\alpha}}$ then if
\n \n \n \n $\\operatorname{gcd}(\\alpha,\\beta) \\gt 1$ then there will be less than $\\alpha$ distinct values $\\mod\\;n$ for the solution.
\n \n \n \n This is because $\\displaystyle{\\lambda \\beta+i\\frac{n\\beta}{\\alpha}=\\lambda \\beta+i\\frac{n\\beta_1}{\\alpha_1}}$ for $\\alpha_1 \\lt \\alpha$ and $\\operatorname{gcd}(\\alpha_1,\\beta_1)=1$.
\n \n \n \n In this case we will get $\\alpha_1$ distinct solutions $\\mod\\;n$ rather than $\\alpha$ for $i=0,1\\dots,\\alpha_1-1$.
\n \n \n \n For example, consider \\[\\displaystyle{4x\\; \\equiv\\;8 \\mod\\; 12}\\]
\n \n \n \n Here we have $\\alpha=\\operatorname{gcd}(4,12)=4$, $12-2\\times 4 = 4 \\Rightarrow \\lambda= -2=10 \\mod 12$ and $\\beta = 8/4=2$.
\n \n \n \n Note that $\\operatorname{gcd}(\\alpha,\\beta) = 2$ and $\\frac{\\beta}{\\alpha}=\\frac{1}{2}$ so $\\alpha_1=2$.
\n \n \n \n So one solution is $\\lambda \\times \\beta = 10 \\times 2 = 20 = 8 \\mod 12$.
\n \n \n \n If we try to form other solutions we have:
\n \n \n \n $\\displaystyle{\\lambda \\beta+i\\frac{n\\beta}{\\alpha} = 8+i\\frac{12\\times 2}{4}=8+6i}$ and we have only $2$ solutions rather than $4$
\n \n \n \n given by $8$ when $i=0$ and $14=2 \\mod 12$ when $i=1$. When $i=2$ we get $8 \\mod 12 $ again.
\n \n \n \n However, if the example you are trying has $\\operatorname{gcd}(\\alpha,\\beta)=1$ then we will get $\\alpha$ distinct solutions.
\n \n \n\n", "showCorrectAnswer": true, "marks": 0, "scripts": {}}], "showCorrectAnswer": true, "marks": 0}], "variables": {"mans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(mans_first=sb,sb-diff,mans_first)", "name": "mans", "description": ""}, "ans2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(csa,sb)", "name": "ans2", "description": ""}, "ans3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(be*ans2,sb)", "name": "ans3", "description": ""}, "mess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\n\n\nif(csa<0,\n\n'$=\\\\var{mod(be*csa,sb)}\\\\;\\\\mod\\\\;\\\\var{sb}$.'\n\n,\n\n'.'\n\n)\n\n\n\n", "name": "mess", "description": ""}, "al": {"templateType": "anything", "group": "Ungrouped variables", "definition": "gcd(sa,sb)", "name": "al", "description": ""}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "//this gives a number sb in the range sa+1 to 80 such that 2 <=gcd(a,b)<=5\nnco(sa,sa,2,5)", "name": "sb", "description": ""}, "mans_first": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sb-mod(sb-ans3,diff)", "name": "mans_first", "description": ""}, "diff": {"templateType": "anything", "group": "Ungrouped variables", "definition": "round(sb/al)", "name": "diff", "description": ""}, "be": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..5)*al+1", "name": "be", "description": ""}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "al*be", "name": "r", "description": ""}, "leans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ans3,diff)", "name": "leans", "description": ""}, "csb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,sb)", "name": "csb", "description": ""}, "csa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sa,sb)", "name": "csa", "description": ""}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2,4,3,5)*random(4..12)", "name": "sa", "description": ""}}, "ungrouped_variables": ["be", "mans", "mess", "ans2", "ans3", "csa", "al", "leans", "csb", "r", "sb", "diff", "sa", "mans_first"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"nco": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)n,nco(a,random(a+1..80),m,n),b)", "parameters": [["a", "number"], ["b", "number"], ["m", "number"], ["n", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 0\n \n ,\n \n extendedgcd2(b,mod(a,b))\n \n )\n \n \n\n", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 1\n \n ,\n \n extendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n \n )\n \n \n\n", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "html", "language": "javascript", "definition": "var table=$('');\nfunction disp(s){\n return Numbas.jme.display.exprToLaTeX(s,['all'],scope);\n}\n\nfunction mdescextgcd(a,b,c1,c2,d1,d2){\nif((a%b==0) || (b%a==0)){\n table.append('| $\\\\var{'+a+'}$ | $\\\\var{'+b+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |
');}\n else {\n if(a$\\\\var{'+a+'}$ | $\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$ | ');\n mdescextgcd(a,b%a,c1,c2,d1-fl*c1,d2-fl*c2);\n }\n else {\nvar fl1=Math.floor(a/b);\ntable.append('| $\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$ | $\\\\var{'+b+'}$ | $'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |
');\nmdescextgcd(a%b,b,c1-fl1*d1,c2-fl1*d2,d1,d2);}\n}\n}\nmdescextgcd(a,b,c1,c2,d1,d2);\n\nreturn table;\n", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}}, "variable_groups": [], "showQuestionGroupNames": false, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "", "tags": ["checked2015", "congruences", "coprime", "euclidean algorithm", "gcd", "MAS3214", "Modular arithmetic", "modular arithmetic", "solving a congruence", "Solving equations", "solving equations", "solving equations in a ring", "udf"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Solving an equation of the form $ax \\equiv\\;b\\;\\textrm{mod}\\;n$ where $\\operatorname{gcd}(a,n)|r$. In this case we can find all solutions. The user is asked for the two greatest.
"}, "advice": "This explanation assumes that you have read the Steps section of this exercise.
\nThe first thing to do is to see if $\\var{sa}$ and $\\var{sb}$ are coprime or not.
\nIf they are then all we do is multiply both sides of the equation by the inverse of $\\var{sa}$ in $\\mathbb{Z}_{\\var{sb}}$ to get a unique solution.
\nBut it is not too hard to see that the gcd of $\\var{sa}$ and $\\var{sb}$ is $\\var{al}$, hence they are not coprime, and that using the extended Euclidean Algorithm
\n{mdescextGCD(sa,sb,1,0,0,1)}
\nSo we see that $\\simplify[all,!collectNumbers,!noleadingMinus]{{csa}*{sa}+{csb}*{sb}={al}}$
\nBut since $\\var{al}$ divides $\\var{r}$ we have that on multiplying this last equation by $\\var{be}$ that
\n\\[\\simplify[std]{{sa}*{be*csa}+{sb}*{be*csb}={al}*{be}={r}}\\]
\nHence we see that $x=\\var{be*csa}\\equiv\\;\\var{ans3}\\;\\mod \\;\\var{sb}$ is a solution.
\nThere are other solutions, (see Steps) of the form \\[x=\\var{ans3}+i\\frac{\\var{sb}\\times \\var{be}}{\\var{al}} \\;\\mod\\;\\var{sb},\\;\\;i=0,\\ldots,\\var{al-1}\\]
\nTo see if we get $\\var{al}$ distinct solutions we check to see if $\\var{be}$ and $\\var{al}$ are coprime, and they clearly are.
\nHence we get $\\var{al}$ solutions, and the difference between successive solutions is:
\n\\[\\frac{\\var{sb}\\times \\var{be}}{\\var{al}} = \\var{diff}\\;\\mod\\;\\var{sb} \\]
\nGiven that we have one solution $x=\\var{ans3} \\;\\mod \\;\\var{sb}$ it is then easy to see that the least solution is $\\var{leans}\\;\\mod\\;\\var{sb}$ and the greatest is $\\var{mans}\\;\\mod\\;\\var{sb}$.
"}, {"name": "Solve three congruences using Chinese Remainder Theorem", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(12..20)", "description": "", "name": "sb"}, "rb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..sb-1)", "description": "", "name": "rb"}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ra*ea+rb*eb+rc*ec,n)", "description": "", "name": "pans"}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop3(sa,sb,sb,2,sa-1)", "description": "", "name": "sc"}, "nb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sc", "description": "", "name": "nb"}, "rc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..sc-1)", "description": "", "name": "rc"}, "ra": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sa-1)", "description": "", "name": "ra"}, "na": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sb*sc", "description": "", "name": "na"}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,8,sb-1)", "description": "", "name": "sa"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "pans", "description": "", "name": "ans"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "na*sa", "description": "", "name": "n"}, "eb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sb,nb)*nb", "description": "", "name": "eb"}, "nc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb", "description": "", "name": "nc"}, "ec": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,nc)*nc", "description": "", "name": "ec"}, "ea": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,na)*na", "description": "", "name": "ea"}}, "ungrouped_variables": ["pans", "na", "nb", "nc", "ea", "rc", "ec", "n", "ra", "rb", "ans", "sc", "sb", "sa", "eb"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"mdescext1gcd": {"type": "string", "language": "jme", "definition": "\n \n \n if(a$\\var{a}$ | $\\var{b}-\\var{floor(b/a)}\\times\\var{a}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify[std,noleadingMinus]{{d1}a+{d2}b-{floor(b/a)}*({c1}a+{c2}b)}$ | \\n'+mdescextGCD(a,mod(b,a),c1,c2,d1-floor(b/a)*c1,d2-floor(b/a)*c2,1)\n \n ,\n \n '| $\\var{a}-\\var{floor(a/b)}\\times\\var{b}$ | $\\var{b}$ | $\\simplify[std,noleadingMinus]{{c1}a+{c2}b-{floor(a/b)}*({d1}a+{d2}b)}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescextGCD(mod(a,b),b,c1-floor(a/b)*d1,c2-floor(a/b)*d2,d1,d2,1)\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 0\n \n ,\n \n extendedgcd2(b,mod(a,b))\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "testgcd3": {"type": "number", "language": "jme", "definition": "max(max(gcd(a,b),gcd(a,c)),gcd(b,c))", "parameters": [["a", "number"], ["b", "number"], ["c", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n \n \n if((a|b) or (b|a),\n \n 1\n \n ,\n \n extendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "chcop3": {"type": "number", "language": "jme", "definition": "if(testgcd3(a,b,c)=1,c,chcop3(a,b,random(p..q),p,q))", "parameters": [["a", "number"], ["b", "number"], ["c", "number"], ["p", "number"], ["q", "number"]]}, "chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(p..q),p,q))", "parameters": [["a", "number"], ["b", "number"], ["p", "number"], ["q", "number"]]}, "mdescextgcd": {"type": "string", "language": "jme", "definition": "\n \n \n if (t=0, \n \n '\\n\\n\\n'+mdescextGCD(a,b,c1,c2,d1,d2,1)\n \n ,\n \n if(a|b,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n \n \n \n $\\var{a} | \\var{b}$ and so $(\\var{sa},\\var{sb})=\\var{a}$. Note that $\\simplify[std]{{c1}*{sa}+{c2}*{sb} = {a}}$\\n\\n '\n \n ,\n \n if(b|a,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n \n \n \n $\\var{b} | \\var{a}$ and so $(\\var{sa},\\var{sb})=\\var{b}$. Note that $\\simplify[std]{{d1}*{sa}+{d2}*{sb} = {b}}$\\n\\n '\n \n ,\n \n ' | $\\var{a}$ | $\\var{b}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescext1GCD(a,b,c1,c2,d1,d2)\n \n )\n \n )\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"], ["t", "number"]]}}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans}", "minValue": "{ans}", "correctAnswerFraction": false, "marks": 4, "showPrecisionHint": false}], "type": "gapfill", "prompt": "\n \n \n Solve the following simultaneous congruences:
\\[\\begin{eqnarray*}\n \n x\\;&\\equiv&\\;\\var{ra}\\;&\\mod&\\;\\var{sa}\\\\\n \n \\\\\n \n x\\;&\\equiv&\\;\\var{rb}\\;&\\mod&\\;\\var{sb}\\\\\n \n \\\\\n \n x\\;&\\equiv&\\;\\var{rc}\\;&\\mod&\\;\\var{sc}\n \n \\end{eqnarray*}\n \n \\]
$x=\\;\\;$ [[0]]
\n \n \n \n Your value of $x$ should satisfy $0 \\leq x \\lt \\var{n}$
\n \n \n \n Steps gives you information on the Chinese Remainder Theorem and the steps you need to take to solve the congruences.
\n \n ", "steps": [{"type": "information", "prompt": "\n \n \n Given the simultaneous congruences:
\\[\\begin{eqnarray*}\n \n x\\;&\\equiv&\\;a_1\\;&\\mod&\\;n_1\\\\\n \n \\\\\n \n x\\;&\\equiv&\\;a_2\\;&\\mod&\\;n_2\\\\\n \n \\\\\n \n x\\;&\\equiv&\\;a_3\\;&\\mod&\\;n_3\n \n \\end{eqnarray*}\n \n \\]
where $\\operatorname{gcd}(n_1,n_2,n_3)=1$ we first observe that:
\n \n \n \n $N_1=n_2 n_3$ and $n_1$ are coprime, $N_2=n_1 n_3$ and $n_2$ are coprime, $N_3=n_1 n_2$ and $n_3$ are coprime.
\n \n \n \n So there is an inverse $x_1$ of $N_1$ in $Z_{n_1}$ such that $N_1x_1\\equiv 1 \\;\\mod\\;n_1$. Let $E_1=N_1x_1$, and similarly:
\n \n \n \n There is an inverse $x_2$ of $N_2$ in $Z_{n_2}$ such that $N_2x_2\\equiv 1 \\;\\mod\\;n_2$. Let $E_2=N_2x_2$.
\n \n \n \n There is an inverse $x_3$ of $N_3$ in $Z_{n_3}$ such that $N_3x_3\\equiv 1 \\;\\mod\\;n_3$. Let $E_3=N_3x_3$.
\n \n \n \n Then $x=a_1 E_1+a_2 E_2 + a_3 E_3 \\;\\mod\\;n_1n_2n_3$ is a solution to the simultaneous congruences.
\n \n \n \n See your notes for a full explanation.
\n \n ", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "Chinese Remainder Theorem", "congruences", "coprime", "euclidean algorithm", "gcd", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving equations", "Solving equations"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Solving three simultaneous congruences using the Chinese Remainder Theorem:
\n\\[\\begin{eqnarray*} x\\;&\\equiv&\\;b_1\\;&\\mod&\\;n_1\\\\ x\\;&\\equiv&\\;b_2\\;&\\mod&\\;n_2\\\\x\\;&\\equiv&\\;b_3\\;&\\mod&\\;n_3 \\end{eqnarray*} \\] where $\\operatorname{gcd}(n_1,n_2,n_3)=1$
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n \n \n Using the notation in Steps we have:
\n \n \n \n 1) $n_1=\\var{sa},\\;n_2=\\var{sb},\\;n_3=\\var{sc}$ are coprime as they have no factors in common.
$n=n_1n_2n_3=\\var{n}$
\n \n \n \n 2)
$N_1=\\var{sb}\\times \\var{sc}=\\var{na},\\;\tN_2=\\var{sa}\\times \\var{sc}=\\var{nb},\\;N_3=\\var{sa}\\times \\var{sb}=\\var{nc}$
\n \n \n \n 3)
\n \n \n \n Using the Extended Euclidean Algorithm for $N_1=\\var{na}$ and $n_1=\\var{sa}$ we find:
\\[\\simplify[std]{{extendedgcd2(sa,na)}* {na} +{extendedgcd1(sa,na)}*{sa}=1} \\Rightarrow E_1=\\var{extendedgcd2(sa,na)}\\times \\var{na}=\\var{ea}\\]
Using the Extended Euclidean Algorithm for $N_2=\\var{nb}$ and $n_2=\\var{sb}$ we find:
\\[\\simplify[std]{{extendedgcd2(sb,nb)}* {nb} +{extendedgcd1(sb,nb)}*{sb}=1} \\Rightarrow E_2=\\var{extendedgcd2(sb,nb)}\\times \\var{nb}=\\var{eb}\\]
Using the Extended Euclidean Algorithm for $N_3=\\var{nc}$ and $n_3=\\var{sc}$ we find:
\\[\\simplify[std]{{extendedgcd2(sc,nc)}* {nc} +{extendedgcd1(sc,nc)}*{sc}=1} \\Rightarrow E_3=\\var{extendedgcd2(sc,nc)}\\times \\var{nc}=\\var{ec}\\]\t
4)
Then the general solution is:\\[\\begin{eqnarray*}\n \n x&=& a_1 E_1+a_2 E_2+a_3 E_3\\;\\mod\\;n\\\\\n \n &=& \\simplify[std]{{ra}*{ea}+{rb}*{eb}+{rc}*{ec}}\\;\\mod\\;\\var{n}\\\\\n \n &=&\\var{ra*ea+rb*eb+rc*ec}\\;\\mod\\;\\var{n}\\\\\n \n &=& \\var{ans}\\;\\mod\\;\\var{n}\n \n \\end{eqnarray*}\n \n \\]
\n \n "}, {"name": "Solve three congruences with the Chinese Remainder Theorem", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "parts": [{"marks": 0, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showPrecisionHint": false, "allowFractions": false, "scripts": {}, "type": "numberentry", "showCorrectAnswer": true, "minValue": "{age}", "maxValue": "{age}", "marks": 3}], "type": "gapfill", "showCorrectAnswer": true, "steps": [{"type": "information", "prompt": "\n\n\nFirst you convert the statements about age into 3 simultaneous congruences of the form:
\\[\\begin{eqnarray*}\n\nx\\;&\\equiv&\\;a_1\\;&\\mod&\\;n_1\\\\\n\n\\\\\n\nx\\;&\\equiv&\\;a_2\\;&\\mod&\\;n_2\\\\\n\n\\\\\n\nx\\;&\\equiv&\\;a_3\\;&\\mod&\\;n_3\n\n\\end{eqnarray*}\n\n\\]
where $\\operatorname{gcd}(n_1,n_2,n_3)=1$ we first observe that:
\n\n\n\n$N_1=n_2 n_3$ and $n_1$ are coprime, $N_2=n_1 n_3$ and $n_2$ are coprime, $N_3=n_1 n_2$ and $n_3$ are coprime.
\n\n\n\nSo there is an inverse $x_1$ of $N_1$ in $Z_{n_1}$ such that $N_1x_1\\equiv 1 \\;\\mod\\;n_1$. Let $E_1=N_1x_1$, and similarly:
\n\n\n\nThere is an inverse $x_2$ of $N_2$ in $Z_{n_2}$ such that $N_2x_2\\equiv 1 \\;\\mod\\;n_2$. Let $E_2=N_2x_2$.
\n\n\n\nThere is an inverse $x_3$ of $N_3$ in $Z_{n_3}$ such that $N_3x_3\\equiv 1 \\;\\mod\\;n_3$. Let $E_3=N_3x_3$.
\n\n\n\nThen $x=a_1 E_1+a_2 E_2 + a_3 E_3 \\;\\mod\\;n_1n_2n_3$ is a solution to the simultaneous congruences.
\n\n\n\nSee your notes for a full explanation.
\n\n", "showCorrectAnswer": true, "marks": 0, "scripts": {}}], "prompt": "\n\n\nSolve the following simultaneous congruences.
On division by $\\var{sa}$ my age gives remainder $\\var{ra}$.
On division by $\\var{sb}$ my age gives remainder $\\var{rb}$.
On division by $\\var{sc}$ my age gives remainder $\\var{rc}$.
\n\n\n\nHold old am I?
\n\n\n\nage$\\;=$ [[0]]
\n\n\n\nYour value of the age should satisfy $29 \\leq x \\leq 73$
\n\n\n\nSteps gives you more information on solving the Chinese Remainder Theorem.
\n\n", "stepsPenalty": 0}], "variables": {"ra": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(age,sa)", "name": "ra", "description": ""}, "rb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(age,sb)", "name": "rb", "description": ""}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ra*ea+rb*eb+rc*ec,n)", "name": "pans", "description": ""}, "co": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[[2,5,7],[2,5,9],[3,4,5],[3,4,7],[3,5,7],[3,5,8],[3,7,10],[4,5,7],[4,5,9]]", "name": "co", "description": ""}, "nb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sc", "name": "nb", "description": ""}, "rc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(age,sc)", "name": "rc", "description": ""}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "co[t][1]", "name": "sb", "description": ""}, "na": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sb*sc", "name": "na", "description": ""}, "age": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(29,31,37,41,43,47,53,59,61,67,71,73)", "name": "age", "description": ""}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb*sc", "name": "n", "description": ""}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "co[t][2]", "name": "sc", "description": ""}, "eb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sb,nb)*nb", "name": "eb", "description": ""}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "co[t][0]", "name": "sa", "description": ""}, "ec": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,nc)*nc", "name": "ec", "description": ""}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..8)", "name": "t", "description": ""}, "ea": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,na)*na", "name": "ea", "description": ""}, "nc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb", "name": "nc", "description": ""}}, "ungrouped_variables": ["pans", "co", "na", "age", "nc", "ea", "ec", "n", "t", "rb", "rc", "sc", "sb", "sa", "eb", "nb", "ra"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(10..a-1)))", "parameters": [["a", "number"], ["b", "number"]]}, "mdescext1gcd": {"type": "string", "language": "jme", "definition": "\n\n\nif(a$\\var{a}$ | $\\var{b}-\\var{floor(b/a)}\\times\\var{a}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify[std,noleadingMinus]{{d1}a+{d2}b-{floor(b/a)}*({c1}a+{c2}b)}$ | \\n'+mdescextGCD(a,mod(b,a),c1,c2,d1-floor(b/a)*c1,d2-floor(b/a)*c2,1)\n\n,\n\n'| $\\var{a}-\\var{floor(a/b)}\\times\\var{b}$ | $\\var{b}$ | $\\simplify[std,noleadingMinus]{{c1}a+{c2}b-{floor(a/b)}*({d1}a+{d2}b)}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescextGCD(mod(a,b),b,c1-floor(a/b)*d1,c2-floor(a/b)*d2,d1,d2,1)\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n1\n\n,\n\nextendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "string", "language": "jme", "definition": "\n\n\nif (t=0, \n\n'\\n\\n\\n'+mdescextGCD(a,b,c1,c2,d1,d2,1)\n\n,\n\nif(a|b,\n\n' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n\n\n\n $\\var{a} | \\var{b}$ and so $(\\var{sa},\\var{sb})=\\var{a}$. Note that $\\simplify[std]{{c1}*{sa}+{c2}*{sb} = {a}}$\\n\\n '\n\n,\n\nif(b|a,\n\n' | $\\var{a}$ | $\\var{b}$ | $\\simplify[std]{{c1}a+{c2}b}$ | $\\simplify[std]{{d1}a+{d2}b}$ |
\n\n\n\n$\\var{b} | \\var{a}$ and so $(\\var{sa},\\var{sb})=\\var{b}$. Note that $\\simplify[std]{{d1}*{sa}+{d2}*{sb} = {b}}$\\n\\n '\n\n,\n\n' | $\\var{a}$ | $\\var{b}$ | $\\simplify{{c1}a+{c2}b}$ | $\\simplify{{d1}a+{d2}b}$ |
\\n'+mdescext1GCD(a,b,c1,c2,d1,d2)\n\n)\n\n)\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"], ["t", "number"]]}}, "variable_groups": [], "showQuestionGroupNames": false, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "", "tags": ["checked2015", "congruences", "coprime", "euclidean algorithm", "gcd", "hcf", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving equations", "Solving equations", "udf"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Solving three simultaneous congruences using the Chinese Remainder Theorem:
\n\\[\\begin{eqnarray*} x\\;&\\equiv&\\;b_1\\;&\\mod&\\;n_1\\\\ x\\;&\\equiv&\\;b_2\\;&\\mod&\\;n_2\\\\x\\;&\\equiv&\\;b_3\\;&\\mod&\\;n_3 \\end{eqnarray*} \\] where $\\operatorname{gcd}(n_1,n_2,n_3)=1$
"}, "advice": "\n\n\nAfter converting the statements about age into congruences we obtain the following congruences:
\\[\\begin{eqnarray*}\n\nx\\;&\\equiv&\\;\\var{ra}\\;&\\mod&\\;\\var{sa}\\\\\n\n\\\\\n\nx\\;&\\equiv&\\;\\var{rb}\\;&\\mod&\\;\\var{sb}\\\\\n\n\\\\\n\nx\\;&\\equiv&\\;\\var{rc}\\;&\\mod&\\;\\var{sc}\n\n\\end{eqnarray*}\n\n\\]
\n\n\n\nFollowing the notation as set out in Steps we have:
\n\n\n\n1) $n_1=\\var{sa},\\;n_2=\\var{sb},\\;n_3=\\var{sc}$ are coprime as they have no factors in common.
\n\n\n\n$n=n_1n_2n_3=\\var{n}$
\n\n\n\n2)
$N_1=\\var{sb}\\times \\var{sc}=\\var{na},\\;\tN_2=\\var{sa}\\times \\var{sc}=\\var{nb},\\;N_3=\\var{sa}\\times \\var{sb}=\\var{nc}$
\n\n\n\n3)
\n\n\n\nUsing the Extended Euclidean Algorithm for $N_1=\\var{na}$ and $n_1=\\var{sa}$ we find:
\\[\\simplify[std]{{extendedgcd2(sa,na)}* {na} +{extendedgcd1(sa,na)}*{sa}=1} \\Rightarrow E_1=\\var{extendedgcd2(sa,na)}\\times \\var{na}=\\var{ea}\\]
Using the Extended Euclidean Algorithm for $N_2=\\var{nb}$ and $n_2=\\var{sb}$ we find:
\\[\\simplify[std]{{extendedgcd2(sb,nb)}* {nb} +{extendedgcd1(sb,nb)}*{sb}=1} \\Rightarrow E_2=\\var{extendedgcd2(sb,nb)}\\times \\var{nb}=\\var{eb}\\]
Using the Extended Euclidean Algorithm for $N_3=\\var{nc}$ and $n_3=\\var{sc}$ we find:
\\[\\simplify[std]{{extendedgcd2(sc,nc)}* {nc} +{extendedgcd1(sc,nc)}*{sc}=1} \\Rightarrow E_3=\\var{extendedgcd2(sc,nc)}\\times \\var{nc}=\\var{ec}\\]\t
4)
Then the solution is:\\[\\begin{eqnarray*}\n\nx&=& a_1 E_1+a_2 E_2+a_3 E_3\\;\\mod\\;n\\\\\n\n&=& \\simplify[std]{{ra}*{ea}+{rb}*{eb}+{rc}*{ec}}\\;\\mod\\;\\var{n}\\\\\n\n&=&\\var{ra*ea+rb*eb+rc*ec}\\;\\mod\\;\\var{n}\\\\\n\n&=& \\var{age}\\;\\mod\\;\\var{n}\n\n\\end{eqnarray*}\n\n\\]
So my age is $\\var{age}$.
\n\n"}, {"name": "Find $\\mu(n)$, $\\sigma(n)$, $\\tau(n)$, $\\phi(n)$", "extensions": ["stats"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"siga1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[(p[0]^(c[0]+1)-1)/(p[0]-1),(p[1]^(c[1]+1)-1)/(p[1]-1),(p[2]^(c[2]+1)-1)/(p[2]-1),(p[3]^(c[3]+1)-1)/(p[3]-1),(p[4]^(c[4]+1)-1)/(p[4]-1)]", "description": "", "name": "siga1"}, "sig": {"templateType": "anything", "group": "Ungrouped variables", "definition": "prodlist(siga,1,4)", "description": "", "name": "sig"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s=0,a2+a1,a1+a2)", "description": "", "name": "a"}, "siga": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(max(x,1),x,siga1)", "description": "", "name": "siga"}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "3", "description": "", "name": "t"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(1..t),2)", "description": "", "name": "a1"}, "mu": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(mu2=1,(-1)^mu1,0)", "description": "", "name": "mu"}, "eorodd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(notzero|2,'even','odd')", "description": "", "name": "eorodd"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "p[0]^c[0]*p[1]^c[1]*p[2]^c[2]*p[3]^c[3]*p[4]^c[4]", "description": "", "name": "n"}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sort(a)", "description": "", "name": "b"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[2,3,5,7,11]", "description": "", "name": "p"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "repeat(random(0..2),2)", "description": "", "name": "a2"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[b[0],b[1]-b[0],b[2]-b[1],b[3]-b[2],t-b[3]]", "description": "", "name": "c"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sort(c)", "description": "", "name": "d"}, "mess": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(mu2>1, 'however','and')", "description": "", "name": "mess"}, "phi": {"templateType": "anything", "group": "Ungrouped variables", "definition": "prodlist(phia,1,4)", "description": "", "name": "phi"}, "ta": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(1+c[0])*(1+c[1])*(1+c[2])*(1+c[3])*(1+c[4])", "description": "", "name": "ta"}, "mu1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sum(c)", "description": "", "name": "mu1"}, "s": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0,1)", "description": "", "name": "s"}, "mu2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[4]", "description": "", "name": "mu2"}, "phia1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[p[0]^(c[0]-1)*(p[0]-1),p[1]^(c[1]-1)*(p[1]-1),p[2]^(c[2]-1)*(p[2]-1),p[3]^(c[3]-1)*(p[3]-1),p[4]^(c[4]-1)*(p[4]-1)]", "description": "", "name": "phia1"}, "phia": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(max(x,1),x,phia1)", "description": "", "name": "phia"}, "notzero": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sum(map(min(x,1),x,c))", "description": "", "name": "notzero"}}, "ungrouped_variables": ["siga", "eorodd", "phia1", "notzero", "sig", "siga1", "ta", "phi", "mess", "a1", "a2", "a", "c", "b", "mu1", "d", "phia", "mu2", "n", "mu", "p", "s", "t"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"prodlist": {"type": "number", "language": "jme", "definition": "if(n=-1,p,prodlist(a,p*a[n],n-1))", "parameters": [["a", "list"], ["p", "number"], ["n", "number"]]}}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{mu}", "minValue": "{mu}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ta}", "minValue": "{ta}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{sig}", "minValue": "{sig}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{phi}", "minValue": "{phi}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "prompt": "\n\n\nLet $n=\\var{n}$.
\n\n\n\nFind:
\n\n\n\n$\\mu(n) =\\;\\;$[[0]]
\n\n\n\n$\\tau(n)=\\;\\;$[[1]]
\n\n\n\n$\\sigma(n)=\\;\\;$[[2]]
\n\n\n\n$\\phi(n)=\\;\\;$[[3]]
\n\n", "steps": [{"type": "information", "prompt": "\n\n\nDefinitions.
\n\n\n\n$\\mu(n)$ gives information on the prime decomposition of $n$ (see formula below).
\n\n\n\n$\\tau(n)$ gives the number of divisors of $n$.
\n\n\n\n$\\sigma(n)$ is the sum of all divisors of $n$
\n\n\n\n$\\phi(n)$ is the number of natural integers $\\lt n$ which are coprime to $n$.
\n\n\n\nAll are multiplicative functions i.e. $f(n)$ is multiplicative if $n_1,\\;n_2$ are coprime then:
\\[ f(n_1n_2)=f(n_1)f(n_2)\\]
\n\n\n\nMore Information and Formulae.
\n\n\n\nRecall that if $n=p_1^{\\beta_1}\\times p_2^{\\beta_2}\\times \\cdots \\times p_m^{\\beta_m},\\;\\;\\beta_j \\ge 1,\\;\\forall j$ is the prime factorization of $n$ then:
\\[\\begin{eqnarray*}\\mu(n)&=&0, \\mbox{ if }\\exists j, p_j \\ge 2\\\\\n\n&=&(-1)^m, \\mbox{ if }\\beta_j=1,\\;\\;\\forall j\\\\\n\n\\\\\n\n\\tau(n)&=&(\\beta_1+1)\\times (\\beta_2+1) \\times\\cdots \\times (\\beta_m+1)\\\\\n\n\\\\\n\n\\sigma(n)&=& \\frac{(p_1^{\\beta_1+1}-1)}{p_1-1}\\times \\frac{(p_2^{\\beta_2+1}-1)}{p_2-1} \\times \\cdots \\times \\frac{(p_m^{\\beta_m+1}-1)}{p_m-1}\\\\\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_m^{\\beta_m} - p_m^{\\beta_m-1})\n\n\\end{eqnarray*}\n\n\\]
\n\n", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "coprime", "euler totient function", "MAS3214", "multiplicative functions", "M\u00f6bius function", "number of divisors", "number theory", "prime decompositions", "sum of divisors"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Number Theory.
\nGiven $n \\in \\mathbb{N}$ find $\\mu(n),\\;\\tau(n),\\;\\sigma(n),\\;\\phi(n).$
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n\n\nThe factorization into a product of powers of prime factors is given by:
\n\n\n\n$\\var{n} = \\simplify[unitFactor,unitPower,zeroPower]{{p[0]}^{c[0]}*{p[1]}^{c[1]}*{p[2]}^{c[2]}*{p[3]}^{c[3]}*{p[4]}^{c[4]}}$
\n\n\n\nFinding $\\mu(\\var{n})$
\n\n\n\nThere are an {eorodd} number $\\var{notzero}$ of distinct prime factors, {mess} since the maximum power of any prime in this factorization is {d[4]} we see that
\n\n\n\n$\\mu(\\var{n})=\\;\\var{mu}$
\n\n\n\nFinding $\\tau(\\var{n})$
\n\n\n\nRecall that if $n=p_1^{\\beta_1}\\times p_2^{\\beta_2}\\times \\cdots \\times p_m^{\\beta_m}$ is the prime factorization of $n$, then the number of divisors is given by:
\n\n\n\n$\\tau(n)=(\\beta_1+1)\\times (\\beta_2+1) \\times\\cdots \\times (\\beta_m+1)$
\n\n\n\nHence in this case we have:
\n\n\n\n$\\tau(\\var{n})=\\tau( \\simplify[unitFactor,unitPower,zeroPower]{{p[0]}^{c[0]}*{p[1]}^{c[1]}*{p[2]}^{c[2]}*{p[3]}^{c[3]}*{p[4]}^{c[4]}})=\\simplify[!basic,unitFactor,zeroTerm]{({c[0]}+1)*({c[1]}+1)*({c[2]}+1)*({c[3]}+1)*({c[4]}+1)}=\\var{ta}$
\n\n\n\nFinding $\\sigma(\\var{n})$
\n\n\n\nThe sum over all divisors is given by :
\n\n\n\n\\[\\sigma(n)= \\frac{(p_1^{\\beta_1+1}-1)}{p_1-1}\\times \\frac{(p_2^{\\beta_2+1}-1)}{p_2-1} \\times \\cdots \\times \\frac{(p_m^{\\beta_m+1}-1)}{p_m-1}\\]
\n\n\n\nIn this case we have:
\n\n\n\n\\[\\begin{eqnarray*}\n\n\\sigma(\\var{n})&=&\\sigma( \\simplify[unitFactor,unitPower,zeroPower]{{p[0]}^{c[0]}*{p[1]}^{c[1]}*{p[2]}^{c[2]}*{p[3]}^{c[3]}*{p[4]}^{c[4]}})\\\\ \n\n&=&\\simplify[unitFactor]{{siga[0]}*{siga[1]}*{siga[2]}*{siga[3]}*{siga[4]}}\\\\\n\n&=&\\var{sig}\n\n\\end{eqnarray*}\n\n\\]
\n\n\n\nFinding $\\phi(\\var{n})$
\n\n\n\nThis is the Euler totient function and $\\phi(n)$ it counts up the number of integers less than $n$ which are coprime to $n$.
\n\n\n\nThe formula we use for this 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_m^{\\beta_m} - p_m^{\\beta_m-1})\\]
\n\n\n\n$\\phi(\\var{n})=\\phi( \\simplify[unitFactor,unitPower,zeroPower]{{p[0]}^{c[0]}*{p[1]}^{c[1]}*{p[2]}^{c[2]}*{p[3]}^{c[3]}*{p[4]}^{c[4]}})=\\simplify[unitFactor]{{phia[0]}*{phia[1]}*{phia[2]}*{phia[3]}*{phia[4]}}=\\var{phi}$
\n\n"}, {"name": "Find all numbers with given value of $\\phi(n)$", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"bp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "ordp[0]*ordp[1]", "description": "", "name": "bp"}, "gcp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "gcd(bp,tp)", "description": "", "name": "gcp"}, "chkmp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "map(if(x=pairs[j][0] or x=pairs[j][1],1,-1),x,0..abs(p)-1)", "description": "", "name": "chkmp"}, "bfp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "ordp[1]", "description": "", "name": "bfp"}, "j": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..17)", "description": "", "name": "j"}, "ordp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[p[pairs[j][0]],p[pairs[j][1]]]", "description": "", "name": "ordp"}, "pairs": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[1,3],[1,5],[1,7],[1,10],[2,4],[2,10],[2,12],[3,9],[3,13],[4,8]]", "description": "", "name": "pairs"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[2,3,5,7,11,13,17,19,23,29,31,37,41,43]", "description": "", "name": "p"}, "tp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(ordp[0]-1)*(ordp[1]-1)", "description": "", "name": "tp"}, "bp1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "bp/gcp", "description": "", "name": "bp1"}, "tp1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "tp/gcp", "description": "", "name": "tp1"}}, "ungrouped_variables": ["pairs", "p", "chkmp", "j", "tp", "bp1", "gcp", "bfp", "bp", "tp1", "ordp"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"displayType": "checkbox", "choices": ["2", "3", "5", "7", "11", "13", "17", "19", "23", "29", "31", "37", "41", "43"], "matrix": ["chkmp[0]", "chkmp[1]", "chkmp[2]", "chkmp[3]", "chkmp[4]", "chkmp[5]", "chkmp[6]", "chkmp[7]", "chkmp[8]", "chkmp[9]", "chkmp[10]", "chkmp[11]", "chkmp[12]", "chkmp[13]"], "distractors": ["", "", "", "", "", "", "", "", "", "", "", "", "", ""], "type": "m_n_2", "maxAnswers": 0, "shuffleChoices": false, "scripts": {}, "minMarks": 0, "minAnswers": 0, "maxMarks": 0, "showCorrectAnswer": true, "displayColumns": 7, "marks": 0}], "type": "gapfill", "prompt": "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\\]
\n\n\n\nIt 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\\]
\n\n\n\nBut 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\\]
\n\n"}, {"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}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "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}], "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"}, {"name": "Find n such that $\\sigma(n)$ is the given number", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variablesTest": {"condition": "len(good_target_factorisations[0])=1", "maxRuns": 100}, "variables": {"good_target_factorisations": {"templateType": "anything", "group": "New thing", "definition": "good_factorisations(target_factorisations)", "description": "Factorisations which don't use $2$ as a factor.
", "name": "good_target_factorisations"}, "smallest_answer": {"templateType": "anything", "group": "New thing", "definition": "if(len(answer)=1,0,min(answer))", "description": "", "name": "smallest_answer"}, "scenarios": {"templateType": "anything", "group": "New thing", "definition": "[[12, [11, 6]], [13, [9]], [15, [8]], [18, [17, 10]], [28, [12]], [31, [16, 25]], [39, [18]], [91, [36]], [93, [50]], [124, [48, 75]], [217, [100]], [403, [144, 225]]]", "description": "Scenarios are picked so that:
\n\n- there are at most two answers
\n- when an answer isn't just $n-1$, no prime greater than 5 and no power greater than 3 is required.
\n- each target has at most two factorisations which don't have a separate factor of 2 (since there's no $n$ such that $\\sigma(n)=2$)
\n- one of the answers is not a prime
\n
\n5 of 12 scenarios have two answers. In 2 of the scenarios, the target is one more than a prime.
\nEach scenario is a structure of the form [target number, [answers]], where $\\sigma(answer) = target$.
", "name": "scenarios"}, "v": {"templateType": "anything", "group": "Ungrouped variables", "definition": "((n1[0])^(n1[1]))*((n2[0])^(n2[1]))", "description": "", "name": "v"}, "f1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][1][0]", "description": "", "name": "f1"}, "n1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][3][0]", "description": "", "name": "n1"}, "answer": {"templateType": "anything", "group": "New thing", "definition": "scenario[1]", "description": "", "name": "answer"}, "d28": {"templateType": "anything", "group": "Divisor data", "definition": "[28,[4,7,0],[0,0],[[3,1],[2,2]]]", "description": "", "name": "d28"}, "d12": {"templateType": "anything", "group": "Divisor data", "definition": "[12,[3,4,1],[0,0],[[2,1],[3,1]]]", "description": "", "name": "d12"}, "d18": {"templateType": "anything", "group": "Divisor data", "definition": "[18,[3,6,1],[0,0],[[2,1],[5,1]]]", "description": "", "name": "d18"}, "n2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][3][1]", "description": "", "name": "n2"}, "target": {"templateType": "anything", "group": "New thing", "definition": "scenario[0]", "description": "", "name": "target"}, "ans1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][1][2]=1,max(v,m-1),v)", "description": "", "name": "ans1"}, "target_one_more_than_a_prime": {"templateType": "anything", "group": "New thing", "definition": "(target-1) in primes", "description": "", "name": "target_one_more_than_a_prime"}, "biggest_answer": {"templateType": "anything", "group": "New thing", "definition": "max(answer)", "description": "", "name": "biggest_answer"}, "f2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][1][1]", "description": "", "name": "f2"}, "d39": {"templateType": "anything", "group": "Divisor data", "definition": "[39,[3,13,0],[0,0],[[2,1],[3,2]]]", "description": "", "name": "d39"}, "inv": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(2|m, ', forgetting those with $2$ as a factor, ',' ')", "description": "", "name": "inv"}, "altf": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][2][0]=0, \n 'There are no other factorizations of $\\\\var{m}$ into powers of prime factors which can give values of $n$.',\n 'Another factorization of $\\\\var{m}$ is given by $\\\\var{m}= \\\\var{d[j][2][0]}\\\\times \\\\var{d[j][2][1]}$, but as $\\\\var{d[j][2][1]}$ does not appear on our table as a possible value of $\\\\sigma$, this does not give a value of $n$'\n)", "description": "", "name": "altf"}, "d91": {"templateType": "anything", "group": "Divisor data", "definition": "[91,[7,13,0],[0,0],[[2,2],[3,2]]]", "description": "", "name": "d91"}, "primes": {"templateType": "anything", "group": "New thing", "definition": "[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]", "description": "", "name": "primes"}, "target_factorisations": {"templateType": "anything", "group": "New thing", "definition": "factorisations(target)", "description": "", "name": "target_factorisations"}, "ans2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][1][2]=1,min(v,m-1),0)", "description": "", "name": "ans2"}, "d124": {"templateType": "anything", "group": "Divisor data", "definition": "[124,[4,31,0],[0,0],[[3,1],[5,2]]]", "description": "", "name": "d124"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[d12,d18,d24,d28,d39,d42,d78,d91,d93,d124,d217,d403]", "description": "Data for the given number
\n[0] is the value of phi
\n", "name": "d"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][0]", "description": "", "name": "m"}, "j": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..11 except 5)", "description": "", "name": "j"}, "d93": {"templateType": "anything", "group": "Divisor data", "definition": "[93,[3,31,0],[0,0],[[2,1],[5,2]]]", "description": "", "name": "d93"}, "biggest_prime": {"templateType": "anything", "group": "New thing", "definition": "max(primes)", "description": "", "name": "biggest_prime"}, "d217": {"templateType": "anything", "group": "Divisor data", "definition": "[217,[7,31,0],[0,0],[[2,2],[5,2]]]", "description": "", "name": "d217"}, "pri": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][1][2]=1,\n 'Note that since $\\\\var{m}-1$ is prime, then $n=\\\\var{m-1}$ is a choice for $n$',\n 'In this case, $\\\\var{m}-1$ is not prime, so $\\\\var{m-1}$ is not a solution. '\n)", "description": "", "name": "pri"}, "scenario": {"templateType": "anything", "group": "New thing", "definition": "random(scenarios)", "description": "", "name": "scenario"}, "d24": {"templateType": "anything", "group": "Divisor data", "definition": "[24,[4,6,1],[3,8],[[3,1],[5,1]]]", "description": "", "name": "d24"}, "second_decomposition": {"templateType": "anything", "group": "New thing", "definition": "if(len(good_target_factorisations)>1,\n if(len(good_target_factorisations[1])>1,true,false),\n false\n)", "description": "", "name": "second_decomposition"}, "d78": {"templateType": "anything", "group": "Divisor data", "definition": "[78,[6,13,0],[3,26],[[5,1],[3,2]]]", "description": "", "name": "d78"}, "d42": {"templateType": "anything", "group": "Divisor data", "definition": "[42,[6,7,1],[3,14],[[5,1],[2,2]]]", "description": "", "name": "d42"}, "d403": {"templateType": "anything", "group": "Divisor data", "definition": "[403,[13,31,0],[0,0],[[3,2],[5,2]]]", "description": "", "name": "d403"}, "af1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][2][0]", "description": "", "name": "af1"}, "af2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][2][1]", "description": "", "name": "af2"}, "inverse_sigma_primes": {"templateType": "anything", "group": "New thing", "definition": "inverse_sigma_prime(good_target_factorisations)", "description": "", "name": "inverse_sigma_primes"}}, "ungrouped_variables": ["af1", "af2", "altf", "ans1", "ans2", "d", "f1", "f2", "inv", "j", "m", "n1", "n2", "pri", "v"], "functions": {"good_factorisations": {"type": "list", "language": "javascript", "definition": "return fs.filter(function(f){ return !f.contains(2)})", "parameters": [["fs", "list"]]}, "factorisations": {"type": "list", "language": "javascript", "definition": "function fns(factors) {\n if(factors.length==0) {\n return [[]];\n }\n var p = factors[0][0];\n var k = factors[0][1];\n if(factors.length>1) {\n var others = Numbas.util.product(factors.slice(1).map(function(f) {\n var out = [];\n var p = f[0];\n var k = f[1];\n for(var i=0;i<=k;i++) {\n out.push([p,i,k-i]);\n }\n return out;\n }));\n } else {\n var others = [[]];\n }\n \n var out = [];\n for(var i=1;i<=k;i++) {\n var t = Math.pow(p,i);\n others.map(function(other) {\n var t2 = t;\n var rest = [];\n other.map(function(f) {\n t2 *= Math.pow(f[0],f[1]);\n if(f[2]>0) {\n rest.push([f[0],f[2]]);\n }\n })\n if(i0});\n\nreturn fns(factors);", "parameters": [["n", "number"]]}, "show_factorisations": {"type": "number", "language": "javascript", "definition": "fs = fs.map(function(f){ return f.join(' \\\\times '); });\nreturn '\\\\begin{align}\\n'+n+' &= '+fs.join('\\\\\\\\ \\n &= ')+'\\n\\\\end{align}';", "parameters": [["n", "number"], ["fs", "list"]]}, "inverse_sigma_prime": {"type": "list", "language": "javascript", "definition": "console.clear();\n\nvar primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997];\nfunction inverse_sigma(n) {\n var out = [];\n for(var i=0;iFind values of $n$ such that $\\sigma(n)=\\var{m}$. There are at most 2.\nIf there are two values of $n$ enter in decreasing order.
\nIf there is only one value for $n$ enter that value in the first answer field and enter 0 in the second field.
\nLargest value for $n = \\;\\;$[[0]]
\nSmallest value for $n=\\;\\;$[[1]] (enter 0 if there is no second value for $n$)
", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "steps": [{"showCorrectAnswer": true, "customName": "", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "useCustomName": false, "prompt": "If $n = p_1^{\\beta_1}p_2^{\\beta_2}\\cdots p_s^{\\beta_s}$ into powers of distinct primes, then we have the sum over all divisors is given by :
\n\\[\\begin{eqnarray*} \\sigma(n)&=& \\sigma(p_1^{\\beta_1})\\times \\sigma(p_1^{\\beta_1}) \\times\\cdots \\times\\sigma(p_s^{\\beta_s})\\\\ &=& \\frac{(p_1^{\\beta_1+1}-1)}{p_1-1}\\times \\frac{(p_2^{\\beta_2+1}-1)}{p_2-1} \\times \\cdots \\times \\frac{(p_m^{\\beta_m+1}-1)}{p_m-1} \\end{eqnarray*} \\]
\nSo for this example we have to examine how $\\var{m}$ can be split into factors corresponding to such a prime decomposition.
\nWe build up a table of values of $\\sigma(q^\\beta)$ for various values of primes $q$ and powers $\\beta$.
\nWe leave out those values of $\\sigma(q^\\beta)$ which are too big for the examples you are given, for example $\\beta \\lt 4$ and for primes $q \\gt 5$ we need not consider any powers of 2 or greater.
\nOther labour saving comments are that if $\\sigma(n)=m$ and $m-1$ is a prime number then we have $\\sigma(m-1)=1+(m-1)=m$ so you have a solution immediately!
\nAlso note that in the following table, $2$ is never a value of $\\sigma(q^{\\beta})$ so any factorization of $m$ which involves $2$ can be ignored.
\n\n\n| $q$ | $q^{\\beta}$ | $\\sigma(q^{\\beta})$ | Value |
|---|
\n\n| $q=2$ | \n$2^1$ | \n$1+2$ | \n$3$ | \n
\n\n | \n$2^2$ | \n$1+2+4$ | \n$7$ | \n
\n\n | \n$2^3$ | \n$1+2+4+8$ | \n$15$ | \n
\n\n | \nToo big! | \n | \n | \n
\n\n| $q=3$ | \n$3^1$ | \n$1+3$ | \n$4$ | \n
\n\n | \n$3^2$ | \n$1+3+9$ | \n$13$ | \n
\n\n | \nToo big! | \n | \n | \n
\n\n| $q=5$ | \n$5^1$ | \n$1+5$ | \n$6$ | \n
\n\n | \n$5^2$ | \n$1+5+25$ | \n$31$ | \n
\n\n | \nToo big! | \n | \n | \n
\n\n
\nWe demonstrate this using the example $\\sigma(n) = 60$. Note that since $60-1=59$ is prime we already have a solution, $n=59$.
\n$60$ can be factorized in several different ways. Most of the factorizations do not correspond to values of $\\sigma(q^\\beta)$ in the table.
\n\\[\\begin{eqnarray*} 60 &=& 1\\times60,\\mbox{ we have a solution corresponding to this, }n=59 \\leftarrow\\\\ 60&=& 2 \\times 30\\mbox{, no solution as 2 is a factor}\\\\ 60&=& 3 \\times 20\\mbox{, no solution as 20 does not appear in the above table}\\\\ 60&=&4 \\times 15.\\mbox{ both 4 and 15 appear in the table, for different primes } 4=\\sigma(3^1),\\;15=\\sigma(2^3) \\leftarrow\\\\ 60&=& 5\\times 12\\mbox{, no solution as neither 5 nor 12 appear in the above table}\\\\ 60&=& 6 \\times 10\\mbox{, no solution as 10 does not appear in the above table}\\\\ 60&=& 2 \\times 3 \\times 10\\mbox{, no solution as 2 is a factor}\\\\ 60&=&2 \\times 5 \\times 6\\mbox{, no solution as 2 is a factor}\\\\ 60&=& 3\\times 4 \\times 5\\mbox{, no solution as 5 does not appear in the table} \\end{eqnarray*} \\]
So we see that we have a solution corresponding to:
\\[\\sigma(n)= 60 = 4 \\times 15 = \\sigma(3^1)\\times \\sigma(2^3)=\\sigma(3 \\times 8)=\\sigma(24)\\]
\nHence $n=24$ is a solution as well as $n=59$.
\nYou can check this as $24$ has divisors, $1,\\;2,\\;3,\\;4,\\;6,\\;8,\\;12,\\;24$ and summing up these gives $60$.
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "type": "information", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "{ans1}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "showFeedbackIcon": true, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "maxValue": "{ans1}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "{ans2}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "showFeedbackIcon": true, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "maxValue": "{ans2}"}], "type": "gapfill", "stepsPenalty": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "statement": "", "tags": ["checked2015", "divisors", "Factorisation", "factorisation", "factorization", "Factors", "factors", "number theory", "Number theory", "prime decomposition", "sigma(n)", "sum of divisors"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": "question.primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]"}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given $m \\in \\mathbb{N}$, find values of $n\\in \\mathbb{N}$ such that $\\sigma(n)=m$.
\nThere are at most two such solutions in this question.
"}, "advice": "First, recall that for a prime $p$, $\\sigma(p^\\alpha) = \\frac{p^{\\alpha+1}-1}{p-1}$, and that $\\sigma$ is mulitplicative.
\nIf $n$ is decomposed into powers of distinct primes, $n = p_1^{\\beta_1}p_2^{\\beta_2}\\cdots p_s^{\\beta_s}$, then the sum of all divisors of $n$ is given by
\n\\begin{align}
\\sigma(n) &= \\sigma(p_1^{\\beta_1})\\times \\sigma(p_2^{\\beta_2})\\times\\cdots \\times\\sigma(p_s^{\\beta_s}) \\\\[0.5em]
&= \\frac{(p_1^{\\beta_1+1}-1)}{p_1-1}\\times \\frac{(p_2^{\\beta_2+1}-1)}{p_2-1} \\times \\cdots \\times \\frac{(p_m^{\\beta_m+1}-1)}{p_m-1}
\\end{align}
\nSo for this example we have to examine how $\\var{target}$ can be split into factors corresponding to such a prime decomposition.
\n$\\var{target}$ can be factorised in the following ways:
\n$\\var{latex(show_factorisations(target,target_factorisations))}$
\nNote that there is no $n$ such that $\\sigma(n) = 2$, so we can ignore the factorisations which involve $2$.
\nAlso note that if $\\sigma(n)=m$, and $m-1$ is a prime number, then we have $\\sigma(m-1)=1+(m-1)=m$ so we have a solution immediately!
\nSince $\\var{target}-1 = \\var{target-1}$ is prime, $n = \\var{target-1}$ is a solution.
\nIn this case, $\\var{m}-1$ is not prime, so $\\var{m-1}$ is not a solution.
\nNow, we build up a table of values of $\\sigma(q^\\beta)$ for various primes $q$ and powers $\\beta$, stopping when $\\sigma(q^{\\beta})$ is bigger than any of the factors in our list.
\n\n\n| $q$ | $q^{\\beta}$ | $\\sigma(q^{\\beta})$ | Value |
|---|
\n\n\n\n| $q=2$ | \n$2^1$ | \n$1+2$ | \n$3$ | \n
\n\n | \n$2^2$ | \n$1+2+4$ | \n$7$ | \n
\n\n | \n$2^3$ | \n$1+2+4+8$ | \n$15$ | \n
\n\n | \nToo big! | \n | \n | \n
\n\n| $q=3$ | \n$3^1$ | \n$1+3$ | \n$4$ | \n
\n\n | \n$3^2$ | \n$1+3+9$ | \n$13$ | \n
\n\n | \nToo big! | \n | \n | \n
\n\n| $q=5$ | \n$5^1$ | \n$1+5$ | \n$6$ | \n
\n\n | \n$5^2$ | \n$1+5+25$ | \n$31$ | \n
\n\n | \nToo big! | \n | \n | \n
\n\n
\n\n
We see from the table that
\n
\\begin{align}
\\var{target} &= \\var{good_target_factorisations[0][0]} \\times \\var{good_target_factorisations[0][1]} \\\\
&= \\sigma(\\var{inverse_sigma_primes[0][0]}^\\var{inverse_sigma_primes[0][1]}) \\times \\sigma(\\var{inverse_sigma_primes[1][0]}^\\var{inverse_sigma_primes[1][1]}) \\\\
&= \\sigma(\\var{answer[0]})
\\end{align}
\n
So $n=\\var{v}$ is a solution.
\n
Find the smallest natural number $n$ with exactly $\\tau(n)=\\var{t[j]}$ divisors.
\n \n \n \n Smallest=[[0]]
\n \n \n \n What is the second smallest?
\n \n \n \n Second smallest=[[1]]
\n \n \n", "steps": [{"type": "information", "prompt": "\n \n \n Recall that if $n=p_1^{\\beta_1}\\times p_2^{\\beta_2}\\times \\cdots \\times p_m^{\\beta_m}$ is the prime factorization of $n$, then the number of divisors is given by:
\n \n \n \n $\\tau(n)=(\\beta_1+1)\\times (\\beta_2+1) \\times\\cdots \\times (\\beta_m+1)$
\n \n \n \n Hence if $\\tau(n)= \\var{ta}$, we factorize $\\var{ta}$ to look for possible values of the $\\beta_j$
\n \n \n \n In this example there are two possible factorizations.
\n \n \n", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "MAS3214", "number of divisors", "number theory", "tau(n)"], "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 the smallest natural number $n \\in \\mathbb{N}$ with $\\tau(n)=m$ divisors.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n \n \n Recall that if $n=p_1^{\\beta_1}\\times p_2^{\\beta_2}\\times \\cdots \\times p_m^{\\beta_m}$ is the prime factorization of $n$, then the number of divisors is given by:
\n \n \n \n $\\tau(n)=(\\beta_1+1)\\times (\\beta_2+1) \\times\\cdots \\times (\\beta_m+1)$
\n \n \n \n Hence if $\\tau(n)= \\var{ta}$, we factorize $\\var{ta}$ to look for possible values of the $\\beta_j$
\n \n \n \n Now there are two possible factorizations i.e.
\n \n \n \n Factorization 1. $\\var{ta}= \\var{ta}$
\n \n \n \n Factorization 2. $\\var{ta}= \\var{fact[0]+1}\\times\\var{fact[1]+1}$
\n \n \n \n Factorization 1:
\n \n \n \n We have only one prime factor and $n = p_1^{\\beta_1} $ for some prime $p$.
\n \n \n \n In this case we have $\\tau(n)= 1+\\beta_1 =\\var{ta} \\Rightarrow \\beta_1 = \\var{ta-1}$
\n \n \n \n Hence possible values for $n$ are $2^{\\var{ta-1}}$ and $3^{\\var{ta-1}}$.
\n \n \n \n No need to look at any more powers of primes as we want the smallest 2 and all other prime powers are greater than these two.
\n \n \n \n But note that these may not be the smallest values of $n$ as we have now to look at case 2.
\n \n \n \n Factorization 2:
\n \n \n \n In this case we have two distinct prime factors as
\n \n \n \n \\[n=p_1^{\\beta_1}p_2^{\\beta_2} \\Rightarrow \\tau(n)=(1+\\beta_1)(1+\\beta_2)= \\var{fact[0]+1}\\times\\var{fact[1]+1} \\Rightarrow \\beta_1=\\var{fact[0]},\\;\\;\\beta_2=\\var{fact[1]}\\]
\n \n \n \n So now we look at the possibilities.
\n \n \n \n There is no point in looking at any primes greater than 5 as combinations of powers of the primes 2,3 and 5 will give the two smallest values of $n$.
\n \n \n \n Also the pair of primes 3, 5 cannot give one of the smallest two values as $3^{\\beta_1}5^{\\beta_2}$ is greater than both $2^{\\beta_1}5^{\\beta_2}$ and $2^{\\beta_1}3^{\\beta_2}$
\n \n \n \n Look at the following table:
\n \n \n \n \n \n | Powers of Prime Numbers |
|---|
\n \n | Prime Number Pairs | $(\\var{fact[0]},\\var{fact[1]})$ | $(\\var{fact[1]},\\var{fact[0]})$ |
|---|
\n \n | $(2,3)$ | $2^{\\var{fact[0]}}\\times 3^{\\var{fact[1]}}=\\var{2^fact[0]* 3^fact[1]}$ | $2^{\\var{fact[1]}}\\times 3^{\\var{fact[0]}}=\\var{2^fact[1]* 3^fact[0]}$ |
|---|
\n \n | $(2,5)$ | $2^{\\var{fact[0]}}\\times 5^{\\var{fact[1]}}=\\var{2^fact[0]* 5^fact[1]}$ | $2^{\\var{fact[1]}}\\times 5^{\\var{fact[0]}}=\\var{2^fact[1]* 5^fact[0]}$ |
|---|
\n \n
\n \n \n \n We see from this table for Factorization 2 and from Factorization 1 that the two smallest values for $n$ are $\\var{poss[0]}$ and $\\var{poss[1]}$.
\n \n \n"}], "name": "", "pickQuestions": 0}], "name": "Number theory and cryptography", "showQuestionGroupNames": false, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Questions used in a university course titled \"Number theory and cryptography\""}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "extensions": ["stats"], "custom_part_types": [], "resources": []}