Blathnaid's copy of Use Bézout's algorithm to solve $as + bt = \gcd(a,b)$,

Error

There was an error loading the page.

Contributors

History

○

Blathnaid Sheridan 6 years, 7 months ago

Created this as a copy of Use Bézout's algorithm to solve

$as + bt = \gcd(a,b)$ , .

Name	Status	Author	Last Modified
Use Bézout's algorithm to solve $as + bt = \gcd(a,b)$ ,	Ready to use	Newcastle University Mathematics and Statistics	02/12/2020 15:42
Blathnaid's copy of Use Bézout's algorithm to solve $as + bt = \gcd(a,b)$ ,	draft	Blathnaid Sheridan	02/12/2020 15:42

There are 3 other versions that do you not have access to.

Question statement

Give any introductory information the student needs.

			Name	Type	Generated Value

g	integer	12
num_lines	integer	4
numbers	list	[ 40596, 9888 ]
a	number	40596
b	number	9888

			Name	Type	Generated Value

d	number	12
diff	number	824
s	integer	-161
t	integer	661
multiple	number	1
show_diff	integer	799

			Name	Type	Generated Value

			sval	number	663
			tval	number	-2722

			Name	Type	Generated Value

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(1..20)

JME function reference

Description

GCD of a and b

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

→ Used by:

numbers

This variable doesn't seem to be used anywhere.

Parts

Part a) Gap-fill
1. Gap Number entry
  Add
Part b) Gap-fill
1. Gap Gap 0. Number entry
  Add
2. Gap Gap 1. Number entry
  Add
1. Step Information only

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

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

$d =$ Unnamed gap

Advice

a)

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

{describegcd(a,b)}

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

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_1$ and $t_1$ such that

$\var{a}s_1+\var{b}t_1= \var{d}$

In this case we find:

{describebezout(a,b)}

So we obtain values $s_1 = \var{s}$ and $t_1 = \var{t}$ .

We see that $0 \le s_1 \le \var{show_diff-1}$ and so meets our requirement and we have $s=\var{s}$ , $t=\var{t}$ .

We see that $s_1$ does not meet the requirement that $0 \le s_1 \le \var{show_diff-1}$ .

Note that if $(s,t)$ is a solution to $\simplify{{a}s + {b}t = {d}}$ , then $(\simplify[]{s + lambda*({b}/{d})}, \simplify[]{t + lambda*({-a}/{d})})$ is also a solution.

So we have to add a multiple of $\frac{\var{b}}{\var{d}}=\var{b/d}$ to $s_1$ and the same multiple of $-\frac{\var{a}}{\var{d}} = -\var{a/d}$ to $t_1$ .

We see that the multiple is $\var{multiple}$ and we have:

$\begin{align} s =\var{s} + \var{multiple}\times \var{b/d} &= \var{sval}, \\ t =\var{t} - \var{multiple}\times \var{a/d} &= \var{tval}. \end{align}$

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Gap-fill
Gap-fill		Hasn't run yet
Number entry
Number entry		Hasn't run yet
Gap-fill
Gap-fill		Hasn't run yet
Number entry
Number entry		Hasn't run yet
Number entry
Number entry		Hasn't run yet
Information only

This question is not used in any exams.

Loading...

Error

Blathnaid's copy of Use Bézout's algorithm to solve $as + bt = \gcd(a,b)$ ,

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Blathnaid Sheridan 6 years, 7 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

a)

b)

Loading...

Error

Blathnaid's copy of Use Bézout's algorithm to solve as+bt=gcd(a,b)as + bt = \gcd(a,b),

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Blathnaid Sheridan 6 years, 7 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

a)

b)

Blathnaid's copy of Use Bézout's algorithm to solve $as + bt = \gcd(a,b)$ ,

Generated value: `integer`