Solve three congruences using Chinese Remainder Theorem

Error

There was an error loading the page.

Contributors

Newcastle University Mathematics and Statistics

History

○

Newcastle University Mathematics and Statistics 9 years, 2 months ago

Created this.

Name	Status	Author	Last Modified
Solve three congruences using Chinese Remainder Theorem	draft	Newcastle University Mathematics and Statistics	20/11/2019 14:51
Blathnaid's copy of Solve three congruences using Chinese Remainder Theorem	draft	Blathnaid Sheridan	11/05/2018 12:11
Blathnaid's copy of Solve three congruences using Chinese Remainder Theorem	draft	Blathnaid Sheridan	18/11/2019 13:17

There is one other version that you do not have access to.

Question statement

Give any introductory information the student needs.

			Name	Type	Generated Value

pans	number	1417
na	number	133
nb	number	126
nc	number	342
ea	number	-665
rc	integer	3
ec	number	-342
n	number	2394
ra	integer	13
rb	integer	11
ans	number	1417
sc	number	7
sb	integer	19
sa	number	18
eb	number	1008

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
mod(ra*ea+rb*eb+rc*ec,n)

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: `number`

1417

← Depends on:

→ Used by:

This variable doesn't seem to be used anywhere.

Parts

Gap-fill
1. Gap 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.

Solve the following simultaneous congruences:

$\begin{eqnarray*} x\;&\equiv&\;\var{ra}\;&\mod&\;\var{sa}\\ \\ x\;&\equiv&\;\var{rb}\;&\mod&\;\var{sb}\\ \\ x\;&\equiv&\;\var{rc}\;&\mod&\;\var{sc} \end{eqnarray*}$

$x=\;\;$ Unnamed gap

Your value of $x$ should satisfy $0 \leq x \lt \var{n}$

Steps gives you information on the Chinese Remainder Theorem and the steps you need to take to solve the congruences.

Advice

Using the notation in Steps we have:

1) $n_1=\var{sa},\;n_2=\var{sb},\;n_3=\var{sc}$ are coprime as they have no factors in common.
$n=n_1n_2n_3=\var{n}$

2)
$N_1=\var{sb}\times \var{sc}=\var{na},\; N_2=\var{sa}\times \var{sc}=\var{nb},\;N_3=\var{sa}\times \var{sb}=\var{nc}$

Using the Extended Euclidean Algorithm for $N_1=\var{na}$ and $n_1=\var{sa}$ we find:

$\simplify[std]{{extendedgcd2(sa,na)}* {na} +{extendedgcd1(sa,na)}*{sa}=1} \Rightarrow E_1=\var{extendedgcd2(sa,na)}\times \var{na}=\var{ea}$
Using the Extended Euclidean Algorithm for

$N_2=\var{nb}$ and

$n_2=\var{sb}$ we find:

$\simplify[std]{{extendedgcd2(sb,nb)}* {nb} +{extendedgcd1(sb,nb)}*{sb}=1} \Rightarrow E_2=\var{extendedgcd2(sb,nb)}\times \var{nb}=\var{eb}$
Using the Extended Euclidean Algorithm for

$N_3=\var{nc}$ and

$n_3=\var{sc}$ we find:

$\simplify[std]{{extendedgcd2(sc,nc)}* {nc} +{extendedgcd1(sc,nc)}*{sc}=1} \Rightarrow E_3=\var{extendedgcd2(sc,nc)}\times \var{nc}=\var{ec}$
4)
Then the general solution is:

$\begin{eqnarray*} x&=& a_1 E_1+a_2 E_2+a_3 E_3\;\mod\;n\\ &=& \simplify[std]{{ra}*{ea}+{rb}*{eb}+{rc}*{ec}}\;\mod\;\var{n}\\ &=&\var{ra*ea+rb*eb+rc*ec}\;\mod\;\var{n}\\ &=& \var{ans}\;\mod\;\var{n} \end{eqnarray*}$

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

This question is used in the following exams:

Loading...

Error

Solve three congruences using Chinese Remainder Theorem

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Newcastle University Mathematics and Statistics 9 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: `number`

Parts

Gap-fill

Loading...

Error

Solve three congruences using Chinese Remainder Theorem

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Newcastle University Mathematics and Statistics 9 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: number

Parts

Gap-fill

Generated value: `number`