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

Error

There was an error loading the page.

Contributors

Newcastle University Mathematics and Statistics

Feedback

From users who are not members of Content created by Newcastle University :

Ida Synnøve Lohne	said	Ready to use	6 years, 5 months ago
Bill Foster	said	Ready to use	6 years, 5 months ago

History

○

Ida Synnøve Lohne 6 years, 5 months ago

Gave some feedback: Ready to use

○

Bill Foster 6 years, 5 months ago

Gave some feedback: Ready to use

○

Newcastle University Mathematics and Statistics 9 years, 3 months ago

Created this.

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	7
num_lines	integer	5
numbers	list	[ 136850, 21161 ]
a	number	136850
b	number	21161

			Name	Type	Generated Value

d	number	7
diff	number	3023
s	integer	319
t	integer	-2063
multiple	number	0
show_diff	integer	2815

			Name	Type	Generated Value

			sval	number	319
			tval	number	-2063

			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`

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 used in the following exams:

Loading...

Error

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

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Ida Synnøve Lohne 6 years, 5 months ago

Bill Foster 6 years, 5 months ago

Newcastle University Mathematics and Statistics 9 years, 3 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

a)

b)

Loading...

Error

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

Feedback

History

Comment

Checkpoint description

Ida Synnøve Lohne 6 years, 5 months ago

Bill Foster 6 years, 5 months ago

Newcastle University Mathematics and Statistics 9 years, 3 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

a)

b)

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

Generated value: `integer`