// Numbas version: finer_feedback_settings
{"name": "Solve congruence in given range", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"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": "<p>Find all the solutions in the range $0 \\leq x \\lt \\var{sb}$ of the following equation by answering the following questions :<br/>\\[ \\var{sa}x \\equiv \\var{r}\\mod\\var{sb}\\]</p>\n<p>Note that it is advisable to read Steps the first one or two times you try this exercise.</p>\n<p>Number of solutions $\\;=\\;$ [[0]]</p>\n<p>What is the difference between successive solutions?</p>\n<p>Distance $\\;=\\;$ [[1]]</p>\n<p>Input here the least solution in the range $0 \\leq x \\lt \\var{sb}$</p>\n<p>$x=\\;\\;$[[2]]</p>\n<p>Input here the greatest solution in the range $0 \\leq x \\lt \\var{sb}$</p>\n<p>$x=\\;\\;$[[3]]</p>", "steps": [{"type": "information", "prompt": "\n  \n  \n  <p>Given an equation $ax\\;\\equiv\\;r \\;\\mod\\; n$ then the first step is to see if $a$ and $n$ are coprime.</p>\n  \n  \n  \n  <p>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.</p>\n  \n  \n  \n  <p>However if not coprime with $\\operatorname{gcd}(a,n) = \\alpha \\gt 1$ then the Extended Euclidean Algorithm gives:<br/>\\[\\lambda a+\\mu n = \\alpha,\\;\\;\\lambda,\\;\\mu \\in \\mathbb{Z}.\\]</p>\n  \n  \n  \n  <p>Now if $\\alpha | r$ and $r=\\beta \\times \\alpha$ then on multiplying the last equation by $\\beta$ we get:<br/>\\[\\lambda \\times \\beta a + \\mu \\times \\beta n=\\alpha \\times \\beta = r\\]</p>\n  \n  \n  \n  <p>Hence we see that $x= \\lambda \\times \\beta \\mod \\;n$ is a solution of our original equation.</p>\n  \n  \n  \n  <p>Also note that we can get other values of $\\lambda$ and $\\mu$ for $\\lambda a+\\mu n = \\alpha $ :<br/>\\[\\left(\\lambda+i\\frac{n}{\\alpha}\\right) a+\\left(\\mu-i\\frac{a}{\\alpha}\\right) n = \\alpha,\\;\\;\\;i=0,1,\\ldots,\\alpha-1\\]</p>\n  \n  \n  \n  <p>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$.</p>\n  \n  \n  \n  <p>At first sight we could multiply by $\\beta$ to get other solutions to our original equation, just as we did above.</p>\n  \n  \n  \n  <p>But if we look at  $\\displaystyle{ \\left(\\lambda+i\\frac{n}{\\alpha}\\right)\\beta = \\lambda \\beta+i\\frac{n\\beta}{\\alpha}}$ then if</p>\n  \n  \n  \n  <p>$\\operatorname{gcd}(\\alpha,\\beta) \\gt 1$ then there will be less than $\\alpha$ distinct values $\\mod\\;n$ for the solution.</p>\n  \n  \n  \n  <p>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$.</p>\n  \n  \n  \n  <p>In this case we will get $\\alpha_1$ distinct solutions $\\mod\\;n$ rather than $\\alpha$ for $i=0,1\\dots,\\alpha_1-1$.</p>\n  \n  \n  \n  <p>For example, consider \\[\\displaystyle{4x\\; \\equiv\\;8 \\mod\\; 12}\\]</p>\n  \n  \n  \n  <p>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$.</p>\n  \n  \n  \n  <p>Note that $\\operatorname{gcd}(\\alpha,\\beta) = 2$ and $\\frac{\\beta}{\\alpha}=\\frac{1}{2}$ so $\\alpha_1=2$.</p>\n  \n  \n  \n  <p>So one solution is $\\lambda \\times \\beta = 10 \\times 2 = 20 = 8 \\mod 12$.</p>\n  \n  \n  \n  <p>If we try to form other solutions we have:</p>\n  \n  \n  \n  <p>$\\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$</p>\n  \n  \n  \n  <p>given by $8$ when $i=0$ and $14=2 \\mod 12$ when $i=1$. When $i=2$ we get $8 \\mod 12 $ again.</p>\n  \n  \n  \n  <p>However, if the example you are trying has $\\operatorname{gcd}(\\alpha,\\beta)=1$ then we will get $\\alpha$ distinct solutions.</p>\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}], "name": "Solve congruence in given range", "functions": {"nco": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)<m or 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=$('<table border=\"1\">');\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('<tr><td>$\\\\var{'+a+'}$</td><td>$\\\\var{'+b+'}$</td><td>$'+ disp(c1+'a+'+c2+'b')+'$</td><td>$'+ disp(d1+'a+'+d2+'b')+'$</td></tr>');}\n  else {\n  if(a<b){\n  var fl=Math.floor(b/a);\n  table.append('<tr><td>$\\\\var{'+a+'}$</td><td>$\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$</td><td>$'+ disp(c1+'a+'+c2+'b')+'$</td><td>$'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$</td></tr>');\n  mdescextgcd(a,b%a,c1,c2,d1-fl*c1,d2-fl*c2);\n  }\n  else {\nvar fl1=Math.floor(a/b);\ntable.append('<tr><td>$\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$</td><td>$\\\\var{'+b+'}$</td><td>$'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$</td><td>$'+ disp(d1+'a+'+d2+'b')+'$</td></tr>');\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": "<p>Solving an equation of the form $ax \\equiv\\;b\\;\\textrm{mod}\\;n$ &nbsp;where $\\operatorname{gcd}(a,n)|r$. In this case we can find all solutions. The user is asked for the two greatest.</p>"}, "advice": "<p>This explanation assumes that you have read the Steps section of this exercise.</p>\n<p>The first thing to do is to see if $\\var{sa}$ and $\\var{sb}$ are coprime or not.</p>\n<p>If 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.</p>\n<p>But 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</p>\n<p>{mdescextGCD(sa,sb,1,0,0,1)}</p>\n<p>So we see that $\\simplify[all,!collectNumbers,!noleadingMinus]{{csa}*{sa}+{csb}*{sb}={al}}$</p>\n<p>But since $\\var{al}$ divides $\\var{r}$ we have that on multiplying this last equation by $\\var{be}$ that</p>\n<p>\\[\\simplify[std]{{sa}*{be*csa}+{sb}*{be*csb}={al}*{be}={r}}\\]</p>\n<p>Hence we see that $x=\\var{be*csa}\\equiv\\;\\var{ans3}\\;\\mod \\;\\var{sb}$ is a solution.</p>\n<p>There 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}\\]</p>\n<p>To see if we get $\\var{al}$ distinct solutions we check to see if $\\var{be}$ and $\\var{al}$ are coprime, and they clearly are.</p>\n<p>Hence we get $\\var{al}$ solutions, and the difference between successive solutions is:</p>\n<p>\\[\\frac{\\var{sb}\\times \\var{be}}{\\var{al}} = \\var{diff}\\;\\mod\\;\\var{sb} \\]</p>\n<p>Given 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}$.</p>", "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}