Modular Arithmetic: Greatest Common Divisor

Error

There was an error loading the page.

Contributors

Feedback

From users who are members of Discrete Mathematics :

Daniel Mansfield

said

Ready to use

7 years, 8 months ago

From users who are not members of Discrete Mathematics :

Oscar Herrera

said

Ready to use

4 years, 10 months ago

History

○

Oscar Herrera 4 years, 10 months ago

Gave some feedback: Ready to use

○

Daniel Mansfield 7 years, 8 months ago

Gave some feedback: Ready to use

○

Daniel Mansfield 7 years, 8 months ago

Published this.

○

Daniel Mansfield 7 years, 8 months ago

Created this.

There is only one version of this question that you have access to.

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

Question statement

A number $n$ divides $a$ when $a = nq$ for some $q$ .

Any number which divides both $a$ and $b$ is called a common divisor of $a$ and $b$ , the largest common divisor is called the greatest common divisor and is denoted $\gcd(a,b)$ .

Give any introductory information the student needs.

			Name	Type	Generated Value

a	integer	8
b	integer	6
gcd	integer	16
a1	integer	16
a2	integer	0
c	rational	9
big	integer	150

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(2..9 except gcd)

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`

← Depends on:

This variable doesn't seem to be used anywhere.

Advice

Every number divides zero, so the largest number to divide $\var{a1}$ is the greatest common divisor of $0$ and $\var{a1}$ . This means that $\gcd(\var{a1},0) = \var{a1}$ .

The Euclidian Algorithm presented here is a variation on the usual presentation. Another common method keeps track of the quotients:

$\var{gcd*(1+b*(1+a))} = \var{b}\times (\var{gcd*(1+a)}) + \var{a1}$

$\var{gcd*(1+a)} = \var{gcd*(1+a)/a1}\times (\var{a1}) + 0$

to write the $\gcd$ in the form of Bézout's identity

$\var{gcd*(1+b*(1+a))} - \var{b}\times (\var{gcd*(1+a)}) = \var{a1}$ .

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?
Number entry
Number entry		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
Information only

This question is used in the following exams:

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Oscar Herrera 4 years, 10 months ago

Daniel Mansfield 7 years, 8 months ago

Daniel Mansfield 7 years, 8 months ago

Daniel Mansfield 7 years, 8 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Number entry

Advanced settings

Loading...

Error

Modular Arithmetic: Greatest Common Divisor

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Oscar Herrera 4 years, 10 months ago

Daniel Mansfield 7 years, 8 months ago

Daniel Mansfield 7 years, 8 months ago

Daniel Mansfield 7 years, 8 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Number entry

Advanced settings

Generated value: `integer`