John's copy of Simplify integers and rationals in Z_n

Error

There was an error loading the page.

Contributors

History

○

John Moss 5 years, 10 months ago

Created this as a copy of Simplify integers and rationals in Z_n.

Name	Status	Author	Last Modified
Simplify integers and rationals in Z_n	Ready to use	Newcastle University Mathematics and Statistics	20/11/2019 14:51
John's copy of Simplify integers and rationals in Z_n	draft	John Moss	18/06/2019 10:55

Question statement

Simplify the following in each of $\mathbb{Z}_{3}, \; \mathbb{Z}_{5}, \; \mathbb{Z}_{7}$ and $\mathbb{Z}_{11}$ .

For the last two questions, recall that for a prime $p$ , $\displaystyle{\frac{1}{b} \bmod{p}}$ is the unique solution to $bx \equiv 1 \bmod{p}$ .

You must input all values as positive integers; negative integers are not accepted.

Give any introductory information the student needs.

			Name	Type	Generated Value

f1	integer	7
p7	integer	1
ans1	integer	-3
inv11	number	6
b1	integer	-4
b3	integer	2
ans27	integer	6
ans25	integer	3
ans23	integer	2
d1	integer	9
q3	integer	-1
rinv11	integer	-5
q5	integer	-2
ans211	integer	6
s2	integer	-1
s1	integer	1
ans111	number	8
minv11	number	10
a1	integer	8
ans13	number	0
a2	integer	83
q11	integer	-5
ans17	number	4
ans15	number	2
c3	integer	31
c1	integer	4
rinv3	integer	-1
rinv5	integer	-2
rinv7	integer	-3
p3	integer	1
q7	integer	-3
p11	integer	1
inv7	number	4
inv5	number	3
p5	integer	1
inv3	number	2
minv3	number	2
minv7	number	5
minv5	number	3

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(2..9)

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`

→ Used by:

ans1

Advice
"Unnamed part" - prompt

Parts

Gap-fill
1. Gap Gap 0. Number entry
  Add
2. Gap Gap 1. Number entry
  Add
3. Gap Gap 2. Number entry
  Add
4. Gap Gap 3. Number entry
  Add
5. Gap Gap 4. Number entry
  Add
6. Gap Gap 5. Number entry
  Add
7. Gap Gap 6. Number entry
  Add
8. Gap Gap 7. Number entry
  Add
9. Gap Gap 8. Number entry
  Add
10. Gap Gap 9. Number entry
  Add
11. Gap Gap 10. Number entry
  Add
12. Gap Gap 11. Number entry
  Add
13. Gap Gap 12. Number entry
  Add
14. Gap Gap 13. Number entry
  Add
15. Gap Gap 14. Number entry
  Add
16. Gap Gap 15. Number entry
  Add

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

	$\mathbb{Z}_{3}$	$\mathbb{Z}_{5}$	$\mathbb{Z}_{7}$	$\mathbb{Z}_{11}$
$\simplify[!basic]{{a1}{b1}+{c1}{d1}-{f1}}$	Gap 0.	Gap 1.	Gap 2.	Gap 3.
$\var{a2}$	Gap 4.	Gap 5.	Gap 6.	Gap 7.
$\displaystyle{ \frac{1}{\var{b3}} }$	Gap 8.	Gap 9.	Gap 10.	Gap 11.
$\displaystyle{ \frac{\var{c3}}{\var{b3}} }$	Gap 12.	Gap 13.	Gap 14.	Gap 15.

Advice

For the first row, it may help to simplify each of the numbers modulo the number corresponding to each column, and then perform the calculation.

For example,

$\begin{align} \simplify[!basic]{{a1}*{b1}+{c1}*{d1}-{f1}} &\equiv \simplify[!basic]{{mod(a1,3)}*{mod(b3,3)}+{mod(c1,3)}*{mod(d1,3)}-{mod(f1,3)}} \mod{3} \\ &\equiv \var{ans13} \mod{3} \end{align}$

In the second row, you just have to work out the remainder when dividing $\var{a2}$ by each of $3$ , $5$ , $7$ and $11$ .

In the third row we have to find the inverse of $\var{b3}$ in each of $\mathbb{Z}_{3}$ , $\mathbb{Z}_{5}$ , $\mathbb{Z}_{7}$ and $\mathbb{Z}_{11}$ .

It should be clear to you that $\var{b3}$ is coprime to each of $3$ , $5$ , $7$ and $11$ , hence we can find an inverse in each of $\mathbb{Z}_{3}$ , $\mathbb{Z}_{5}$ , $\mathbb{Z}_{7}$ and $\mathbb{Z}_{11}$ .

You can do this in $\mathbb{Z}_{3}$ by finding $x$ such that $\var{b3}x \equiv 1 \bmod{3}$ , similarly for $5$ , $7$ , $11$ .

You can do this by trying values to find one that works; this is easy for $\mathbb{Z}_{3}$ since there are only two cases to check, and you will find that

$b = \var{inv3}$ satisfies $\var{inv3} \times \var{b3} = \var{inv3*b3} \equiv 1 \bmod{3}.$

Inverse in $\mathbb{Z}_{5}$

If you cannot immediately find an inverse in $\mathbb{Z}_{5}$ , you can use the Euclidean algorithm to find $a$ and $b$ such that

$\var{b3}b +5a = \operatorname{gcd}(\var{b3},5) = 1$

as $\var{b3}$ and $5$ are coprime.

It follows that $\var{b3}b \equiv 1 \bmod{5}$ , and hence $b \bmod{5}$ is the inverse of $\var{b3}$ in $\mathbb{Z}_{5}$ .

Using the Euclidean algorithm I find that

$\simplify[!basic]{ {max(5,b3)}*{p5} + {min(5,b3)}*{q5} = 1 }.$

Hence the inverse is

$b = \var{rinv5} \equiv \var{inv5} \bmod{5}.$

Inverse in $\mathbb{Z}_{7}$

Once again if you cannot spot the solution:

Using the Euclidean algorithm I find that

$\simplify[!basic]{ {max(7,b3)}*{p7} + {min(7,b3)}*{q7} = 1 }.$

Hence the inverse of $\var{b3}$ in $\mathbb{Z}_{7}$ is

$b = \var{rinv7} \equiv \var{inv7} \bmod{7}.$

Inverse in $\mathbb{Z}_{11}$

Using the Euclidean algorithm I find that

$\simplify[!basic]{ {max(11,b3)}*{p11} + {min(11,b3)}*{q11} = 1}.$

Hence the inverse of $\var{b3}$ in $\mathbb{Z}_{11}$ is

$b = \var{rinv11} \equiv \var{inv11} \bmod{11}.$

Last Question

The last question's answers are found by, for example in $\mathbb{Z}_{7}$ , considering (all $\bmod 7$ )

$\frac{\var{c3}}{\var{b3}} = \var{c3} \times \frac{1}{\var{b3}} \equiv \var{c3} \times \var{inv7} \equiv \var{c3*inv7} \equiv \var{minv7} \bmod{7}.$

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
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
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
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
Number entry
Number entry		Hasn't run yet

This question is used in the following exam:

Practice Cryptography by John Moss in John's workspace.

Loading...

Error

John's copy of Simplify integers and rationals in Z_n

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

John Moss 5 years, 10 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

Inverse in $\mathbb{Z}_{5}$

Inverse in $\mathbb{Z}_{7}$

Inverse in $\mathbb{Z}_{11}$

Last Question

Loading...

Error

John's copy of Simplify integers and rationals in Z_n

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

John Moss 5 years, 10 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

Inverse in Z5\mathbb{Z}_{5}

Inverse in Z7\mathbb{Z}_{7}

Inverse in Z11\mathbb{Z}_{11}

Last Question

Generated value: `integer`

Inverse in $\mathbb{Z}_{5}$

Inverse in $\mathbb{Z}_{7}$

Inverse in $\mathbb{Z}_{11}$