Modular Arithmetic Revision Notes for AQA A-Level Further Maths

Modular Arithmetic

Introduction to modular arithmetic

Modular arithmetic is a system of arithmetic where numbers wrap around after reaching a certain value called the modulus. You encounter this concept daily when reading a 12-hour clock. When it's 11:00 and five hours pass, the time becomes 4:00, not 16:00. Similarly, three hours before 1:00 gives us 10:00, not -2:00. This wrapping behaviour is the foundation of modular arithmetic, and we write these relationships as $11 + 5 \equiv 4 \pmod{12}$ and $1 - 3 \equiv 10 \pmod{12}$ .

infoNote

The Clock Analogy

Think of a 12-hour clock as the perfect example of modular arithmetic in action. The clock face shows numbers 1 through 12, but when you reach 12, you don't continue to 13 - instead, you return to 1 (or think of 12 as 0 in mathematical terms). This is exactly how modular arithmetic works with any modulus!

The key principle is that in modular arithmetic, once you reach the modulus value, you start counting again from zero. For a 12-hour clock, the modulus is 12, which means every time you reach 12, you return to 0. This concept applies to any positive integer as a modulus, not just 12.

Understanding congruence

The symbol ≡ means is congruent to and is central to modular arithmetic. Two numbers are congruent modulo n if they give the same remainder when divided by $n$ . For example, in modulo 12 arithmetic, 12 is congruent to 0 because dividing 12 by 12 gives a remainder of 0. We write this as $12 \equiv 0 \pmod{12}$ .

chatImportant

Understanding the ≡ Symbol

The congruence symbol ≡ looks similar to the equals sign = for good reason - congruent numbers behave similarly in calculations! However, while $a = b$ means the numbers are exactly the same, $a \equiv b \pmod{n}$ means they give the same remainder when divided by $n$ .

Another way to understand this is that $a \pmod{n}$ represents the remainder when $a$ is divided by $n$ . This remainder is always a non-negative integer less than $n$ .

Congruence with different moduli

Any modulo can be used for modular arithmetic. Let's consider modulo 5 as an example. Whenever you reach a multiple of 5, you start counting again from 0. This means 5 is congruent to 0, 6 is congruent to 1, 7 is congruent to 2, and this pattern continues.

The table above illustrates this pattern clearly. Looking at the numbers, we can see:

$5 \equiv 0 \pmod{5}$
$6 \equiv 1 \pmod{5}$
$10 \equiv 0 \pmod{5}$
$15 \equiv 0 \pmod{5}$

Using this understanding, we can calculate: $3 + 4 \equiv 2 \pmod{5}$ and $4 \times 4 \equiv 1 \pmod{5}$ .

Mathematical representation of congruence

infoNote

Alternative Way to Express Congruence

If $a \equiv b \pmod{n}$ , then $a$ can be written as $a = b + kn$ where $k$ is an integer. Similarly, if $c \equiv d \pmod{n}$ , then $c = d + mn$ where $m$ is an integer.

This representation shows that congruent numbers differ by a multiple of the modulus. In other words, if two numbers are congruent modulo $n$ , their difference is divisible by $n$ .

Rules of modular arithmetic

You can use specific rules to add, subtract, multiply, and work with powers in modular arithmetic. These rules allow you to simplify calculations significantly.

The three fundamental rules

chatImportant

The Core Rules of Modular Arithmetic

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ , then:

Addition: $a + c \equiv b + d \pmod{n}$
Subtraction: $a - c \equiv b - d \pmod{n}$
Multiplication: $ac \equiv bd \pmod{n}$ (provided that $a, b, c, d, n$ are integers)

These rules are fundamental because they allow you to simplify complex calculations by working with smaller, equivalent numbers.

These rules work because when you add, subtract, or multiply congruent numbers, the results remain congruent. The solution can be written as $b + d \pmod{n}$ since $k + m$ is also an integer.

Exponential rule

For powers in modular arithmetic, if $a \equiv b \pmod{n}$ , then:

$a^k \equiv b^k \pmod{n}$

where $a, b, n \in \mathbb{Z}$ , $n \in \mathbb{Z}^+$ , and $k \in \mathbb{Z}^+$ .

This rule is particularly useful for simplifying large exponential expressions.

Worked examples

lightbulbExample

Worked Example: Basic Modular Calculations - Part (a)

Calculate: $53 + 14 \pmod{10}$

Solution:

First, we simplify each number modulo 10:

$53 \equiv 3 \pmod{10}$ (since $53 \div 10$ leaves remainder 3)
$14 \equiv 4 \pmod{10}$ (since $14 \div 10$ leaves remainder 4)

Now apply the addition rule:

$53 + 14 \equiv 3 + 4 \pmod{10}$ $\equiv 7 \pmod{10}$

lightbulbExample

Worked Example: Basic Modular Calculations - Part (b)

Calculate: $53 \times 14 \pmod{10}$

Solution:

Using the same simplifications as above:

$53 \equiv 3 \pmod{10}$
$14 \equiv 4 \pmod{10}$

Apply the multiplication rule:

$53 \times 14 \equiv 3 \times 4 \pmod{10}$ $\equiv 12 \pmod{10}$ $\equiv 2 \pmod{10}$

Key point: Always write your answer in its simplest form, which means the remainder should be between 0 and $n-1$ .

lightbulbExample

Worked Example: Using the Exponential Rule - Part (c)

Calculate: $152^6 \pmod{10}$

Solution:

First simplify the base:

$152 \equiv 2 \pmod{10}$

Using the exponential rule: $152^6 \equiv 2^6 \pmod{10}$

Calculate $2^6 = 64$ , then:

$64 \equiv 4 \pmod{10}$

Therefore: $152^6 \equiv 4 \pmod{10}$

Strategy: When dealing with powers, always simplify the base first before calculating the exponent. This makes calculations much easier and helps avoid working with unnecessarily large numbers.

Cayley tables and binary operations

Binary operations in modular arithmetic can be represented using Cayley tables. These tables show the result of an operation (like addition or multiplication) for every possible pair of elements in a set. Cayley tables are particularly useful for identifying patterns and properties in modular arithmetic.

Notation for binary operations

The notation +ₙ represents addition modulo n, where $n$ is a positive integer. Similarly, the notation ×ₙ represents multiplication modulo n, where $n$ is a positive integer. These notations make it clear which modulus is being used for the operation.

Constructing a Cayley table

To construct a Cayley table for a binary operation on the set of integers modulo $n$ :

Draw a table with rows and columns labelled with the set $\{0, 1, 2, \ldots, n-1\}$
Calculate the operation for each pair of integers and write the answers (mod $n$ ) in the table cells
Use the property that $a * e = e * a = a$ to identify the identity element $e$

lightbulbExample

Worked Example: Cayley Table for Addition Modulo 6

Consider the binary operation $+_6$ on the set of integers modulo 6.

The set contains the integers $\{0, 1, 2, 3, 4, 5\}$ .

Here is the Cayley table for addition modulo 6:

+₆	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

How to read the table: To find $2 +_6 5$ , look at the row labelled 2 and the column labelled 5. The cell shows 1, so $2 +_6 5 = 1 \pmod{6}$ . This makes sense because $2 + 5 = 7$ , and $7 \equiv 1 \pmod{6}$ .

Identity element

The identity element is the element that leaves other elements unchanged when the operation is applied. For addition modulo 6, the identity element is 0 because $a + 0 \equiv 0 + a \equiv a$ for all values of $a$ in the set.

infoNote

Identifying the Identity Element in a Cayley Table

You can identify the identity element in a Cayley table by finding the row and column that exactly match the headers. In the table above, both the row and column for 0 show the sequence $\{0, 1, 2, 3, 4, 5\}$ .

Think of it this way: the identity element is like zero in addition or one in multiplication - it doesn't change the other number when you apply the operation!

Inverse elements

Each element in modular arithmetic may have an inverse - an element that, when combined with the original using the operation, produces the identity element. For addition modulo 6:

The inverse of 1 is 5 (because $1 + 5 \equiv 0 \pmod{6}$ )
The inverse of 2 is 4 (because $2 + 4 \equiv 0 \pmod{6}$ )
The inverse of 3 is 3 (because $3 + 3 \equiv 0 \pmod{6}$ )
0 is its own inverse (because $0 + 0 \equiv 0 \pmod{6}$ )

We can write this as: the inverse of 1 is 5 and vice versa; the inverse of 2 is 4 and vice versa; 0 and 3 are self-inverse.

chatImportant

Finding Inverses Using Cayley Tables

In a Cayley table, to find the inverse of an element, look for the identity element in that element's row or column. The corresponding row/column header is the inverse.

For example, in the addition modulo 6 table, look at row 2: the identity element 0 appears in the column labelled 4, so 4 is the inverse of 2.

bookmarkSummary

Key Points to Remember:

Modular arithmetic involves working with remainders after division by a fixed modulus $n$ . Think of it like a clock where numbers wrap around.
Two numbers are congruent modulo n (written $a \equiv b \pmod{n}$ ) if they leave the same remainder when divided by $n$ . Alternatively, $a \equiv b \pmod{n}$ means $a = b + kn$ for some integer $k$ .
The three key rules allow you to add, subtract, and multiply congruent numbers: if $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ , then $a + c \equiv b + d \pmod{n}$ , $a - c \equiv b - d \pmod{n}$ , and $ac \equiv bd \pmod{n}$ .
Cayley tables display the results of binary operations on finite sets. The identity element leaves other elements unchanged, while inverse elements combine with originals to produce the identity.
When working with powers, use the exponential rule: $a^k \equiv b^k \pmod{n}$ when $a \equiv b \pmod{n}$ . Always simplify the base before calculating the exponent to make computations easier.

Modular Arithmetic (AQA A-Level Further Maths): Revision Notes