What is modular arithmetic?

Modular arithmetic is a system where numbers wrap around after reaching a modulus n. All operations stay within the set {0, 1, 2, ..., n-1}. Like a 12-hour clock where 10 + 5 = 3 (not 15), numbers cycle back when they exceed the modulus.

How do you add numbers in modular arithmetic?

Reduce each operand mod n, add the results, then reduce again if the sum reaches or exceeds n. For (47 + 38) mod 10: reduce to 7 + 8 = 15, then 15 mod 10 = 5. The final reduction handles sums that exceed the modulus.

How do you subtract in modular arithmetic?

Reduce each operand, subtract, and if the result is negative, add n. For (23 - 47) mod 10: reduce to 3 - 7 = -4, then add 10 to get 6. The negative result represents wrapping backward past zero on the number cycle.

How do you multiply in modular arithmetic?

Reduce each factor mod n, multiply the remainders, then reduce the product. For (89 × 76) mod 9: reduce to 8 × 4 = 32, then 32 mod 9 = 5. This avoids computing the full product 6,764.

How do you compute large powers modulo n?

Reduce after every multiplication instead of computing the full power first. For 7⁴ mod 10: compute 7² = 49 → 9, then 9 × 7 = 63 → 3, then 3 × 7 = 21 → 1. The largest intermediate is 63, not 2,401.

What are power cycles in modular arithmetic?

Powers of any base mod n eventually repeat in a cycle. For 2^k mod 7, the cycle is {2, 4, 1} with period 3. To find 2¹⁰⁰ mod 7: divide 100 by 3 to get remainder 1, so 2¹⁰⁰ ≡ 2¹ = 2 (mod 7).

Why doesn't division work normally in modular arithmetic?

Modular reduction discards information that division needs. Dividing remainders directly gives wrong answers. Instead, division requires the modular inverse: to divide by b, multiply by b⁻¹ where b·b⁻¹ ≡ 1 (mod n). Not every number has an inverse for every modulus.

How do you find the last digit of a large power?

The last digit is the number mod 10. Find the cycle of powers mod 10, then locate the exponent's position in that cycle. For 7¹⁰⁰: powers of 7 cycle {7,9,3,1} with period 4. Since 100 mod 4 = 0, the answer is 1 (position of 7⁴).

How do you solve clock problems with modular arithmetic?

A 12-hour clock uses mod 12; a 24-hour clock uses mod 24. Add hours to current time and reduce. For 50 hours after 10:00: (10 + 50) mod 12 = 60 mod 12 = 0, which is 12:00. For backward calculations, subtract and add n if negative.

How do you calculate day of the week using modulo?

Days cycle mod 7. Assign Sunday = 0 through Saturday = 6. Add the number of days to the current day number and reduce mod 7. For 100 days after Wednesday (day 3): (3 + 100) mod 7 = 103 mod 7 = 5 = Friday.

Why do divisibility rules work?

Divisibility rules exploit congruence properties of 10. For divisibility by 9: since 10 ≡ 1 (mod 9), each digit contributes its face value regardless of position, making the digit sum determine divisibility. For 11: since 10 ≡ -1 (mod 11), positions alternate in sign.

How do you find the last two digits of a power?

The last two digits are the number mod 100. Find when the powers cycle mod 100. For 7⁵⁰ mod 100: since 7⁴ = 2401 ≡ 1 (mod 100), and 50 = 4×12 + 2, we get 7⁵⁰ ≡ 7² = 49 (mod 100). The last two digits are 49.

Modular Arithmetic: Operations, Power Cycles & Applications

Q: What is the core principle of modular arithmetic?

Reducing numbers before, during, or after an operation produces the same final remainder. This means large numbers can be replaced by their remainders at any stage without affecting the outcome, making calculations with huge numbers practical.

Operating Within a Modulus

Standard arithmetic works on the full number line — results can grow without bound. Modular arithmetic restricts the playing field. Every number is reduced to one of

n

possible remainders, and every operation stays within that set.

Add

9 + 7

in ordinary arithmetic and the answer is

16

. Add

9 + 7

modulo

10

and the answer is

6

— the sum wraps past

9

and cycles back. The number

16

and the number

6

are different on the number line, but they are the same in the world of

\bmod 10

.

The mental model is a clock with

n

hours. On a

10

-hour clock, moving

7

steps forward from

9

lands on

6

, not

16

. On a

12

-hour clock,

10 + 5 = 3

, not

15

. The numbers wrap around whenever they reach the modulus.

This wrap-around is not an approximation or a shortcut — it is a self-contained arithmetic system with its own rules, and those rules are precise enough to produce exact answers to problems that would be impractical to solve on the full number line.

The Core Principle

The power of modular arithmetic comes from one fact: reducing numbers before, during, or after an operation all produce the same final remainder.

This means large numbers can be replaced by their remainders at any stage of a calculation without affecting the outcome. The formal statement: if

a \equiv a' \pmod{n}

and

b \equiv b' \pmod{n}

, then:

a + b \equiv a' + b' \pmod{n}

a - b \equiv a' - b' \pmod{n}

a \cdot b \equiv a' \cdot b' \pmod{n}

In words: replacing any number with a congruent one does not change the remainder of the result. The product

89 \times 76

modulo

9

does not require computing

6{,}764

first — replacing

89

with

8

and

76

with

4

gives

32

, and

32 \bmod 9 = 5

. The answer is the same either way.

This principle is what makes modular arithmetic practical. Without it, every computation would require handling the full-size numbers and reducing only at the end.

Addition

Modular addition reduces each operand, adds the results, and reduces once more if the sum reaches or exceeds

n

:

(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n

For

(47 + 38) \bmod 10

: reduce

47

to

7

and

38

to

8

. Add:

7 + 8 = 15

. Reduce:

15 \bmod 10 = 5

.

For

(123 + 456) \bmod 7

: reduce

123

to

4

and

456

to

1

. Add:

4 + 1 = 5

. Since

5 < 7

, no further reduction is needed.

The final reduction is necessary because the sum of two remainders can reach as high as

2(n - 1)

. For

\bmod 10

, the largest possible intermediate sum is

9 + 9 = 18

, which still needs one more reduction. But it can never reach

2n

, so a single reduction always suffices.

Subtraction

Modular subtraction follows the same reduce-operate-reduce pattern, with one wrinkle: the intermediate result may be negative.

(a - b) \bmod n = ((a \bmod n) - (b \bmod n)) \bmod n

For

(23 - 47) \bmod 10

: reduce

23

to

3

and

47

to

7

. Subtract:

3 - 7 = -4

. The result is negative, so add

n

:

-4 + 10 = 6

.

The alternative is to compute the full subtraction first:

23 - 47 = -24

, then

-24 \bmod 10 = 6

(using the floored convention). Either route gives

6

.

The negative intermediate result is not an error — it reflects a position on the number cycle that has wrapped past zero in the backward direction. Adding

n

translates it to its equivalent position in

\{0, 1, \ldots, n-1\}

.

Multiplication

Modular multiplication reduces each factor, multiplies the remainders, and reduces the product:

(a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n

For

(23 \cdot 17) \bmod 5

: reduce

23

to

3

and

17

to

2

. Multiply:

3 \cdot 2 = 6

. Reduce:

6 \bmod 5 = 1

.

For

(89 \cdot 76) \bmod 9

: reduce

89

to

8

and

76

to

4

. Multiply:

8 \cdot 4 = 32

. Reduce:

32 \bmod 9 = 5

.

The savings are dramatic for large numbers. The product

89 \times 76 = 6{,}764

is never needed — the same answer emerges from the product

8 \times 4 = 32

, a computation simple enough to do mentally.

The principle chains through multiple factors. For

(13 \cdot 17 \cdot 19) \bmod 5

: reduce to

3 \cdot 2 \cdot 4 = 24

, then

24 \bmod 5 = 4

. Reduce at every step to keep the numbers small.

Powers

Computing

a^k \bmod n

by first calculating

a^k

and then reducing is impractical — the intermediate number grows exponentially. Instead, reduce after every multiplication.

For

7^4 \bmod 10

, build the power step by step:

7^1 \bmod 10 = 7

7^2 = 7 \cdot 7 = 49 \to 49 \bmod 10 = 9

7^3 = 9 \cdot 7 = 63 \to 63 \bmod 10 = 3

7^4 = 3 \cdot 7 = 21 \to 21 \bmod 10 = 1

The answer is

1

. The largest intermediate number was

63

— far smaller than

7^4 = 2{,}401

.

For

3^{10} \bmod 7

:

3^1 = 3

,

3^2 = 9 \to 2

,

3^3 = 6

,

3^4 = 18 \to 4

,

3^5 = 12 \to 5

,

3^6 = 15 \to 1

.

At

3^6

, the remainder returns to

1

. From here:

3^{10} = 3^6 \cdot 3^4 \equiv 1 \cdot 4 = 4 \pmod{7}

.

Detecting Cycles in Powers

Because

\bmod n

confines remainders to a finite set, the sequence of remainders

a^1, a^2, a^3, \ldots \bmod n

must eventually repeat. Once a remainder reappears, the entire pattern cycles from that point forward.

Powers of

2 \bmod 7

produce the sequence:

2, 4, 1, 2, 4, 1, 2, 4, 1, \ldots

The cycle

\{2, 4, 1\}

has length

3

and repeats indefinitely.

To compute

2^{100} \bmod 7

, divide the exponent by the cycle length:

100 = 3 \cdot 33 + 1

. The remainder is

1

, so

2^{100}

lands at the same position as

2^1

in the cycle. The answer is

2

.

Powers of

3 \bmod 10

cycle through

\{3, 9, 7, 1\}

with length

4

. For

3^{75} \bmod 10

:

75 = 4 \cdot 18 + 3

, so

3^{75}

matches

3^3 = 7

. The answer is

7

.

The cycle always begins once the remainder

1

appears (assuming it does), because

a^k \equiv 1

implies

a^{k+j} \equiv a^j

for any

j

— the sequence restarts.

Why Division Is Different

Addition, subtraction, and multiplication all pass through

\bmod n

cleanly. Division does not.

Consider

12 \div 4 = 3

. Working modulo

5

:

12 \bmod 5 = 2

and

4 \bmod 5 = 4

. Dividing the remainders gives

\frac{2}{4} = 0.5

— not an integer, and certainly not

3 \bmod 5 = 3

.

The problem is that division undoes multiplication, but modular reduction discards information that division needs to recover. The product

4 \cdot 3 = 12

reduces to

2 \bmod 5

, and knowing only

2

and

4

is not enough to reconstruct

3

through ordinary division.

Modular division requires a different tool: the modular inverse. The inverse of

b

modulo

n

is a number

b^{-1}

such that

b \cdot b^{-1} \equiv 1 \pmod{n}

. Dividing by

b

then means multiplying by

b^{-1}

. Not every number has an inverse for every modulus — the theory belongs to number theory and is not covered here.

Last Digit Problems

The last digit of any number is that number

\bmod 10

. Finding the last digit of a large power reduces to modular exponentiation with

n = 10

.

Find the last digit of

7^{100}

. The powers of

7 \bmod 10

cycle:

7, 9, 3, 1, 7, 9, 3, 1, \ldots

with period

4

.

Divide the exponent by the cycle length:

100 = 4 \cdot 25 + 0

. A remainder of

0

means the exponent aligns with the end of a full cycle — the position of

7^4

, whose last digit is

1

.

Find the last digit of

3^{75}

. The powers of

3 \bmod 10

cycle:

3, 9, 7, 1

with period

4

. Divide:

75 = 4 \cdot 18 + 3

. The remainder

3

points to the third position in the cycle:

7

.

The method works for any base. Identify the cycle of last digits, find the exponent's position within that cycle, and read off the answer — no need to compute the full power.

Clock Problems

Time wraps around, making clock questions natural applications of modular arithmetic.

A

12

-hour clock operates

\bmod 12

. If it is

10{:}00

now, what time will it be in

50

hours? Compute

(10 + 50) \bmod 12 = 60 \bmod 12 = 0

. On a

12

-hour clock, a remainder of

0

corresponds to

12{:}00

.

A

24

-hour clock operates

\bmod 24

. If it is

21{:}00

(9 PM), what time will it be in

100

hours? Compute

(21 + 100) \bmod 24 = 121 \bmod 24

. Divide:

121 = 24 \cdot 5 + 1

. The answer is

1{:}00

— one o'clock in the morning.

The same logic handles backward calculations. If it is

3{:}00

now, what time was it

20

hours ago? Compute

(3 - 20) \bmod 12 = -17 \bmod 12

. Adding

24

(two full cycles):

-17 + 24 = 7

. It was

7{:}00

.

Day of Week Problems

Days of the week cycle with period

7

, making them a

\bmod 7

system. Assign numbers: Sunday

= 0

, Monday

= 1

, Tuesday

= 2

, Wednesday

= 3

, Thursday

= 4

, Friday

= 5

, Saturday

= 6

.

Today is Wednesday (day

3

). What day is it in

100

days? Compute

(3 + 100) \bmod 7 = 103 \bmod 7

. Divide:

103 = 7 \cdot 14 + 5

. Day

5

is Friday.

January

1

is a Monday (day

1

). What day is March

15

? Count the days:

31

(remaining in January)

+ 28

(February)

+ 14

(first

14

days of March)

= 73

days later. Compute

(1 + 73) \bmod 7 = 74 \bmod 7

. Divide:

74 = 7 \cdot 10 + 4

. Day

4

is Thursday.

Larger spans work identically. What day is it

1{,}000

days from a Tuesday (day

2

)? Compute

(2 + 1000) \bmod 7 = 1002 \bmod 7

. Divide:

1002 = 7 \cdot 143 + 1

. Day

1

is Monday.

Why Divisibility Rules Work

The familiar divisibility rules are modular arithmetic in disguise. Each rule exploits a congruence property of

10

— the base of our number system.

The digit-sum rule for

9

works because

10 \equiv 1 \pmod{9}

. Every power of

10

is congruent to

1

:

10^0 = 1

,

10^1 \equiv 1

,

10^2 \equiv 1

, and so on. A digit

d

in the

k

th place contributes

d \cdot 10^k \equiv d \cdot 1 = d \pmod{9}

. The place value drops away, and only the digit itself matters. So the entire number is congruent to the sum of its digits modulo

9

.

The rule for

3

follows identically:

10 \equiv 1 \pmod{3}

, so the digit sum also determines divisibility by

3

.

The alternating-sum rule for

11

works because

10 \equiv -1 \pmod{11}

. Powers of

10

alternate:

10^0 = 1

,

10^1 \equiv -1

,

10^2 \equiv 1

,

10^3 \equiv -1

. Each digit's contribution alternates in sign depending on its position, producing the alternating sum.

Every shortcut in the divisibility rules page traces back to a congruence property of

10

modulo the divisor in question. Modular arithmetic is the engine; the rules are the user-facing controls.

Worked Examples

Compute

(137 \cdot 249) \bmod 7

. Reduce:

137 \bmod 7 = 4

and

249 \bmod 7 = 4

. Multiply:

4 \cdot 4 = 16

. Reduce:

16 \bmod 7 = 2

.

Find the last two digits of

7^{50}

(that is,

7^{50} \bmod 100

). Compute powers step by step:

7^1 = 7

,

7^2 = 49

,

7^4 = 49^2 = 2401 \to 1 \bmod 100

. Since

7^4 \equiv 1 \pmod{100}

, and

50 = 4 \cdot 12 + 2

, we get

7^{50} \equiv 7^2 = 49 \pmod{100}

. The last two digits are

49

.

A meeting happens every

8

days. Another happens every

12

days. Both occur today. When do they next coincide? The answer is the LCM of

8

and

12

, which is

24

— but modular thinking frames it as: find the smallest

d > 0

such that

d \equiv 0 \pmod{8}

and

d \equiv 0 \pmod{12}

.

Verify that

8{,}361

is divisible by

9

. Digit sum:

8 + 3 + 6 + 1 = 18

, then

1 + 8 = 9

. Since

9 \equiv 0 \pmod 9

, the number is divisible by

9

. Confirm:

8361 = 9 \cdot 929

.

Simplify

(2^{50} + 3^{50}) \bmod 5

. Powers of

2 \bmod 5

cycle

\{2, 4, 3, 1\}

with period

4

. Since

50 = 4 \cdot 12 + 2

,

2^{50} \equiv 4 \pmod{5}

. Powers of

3 \bmod 5

cycle

\{3, 4, 2, 1\}

with period

4

. Since

50 = 4 \cdot 12 + 2

,

3^{50} \equiv 4 \pmod{5}

. Sum:

4 + 4 = 8 \to 8 \bmod 5 = 3

.

Modulo Operations

Arithmetic That Wraps Around

Operating Within a Modulus

The Core Principle

Addition

Subtraction

Multiplication

Powers

Detecting Cycles in Powers

Why Division Is Different

Last Digit Problems

Clock Problems

Day of Week Problems

Why Divisibility Rules Work

Worked Examples