Modular Arithmetic

Modular arithmetic is a system of arithmetic that concerns remainders. Instead of mainstream notation, I have introduced a new notation. I will provide examples to clarify. For the duration of this text, variables are denoted by italicized lowercase letters, and can represent any integer, unless restrictions are specified. n, however, is always positive.

Axioms

Remainders

Define

R_{n} (a)

to be the remainder when a is divided by n.

Example:

R_{5} (13) = 3

Define the axiom

a = k n + R_{n} (a)

for some k.

Example:

13 = 5 k + R_{5} (13) = 5 (2) + 3

Congruence

Define the relation

C_{n} (a, b) ⟺ R_{n} (a) = R_{n} (b)

Example:

R_{5} (8) = R_{5} (13) ⟺ 3 = 3 ⟺ C_{5} (8, 13)

Define the axioms

C_{n} (a, a)

C_{n} (a, R_{n} (a))

C_{n} (a \cdot 1, a)

C_{n} (k n + a, a)

Define the axioms

\begin{array}{rcl} C_{n} (a, b) & ⟺ & C_{n} (b, a) \\ C_{n} (a, b), C_{n} (b, c) & ⟺ & C_{n} (a, c) \end{array}

Define the axiom

C_{n} (a_{1}, a_{2}), C_{n} (a_{2}, a_{3}) \dots C_{n} (a_{i - 1}, a_{i}) ⟺ C_{n} (a_{1}, a_{2}, a_{3} \dots a_{i - 1}, a_{i})

where i is any positive integer.

Theorems

Additive Property

Define the relationship

C_{n} (a + b, R_{n} (a) + R_{n} (b))

Proof:

Let

\begin{array}{rcl} a & = & c n + R_{n} (a) \\ b & = & d n + R_{n} (b) \end{array}

Then

C_{n} (a + b, c n + R_{n} (a) + d n + R_{n} (b), n (c + d) + R_{n} (a) + R_{n} (b), R_{n} (a) + R_{n} (b)) ◼

Corollary:

C_{n} (a, b) ⟺ C_{n} (a + c, b + c)

Multiplicative Property

Define the relationship

C_{n} (a b, R_{n} (a) R_{n} (b))

Proof:

Let

\begin{array}{rcl} a & = & c n + R_{n} (a) \\ b & = & d n + R_{n} (b) \end{array}

Then

C_{n} (a b, c n d n + c n R_{n} (b) + R_{n} (a) d n + R_{n} (a) R_{n} (b), n (c d n + c R_{n} (b) + R_{n} (a) d) + R_{n} (a) R_{n} (b), R_{n} (a) R_{n} (b)) ◼

Corollary:

C_{n} (a, b) ⟺ C_{n} (a c, b c)

Exponential Property

Define the relationship

C_{n} (a^{b}, (R_{n} (a))^{b})

where b is positive.

Proof:

Assume this relation holds for some b. Then

C_{n} (a^{b + 1}, a^{b} a, R_{n} (a^{b}) R_{n} (a), (R_{n} (a))^{b} R_{n} (a), (R_{n} (a))^{b + 1})

Therefore, it follows that if this relation holds for b, it also holds for b + 1. Let b = 1. Then

C_{n} (a^{1}, (R_{n} (a))^{1})

C_{n} (a, (R_{n} (a)))

This holds true. Therefore, this relation holds true for any positive b. $◼$

Corollary:

C_{n} (a, b) ⟺ C_{n} (a^{c}, b^{c})

where c is positive.

Divisor Rule

Define the relationship

C_{x y} (a, b) \Rightarrow C_{x} (a, b), C_{y} (a, b)

where x and y are positive.

Proof:

C_{x y} (a, b) ⟺ R_{x y} (a) = R_{x y} (b) = r

for some r. Let

\begin{array}{rcl} a & = & c x y + r \\ b & = & d x y + r \end{array}

Then, it follows that

\begin{array}{rcl} a & = & j x + r \\ b & = & k x + r \end{array}

And

C_{x} (a, j x + r, r)

C_{x} (b, k x + r, r)

Therefore

C_{x} (a, b) ◼

Similarly for y.

Product Rule

Define the relationship

C_{x} (a, b), C_{y} (a, b), g c d (x, y) = 1 \Rightarrow C_{x y} (a, b)

where x and y are positive, and gcd is the greatest common divisor function.

Proof:

Let

\begin{array}{rcl} a & = & b + k_{1} x \\ a & = & b + k_{2} y \\ k_{1} x & = & k_{2} y \end{array}

Then, by gcd(x, y) = 1,

\begin{array}{rcl} k_{1} & = & l y \\ k_{2} & = & l x \\ a & = & b + l x y \end{array}

Therefore

C_{x y} (a, b) ◼

Exponential Identity

Define the relationship

C_{a^{q}} ((a + b)^{p}, \sum_{i = 0}^{q - 1} (\binom{p}{i}) a^{i} b^{p - i})

where

1 < q < b

Proof:

This directly follows from the binomial theorem. $◼$

Exponential Congruence Theorem

If gcd(n, a) = 1, then there exists p such that

C_{n} (a^{p}, 1)

Proof:

Assume there does not exist such p. By the Pigeonhole Principle, there exist p₁ and p₂ such that

p_{1} > p_{2} > 0, C_{n} (a^{p_{1}}, a^{p_{2}})

Then, it must be the case that either

C_{n} (a^{p_{1} - p_{2}}, 1)

or

C_{n} (a^{p_{1}}, 0)

But since p₁ - p₂ > 0, this case contradicts the assumption. Then, the second case must be true.

But

C_{n} (a^{p_{1}}, 0) \Rightarrow a^{p_{1}} = k n

which is not satisfied since gcd(n, a) = 1. Therefore, the assumption is false, and the theorem is proven. $◼$

Examples

Problem 1

Does there exist a number that is a perfect square, a multiple of 2 but not a multiple of 4?

Solution:

This is equivalent to finding n such that

n = 4 x + 2 = y^{2}

Then, if such n exists,

C_{4} (2, y^{2})

Clearly, y = 2k. But

C_{4} (2, (2 k)^{2}, 4 k^{2}, 0)

which is impossible. Therefore, n does not exist. $◼$

Problem 2

Given the function

f (x) = {\begin{cases} 1, & if x = 1 \\ x^{f (x - 1)}, & if x > 1 \end{cases}

find

R_{100} (f (2009))

Note: this is equivalent to the last 2 base 10 digits of

200 9^{200 8^{200 7^{\cdot^{\cdot^{3^{2^{1}}}}}}}

Solution:

C_{100} (f (2009), 200 9^{f (2008)}, 9^{f (2008)})

To simplify this, we look for simpler congruences. By the exponential identity, we get

C_{100} (8 1^{p}, 1 + 80 p, 1)

if p = 5k. Therefore

C_{100} (9^{f (2008)}, 9^{R_{10} (f (2008))} 9^{10 k}, 9^{R_{10} (f (2008))})

To proceed, we use the product rule to split up 10 into 2 and 5, getting

C_{2} (f (2008), 200 8^{f (2007)}, 0)

C_{5} (f (2008), 200 8^{f (2007)}, 3^{R_{4} (f (2007))} 3^{4 k}, 3^{R_{4} (f (2007))} 8 1^{k}, 3^{R_{4} (f (2007))})

for some k. To proceed, we evaluate

C_{4} (f (2007), 200 7^{f (2006)}, 3^{f (2006)}, 3^{2 k}, 9^{k}, 1)

for some k. Then

C_{5} (f (2008), 3, 8)

C_{2} (f (2008), 0, 8)

Putting the product back together, we get

C_{10} (f (2008), 8)

R_{10} (f (2008)) = 8

C_{100} (f (2009), 9^{f (2008)}, 9^{R_{10} (f (2008))}, 9^{8}, 8 1^{4}, 6 1^{2}, 21)

Therefore, our desired result is

R_{100} (f (2009)) = 21