Arithmetic Operations and Solving Linear Equations Modulo m

1. Arithmetic Operations Modulo m

In modular arithmetic, numbers are reduced to their remainders after division by mmm.

The notation:

a (mod m) means we divide a by m and take the remainder.

A. Addition Modulo m

Rule: (a + b) (mod m)

Example:

Find: 7 + 9 (mod 5)

Step 1: Add first: 7 + 9 = 16

Step 2: Divide by 5: 16 ÷ 5 = 3 remainder 1

Therefore: 7 + 9 ≡ 1 (mod 5)

B. Subtraction Modulo m

Rule: (a − b) (mod m)

Example:

Find: 8 − 13 (mod 6)

Step 1: Subtract: 8 – 13 = −5

Step 2: Add 6 until it becomes positive: −5 + 6 = 1

Therefore: 8 − 13 ≡ 1 (mod 6)

C. Multiplication Modulo m

Rule: (a × b) (mod m)

Example:

Find: 4(7) (mod 5)

Step 1: Multiply: 4(7) = 28

Step 2: Divide by 5: 28 ÷ 5 = 5 remainder 3

Therefore: 4(7) ≡ 3 (mod 5)

D. Division Modulo m

Division is different because we need a multiplicative inverse.

The inverse of a modulo mmm is a number x such that:

ax ≡ 1 (mod m)

Example:

Find: (mod 5)

Step 1: Find the inverse of 2:

Try the numbers:

2 × 1 = 2 ≡ 1

2 × 2 = 4 ≡ 1

2 × 3 = 6 ≡ 1 (mod 5)

2 × 4 = 8 ≡ 3 (mod 5)

8 ÷ 5 = 1 remainder 3

So, 2-1 ≡ 3 (mod 5)

2(4) ≡ 3 (mod 5)

Therefore: 3/2 ≡ 4 (mod 5)

Solving Linear Equations Modulo m

A linear congruence has the form:

ax ≡ b (mod m) we solve for x.

Example 1:

Solve: 3x ≡ 6 (mod 9)

Step 1: Find the inverse of 3 modulo 9

There is no inverse because: gcd(3, 9) = 3

Since 3 divides 6: 3 ∣ 6 solutions exist.

Divide the equation by 3:

x ≡ 2 (mod 3)

Therefore: x ≡ 2 (mod 3)

Example 2:

Solve: 2x ≡ 8 (mod 5)

Step 1: Find the inverse of 2 modulo 5

2(3) = 6 ≡ 1(mod 5)

The inverse of 2 is 3.

Step 2: Multiply both sides by 3

3(2x) ≡ 3(8) (mod 5)

x ≡ 24 (mod 5)

Step 3: Reduce: 24 ÷ 5 = 4 remainder 4

Therefore: x ≡ 4 (mod 5)

Solving Problems Involving Modular Arithmetic

Modular arithmetic deals with numbers that "wrap around" after reaching a certain value called the modulus.

The notation: a ≡ b(mod m)

means that a and b have the same remainder when divided by m.

Example 1: Find the remainder

47 (mod 6)

Solution:

Divide 47 by 6: 47 ÷ 6 = 7 remainder 5

Therefore: 47 ≡ 5 (mod 6)

Example 2: Addition Modulo m

25 + 18 (mod 7)

Solution:

Add: 25 + 18 = 43

Divide by 7: 43 ÷ 7 = 6 remainder 1

Therefore: 25 + 18 ≡ 1 (mod 7)

Example 3: Subtraction Modulo m

12 – 20 (mod 9)

Solution:

Subtract: 12 – 20 = −8

Add 9: −8 + 9 = 1

Therefore: 12−20 ≡ 1 (mod 9)

Example 4: Multiplication Modulo m

13 × 7 (mod 10)

Solution:

Multiply: 13(7) = 91

Divide by 10: 91 ÷ 10 = 9 remainder 1

Therefore: 13 × 7 ≡ 1 (mod 10)

Example 5: Solving a Linear Congruence

4x ≡ 8 (mod 12)

Solution:

Step 1: Find the GCD: gcd(4,12) = 4

Since: 4 ∣ 8 a solution exists.

Step 2: Divide by 4: x ≡ 2 (mod 3)

Therefore: x ≡ 2 (mod 3)

Example 6: Find the Unknown Number

Find x: x + 7 ≡ 3 (mod 10)

Solution:

Step 1: Subtract 7 from both sides:

x ≡ 3 – 7 (mod 10)

x ≡ −4 (mod 10)

Step 2: Convert to a positive remainder

−4 + 10 = 6

Therefore: x ≡ 6 (mod 10)

Example 7: Word Problem (Clock Arithmetic)

A clock shows 8 o'clock. What time will it show after 15 hours?

Solution:

Because clocks use modulo 12:

8 + 15 (mod 12)

23 (mod 12)

23 – 12 = 11

Therefore: The clock will show 11 o’clock

Page updated

Report abuse