Blathnaid's copy of Greatest common divisor and Bézout's algorithm

Error

There was an error loading the page.

Contributors

History

○

Blathnaid Sheridan 5 years, 6 months ago

Created this as a copy of Greatest common divisor and Bézout's algorithm.

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	-3
diff	number	25
b1	integer	7800
b	integer	7800
n	number	1872
t	integer	4
a1	integer	10296
bb	integer	7800
c	integer	24
describeleast	string	So, the first positive solutio
a	integer	10296
least	number	7
d	number	312
k	integer	6

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`

-3

← Depends on:

→ Used by:

describeleast
least

This variable doesn't seem to be used anywhere.

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

This question is used in the following exam:

Paul's copy of CMPU2012-Number Theory by Paul Molloy in Paul's workspace.

Loading...

Error

Blathnaid's copy of Greatest common divisor and Bézout's algorithm

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Blathnaid Sheridan 5 years, 6 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

Blathnaid's copy of Greatest common divisor and Bézout's algorithm

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Blathnaid Sheridan 5 years, 6 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`