// Numbas version: finer_feedback_settings
{"name": "Blathnaid's copy of Solve three congruences using Chinese Remainder Theorem", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"ungrouped_variables": ["pans", "na", "nb", "nc", "ea", "rc", "ec", "n", "ra", "rb", "ans", "sc", "sb", "sa", "eb"], "question_groups": [{"pickQuestions": 0, "name": "", "pickingStrategy": "all-ordered", "questions": []}], "statement": "", "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 ", "variablesTest": {"maxRuns": 100, "condition": ""}, "tags": ["checked2015", "Chinese Remainder Theorem", "congruences", "coprime", "euclidean algorithm", "gcd", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving equations", "Solving equations"], "preamble": {"css": "", "js": ""}, "name": "Blathnaid's copy of Solve three congruences using Chinese Remainder Theorem", "parts": [{"stepsPenalty": 0, "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 ", "marks": 0, "gaps": [{"maxValue": "{ans}", "minValue": "{ans}", "scripts": {}, "correctAnswerFraction": false, "allowFractions": false, "showPrecisionHint": false, "marks": 4, "showCorrectAnswer": true, "type": "numberentry"}], "steps": [{"showCorrectAnswer": true, "marks": 0, "scripts": {}, "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 ", "type": "information"}], "scripts": {}, "showCorrectAnswer": true, "type": "gapfill"}], "showQuestionGroupNames": false, "metadata": {"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$
", "notes": "", "licence": "Creative Commons Attribution 4.0 International"}, "functions": {"mdescext1gcd": {"parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]], "type": "string", "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 ", "language": "jme"}, "chcop": {"parameters": [["a", "number"], ["b", "number"], ["p", "number"], ["q", "number"]], "type": "number", "definition": "if(gcd(a,b)=1,b,chcop(a,random(p..q),p,q))", "language": "jme"}, "testgcd3": {"parameters": [["a", "number"], ["b", "number"], ["c", "number"]], "type": "number", "definition": "max(max(gcd(a,b),gcd(a,c)),gcd(b,c))", "language": "jme"}, "mdescextgcd": {"parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"], ["t", "number"]], "type": "string", "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 ", "language": "jme"}, "chcop3": {"parameters": [["a", "number"], ["b", "number"], ["c", "number"], ["p", "number"], ["q", "number"]], "type": "number", "definition": "if(testgcd3(a,b,c)=1,c,chcop3(a,b,random(p..q),p,q))", "language": "jme"}, "extendedgcd1": {"parameters": [["a", "number"], ["b", "number"]], "type": "number", "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 ", "language": "jme"}, "extendedgcd2": {"parameters": [["a", "number"], ["b", "number"]], "type": "number", "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 ", "language": "jme"}}, "variables": {"nc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb", "name": "nc", "description": ""}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop3(sa,sb,sb,2,sa-1)", "name": "sc", "description": ""}, "na": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sb*sc", "name": "na", "description": ""}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "pans", "name": "ans", "description": ""}, "ec": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,nc)*nc", "name": "ec", "description": ""}, "rb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..sb-1)", "name": "rb", "description": ""}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "na*sa", "name": "n", "description": ""}, "rc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..sc-1)", "name": "rc", "description": ""}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(12..20)", "name": "sb", "description": ""}, "eb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sb,nb)*nb", "name": "eb", "description": ""}, "ea": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,na)*na", "name": "ea", "description": ""}, "ra": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sa-1)", "name": "ra", "description": ""}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,8,sb-1)", "name": "sa", "description": ""}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ra*ea+rb*eb+rc*ec,n)", "name": "pans", "description": ""}, "nb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sc", "name": "nb", "description": ""}}, "variable_groups": [], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "type": "question", "contributors": [{"name": "Blathnaid Sheridan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/447/"}]}]}], "contributors": [{"name": "Blathnaid Sheridan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/447/"}]}