// Numbas version: exam_results_page_options {"name": "Blathnaid's copy of Greatest common divisor and B\u00e9zout's algorithm", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Blathnaid's copy of Greatest common divisor and B\u00e9zout's algorithm", "functions": {"randompow": {"type": "number", "definition": "\n\n\nif(n>0,\n\nrandom(2,3,5,7,11,13,17,19,23)*randompow(n-1),\n\n1)\n\n\n ", "language": "jme", "parameters": [["n", "number"]]}, "describegcd": {"type": "html", "definition": "var table = $('');\nfunction describegcd(a,b) {\nif(a');\nreturn describegcd(b,a);\n}\n\nif(a%b==0) {\ntable.append('');\n}\nelse {\ntable.append('');\ndescribegcd(b,a%b);\n}\n}\ndescribegcd(a,b);\nreturn table;", "language": "javascript", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd1": {"type": "number", "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n ", "language": "jme", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "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 ", "language": "jme", "parameters": [["a", "number"], ["b", "number"]]}, "describebezout": {"type": "html", "definition": "var list = $('

$'+old_r+' = '+expr+'$

Find $d = \\operatorname{gcd}(\\var{a},\\var{b})$, the greatest common divisor of $\\var{a}$ and $\\var{b}$:

$d = \\phantom{{}}$[[0]]

Now find integers $s$ and $t$ such that:

\\[\\var{a}s+\\var{b}t = d\\]

$s = \\phantom{{}}$[[1]] $, t = \\phantom{{}}$[[2]]$.$

Find all solutions $x$ of the following congruence:

\\[\\var{a}x \\equiv \\var{n} \\mod \\var{b} \\]

The least solution $x$ such that $0 \\lt x \\lt \\var{b}$ is: [[0]]

Given two numbers, find the gcd, then use Bézout's algorithm to find $s$ and $t$ such that $as+bt=\\operatorname{gcd}(a,b)$. Finally, find all solutions of an equation $\\mod b$.

a)

On applying the standard method for finding the $\\operatorname{gcd}$ of two numbers we have the following sequence:

{describegcd(a,b)}

The last non-zero remainder is $\\var{d}$, so this is the $\\operatorname{gcd}$ of $\\var{a}$ and $\\var{b}$.

Now work backwards through those steps, rearranging them to find the remainders as linear combinations of the other numbers.

When you reach the last line you will have found $s$ and $t$ such that
\\[\\var{a}s+\\var{b}t = \\var{d}\\]

{describebezout(a,b)}

So $s = \\var{s}$ and $t = \\var{t}$.

b)

First Step

We would like to find all the solutions $x$ of the equation
\\[\\var{a}x \\equiv \\var{n} \\mod \\var{b}.\\]

In order to solve such an equation first determine if there is a solution at all.

Lemma

An equation of the form $ax \\equiv n \\mod b$ has a solution if and only if $\\operatorname{gcd}(a,b)|n$.

So the first task is to find $\\operatorname{gcd}(a,b)$ and see if it divides $n$. If not, there is no solution.

In the first part, we found that $d = \\operatorname{gcd}(\\var{a},\\var{b}) = \\var{d}$.

$\\var{n} = \\var{d} \\times \\var{k}$, so the equation $\\var{a}x \\equiv \\var{n} \\mod \\var{b}$ has a solution.

Finding a solution

Note that because $d|n$, then $n=kd$ for some integer $k$.

In order to find a solution of $x$ go back to the first part and use the integers $s$ and $t$ such that

\\[ \\var{a}s + \\var{b}t = d. \\]

If we multiply both sides of this equation by $k$ we find that

\\[ \\var{a}ks + \\var{b}kt = kd = n, \\]

and by taking both sides modulo $\\var{b}$ we see that

\\[ \\var{a}ks \\equiv n \\mod \\var{b}. \\]

So $x = ks = \\var{k*s}$ is a solution of the equation.

The difference between successive terms is $\\frac{\\var{b}}{\\var{d}} = \\var{diff}$.

{describeLeast}

First of all, the biggest number needs to go first:	$\\\\operatorname{gcd}(\\\\var{'+a+'},\\\\var{'+b+'}) = \\\\operatorname{gcd}(\\\\var{'+b+'},\\\\var{'+a+'}), $
Finally, $\\\\var{'+b+'}$ divides into $\\\\var{'+a+'}$ exactly $\\\\var{'+a/b+'}$ times:	$\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+a/b+'}.$
Divide $\\\\var{'+a+'}$ by $\\\\var{'+b+'}$ with remainder $\\\\var{'+(a%b)+'}$:	$\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+Math.floor(a/b)+'} + \\\\var{'+(a%b)+'},$