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=kn+R_{n}(a)$

for some k.

Example:

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

Congruence

Define the relation

$C_{n}(a,\;b)\iff R_{n}(a)=R_{n}(b)$

Example:

$R_{5}(8)=R_{5}(13)\iff 3=3\iff 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}(kn+a,\;a)$

Define the axioms

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

Define the axiom

$C_{n}(a_{1},\;a_{2}),\;C_{n}(a_{2},\;a_{3})\;\cdots \;{C_{n}(a_{i-1},\;a_{i}})\iff {C_{n}(a_{1},\;a_{2},\;a_{3}\;\cdots \;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&=&cn+R_{n}(a)\\b&=&dn+R_{n}(b)\end{array}}$

Then

$C_{n}({a+b},\;{cn+R_{n}(a)+dn+R_{n}(b)},\;{n(c+d)+R_{n}(a)+R_{n}(b)},\;{R_{n}(a)+R_{n}(b)})~~\blacksquare$

Corollary:

$C_{n}(a,\;b)\iff {C_{n}(a+c,\;b+c)}$

Multiplicative Property

Define the relationship

$C_{n}(ab,\;R_{n}(a)R_{n}(b))$

Proof:

Let

${\begin{array}{rcl}a&=&cn+R_{n}(a)\\b&=&dn+R_{n}(b)\end{array}}$

Then

$C_{n}(ab,\;{cn\,dn+cn\,R_{n}(b)+R_{n}(a)\,dn+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))~~\blacksquare$

Corollary:

$C_{n}(a,\;b)\iff {C_{n}(ac,\;bc)}$

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. $\blacksquare$

Corollary:

$C_{n}(a,\;b)\iff {C_{n}(a^{c},\;b^{c})}$

where c is positive.

Divisor Rule

Define the relationship

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

where x and y are positive.

Proof:

$C_{xy}(a,\;b)\iff {R_{xy}(a)=R_{xy}(b)=r}$

for some r. Let

${\begin{array}{rcl}a&=&cxy+r\\b&=&dxy+r\end{array}}$

Then, it follows that

${\begin{array}{rcl}a&=&jx+r\\b&=&kx+r\end{array}}$

And

$C_{x}(a,\;{jx+r},\;r)$

$C_{x}(b,\;{kx+r},\;r)$

Therefore

$C_{x}(a,\;b)~\blacksquare$

Similarly for y.

Product Rule

Define the relationship

$C_{x}(a,\;b),\;C_{y}(a,\;b),\;gcd(x,\;y)=1\Rightarrow {C_{xy}(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}&=&ly\\k_{2}&=&lx\\a&=&b+lxy\end{array}}$

Therefore

$C_{xy}(a,\;b)~\blacksquare$

Exponential Identity

Define the relationship

$C_{a^{q}}((a+b)^{p},\;\sum _{i=0}^{q-1}{\tbinom {p}{i}}\,a^{i}\,b^{p-i})$

where

$1<q<b$

Proof:

This directly follows from the binomial theorem. $\blacksquare$

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}}=kn$

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

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=4x+2=y^{2}$

Then, if such n exists,

$C_{4}(2,\;y^{2})$

Clearly, y = 2k. But

$C_{4}(2,\;(2k)^{2},\;4k^{2},0)$

which is impossible. Therefore, n does not exist. $\blacksquare$

Problem 2

Given the function

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

find

$R_{100}(f(2009))$

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

$2009^{2008^{2007^{\cdot ^{\cdot ^{3^{2^{1}}}}}}}$

Solution:

$C_{100}(f(2009),\;2009^{f(2008)},\;9^{f(2008)})$

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

$C_{100}(81^{p},\;1+80p,\;1)$

if p = 5k. Therefore

$C_{100}(9^{f(2008)},\;9^{R_{10}(f(2008))}\,9^{10k},\;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),\;2008^{f(2007)},\;0)$

$C_{5}(f(2008),\;2008^{f(2007)},\;3^{R_{4}(f(2007))}\,3^{4k},\;3^{R_{4}(f(2007))}\,81^{k},\;3^{R_{4}(f(2007))})$

for some k. To proceed, we evaluate

$C_{4}(f(2007),\;2007^{f(2006)},\;3^{f(2006)},\;3^{2k},\;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},\;81^{4},\;61^{2}\;,21)$

Therefore, our desired result is

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