Argue In Your Head: 15 divides 2¹⁰⁰⁰⁰⁰⁰-1

## How can this be done?

Consider powers of two: 2²=4, 2³=8, 2⁴=16, 2⁵=32…., very quickly raising 2 to higher and higher powers will yield seemingly gigantic and unfathomable numbers.

Take for example 2¹⁰⁰, which I’m told by my trusted source Alexa, is approximately 1.268 million trillion trillion.

How can we be sure then, that 2¹⁰⁰⁰⁰⁰⁰-1 is divisible by 15?

This is where modular arithmetic is powerful.

## Modular Arithmetic

We say for integers a, b and m (m>0) that a is congruent to b modulus m if and only if m divides a minus b.

In short form, we write a ≡ b mod m (where we use the triple bar symbol ‘≡’ which looks like the equal symbol).

Examples:

- 18 ≡ 4 mod 7 (since 7 divides 18–4=14)
- 9 ≡ 4 mod 5 (since 5 divides 9–4=5)
- 1 ≡ 1 mod 11 (since 11 divides 1–1=0)
- 100 ≡ 1 mod 9 (since 9 divides 100–1=99)

This curious definition has wide reaching applications in Mathematics, Computer Science and other disciplines.

To get back to the problem above, let’s state and prove a result which will help us.

Proposition: If we have a ≡ b mod m and c ≡ d mod m for integers a, b, c, d and m (m>0) then ac ≡ bd mod m.

Example: 11 ≡ 3 mod 8, 21 ≡ 5 mod 8 and 231 ≡ 15 mod 8.

Proof: If m divides a-b then we can write a-b=mk for some integer k or equivalently a=b+mk. Similarly, we can write c=d+mj for some integer j. Now let’s multiply these two equations and we get ac=(b+mk)(d+mj)= bd+m(bj+ck+mkj) which is just saying that m divides ac-bd or that ac ≡ bd mod m.

Comment: You should see from this proposition that if a ≡ b mod m then a² ≡ b² mod m. Indeed, we can raise to any power e.g. a¹⁰⁰⁰⁰⁰⁰ ≡ b¹⁰⁰⁰⁰⁰⁰ mod m.

## Why does 15 divide 2¹⁰⁰⁰⁰⁰⁰-1?

It’s clear that 2⁴=16 ≡ 1 mod 15 and a million is 4 multiplied by 250,000. We can repeatedly apply the above proposition to say the following: