Greatest common divisor and Bézout's algorithm

Error

There was an error loading the page.

Contributors

Christian Lawson-Perfect

Feedback

From users who are members of Christian's workspace :

Christian Lawson-Perfect

said

Ready to use

10 years ago

History

○

Christian Lawson-Perfect 10 years ago

Gave some feedback: Ready to use

○

Christian Lawson-Perfect 12 years, 2 months ago

Created this.

Name	Status	Author	Last Modified
Greatest common divisor and Bézout's algorithm	Ready to use	Christian Lawson-Perfect	02/12/2020 15:42
Blathnaid's copy of Greatest common divisor and Bézout's algorithm	draft	Blathnaid Sheridan	02/12/2020 15:42

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

Question statement

Give any introductory information the student needs.

			Name	Type	Generated Value

s	integer	-2
diff	number	13
b1	integer	5304
b	integer	5304
n	number	2856
t	integer	3
a1	integer	7752
bb	integer	5304
c	integer	8
describeleast	string	So, the first positive solutio
a	integer	7752
least	number	12
d	number	408
k	integer	7

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
extendedgcd1(max(a,b),min(a,b))

JME function reference

Description

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`

-2

← Depends on:

→ Used by:

describeleast
least

Advice
"Part a)" → "Gap 1." - Minimum accepted value
"Part a)" → "Gap 1." - Maximum accepted value

Parts

Part a) Gap-fill
1. Gap Gap 0. Number entry
  Add
2. Gap Gap 1. Number entry
  Add
3. Gap Gap 2. Number entry
  Add
Part b) Gap-fill
1. Gap Gap 0. Number entry
  Add
2. Gap Gap 1. Number entry
  Add

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 = \phantom{{}}$ Gap 0.

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

$\var{a}s+\var{b}t = d$

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

Advice

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}

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
Number entry
Number entry		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

This question is used in the following exams:

Loading...

Error

Greatest common divisor and Bézout's algorithm

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Christian Lawson-Perfect 10 years ago

Christian Lawson-Perfect 12 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

a)

b)

First Step

Lemma

Finding a solution

Loading...

Error

Greatest common divisor and Bézout's algorithm

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Christian Lawson-Perfect 10 years ago

Christian Lawson-Perfect 12 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

a)

b)

First Step

Lemma

Finding a solution

Generated value: `integer`