Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

Modular Arithmetic

In this section we will learn more about modular arithmetic, including how it interacts with addition, subtraction, multiplication and division. These are mostly straightforward, except for division. We’ll leave that one for later.

Watch the video and then answer the questions below.

Twelve-minute video

You can also view this video on YouTube

Key Points

Modlar arithmatic applies to integers. For example, arithmatic modulo 4 just uses the numbers {0, 1, 2, 3}
Moduar arithmetic introduces the congruance relation. It is written using a triple equals symbol ≡.
Numbers are congruant modulo n, if after finding their modulus with n, you get the same answer. For example 1 and 7 are congruant modulo 6, and 13 and 23 are congruant modulo 10.

Properties of Relations

A relation R is reflexive if it is always true that a R a, no matter what a is.
A relation R is symmetric if from a R b you can infer b R a.
Given a relation R, say you know that a R b and b R c are both true. If R is transitive, then you can infer a R c.

Additivity and Multiplicativity

Both equality = and the congruance relation ≡ are additive and multiplicative.
Additivity means you can add the same value to both sides of an equation.
Multiplicativity means that you can multiply both sides of an equation by the same value.
With modular arithmatic, because you can add or multiply values that are not equal, so long as they are congruant.
If you know a ≡ b and c ≡ d, you can infer that a + c ≡ b + d
If you know a ≡ b and c ≡ d, you can infer that a * c ≡ b * d

Simplifying modular expressions

You can simplify modular expressions in the following way, if the modulus is the same:

(a mod n) + (b mod n) = (a+b) mod n
(a mod n) - (b mod n) = (a+b) mod n
(a mod n) x (b mod n) = (a+b) mod n.

Questions

1. Check your understanding

1. Simplifying modular expressions

Rewrite the following into the form: a mod b

(4 mod 8) + (22 mod 8)
(1 mod 11) + (4 mod 11)
(12 mod 4) – (3 mod 4 )
(65 mod 12) – (42 mod 12)
(6 mod 3) * (9 mod 3)
(2 mod 8) * (6 mod 8)

Check Answers

2. Relations

Check all those properties that hold of the given relation.

Relation	Reflexive	Symmetric	Transitive
`>` (greater than)
`≥` (greater or equal to)
`≡` (congruant modulo n)
`=` (equals)
“is standing next to”
“is twice as tall as”