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
![{\displaystyle R_{n}(a)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/1cbf735cb0dd977d741f66200a478e26210dc39b)
to be the remainder when a is divided by n.
Example:
![{\displaystyle R_{5}(13)=3}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/c1ad75c8aecdfc209e287ea953fc3bd0054d4ce6)
Define the axiom
![{\displaystyle a=kn+R_{n}(a)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5e7ae1aaf6c2a8563017ed6222eda67010c7d5a1)
for some k.
Example:
![{\displaystyle 13=5k+R_{5}(13)=5(2)+3}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/63528cc8a84f18aee223e9069f4ac067cb4fe541)
Congruence
Define the relation
![{\displaystyle C_{n}(a,\;b)\iff R_{n}(a)=R_{n}(b)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4bdb82fe156be2cafd175a6845e2fb1276ebcd0e)
Example:
![{\displaystyle R_{5}(8)=R_{5}(13)\iff 3=3\iff C_{5}(8,\;13)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a8b5c867ffce8a8292b767f31960f9f8bc98dbd8)
Define the axioms
![{\displaystyle C_{n}(a,\;a)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/3219a7372b0f1c1f1e94b52ec5448559a24d3ca7)
![{\displaystyle C_{n}(a,\;R_{n}(a))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/798ea35263fe74f64515e69bd4ef2af86cad7b14)
![{\displaystyle C_{n}(a\cdot 1,\;a)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/440f6c10806d777dfe17044d7ef2b75e590d1a23)
![{\displaystyle C_{n}(kn+a,\;a)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5c017ed22009f3bdfa0a657ddf55b2c6e9835d87)
Define the axioms
![{\displaystyle {\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}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/f229d0710a394d8ee48041bdadbcb8e7d49143e0)
Define the axiom
![{\displaystyle 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})}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b8a6487f68373468e365ad1a96f9a9064e07bd19)
where i is any positive integer.
Theorems
Additive Property
Define the relationship
![{\displaystyle C_{n}(a+b,\;R_{n}(a)+R_{n}(b))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b33262de54ffc7175f9027efe031ef083be450a3)
Proof:
Let
![{\displaystyle {\begin{array}{rcl}a&=&cn+R_{n}(a)\\b&=&dn+R_{n}(b)\end{array}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/1a88d677ffd0cf402997eb41621f10a524895394)
Then
![{\displaystyle 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 }](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/341c780a511822a1f17697e1bb34096c50844a41)
Corollary:
![{\displaystyle C_{n}(a,\;b)\iff {C_{n}(a+c,\;b+c)}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4dcbffea6abf230bb71c75d9656aaab19ad8c6ff)
Multiplicative Property
Define the relationship
![{\displaystyle C_{n}(ab,\;R_{n}(a)R_{n}(b))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/e14c2c41486a31d3e9a776a19c9a3a78580fe971)
Proof:
Let
![{\displaystyle {\begin{array}{rcl}a&=&cn+R_{n}(a)\\b&=&dn+R_{n}(b)\end{array}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/1a88d677ffd0cf402997eb41621f10a524895394)
Then
![{\displaystyle 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 }](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/8cf80f39f7465304a7f7f80a383dd6437ea091cc)
Corollary:
![{\displaystyle C_{n}(a,\;b)\iff {C_{n}(ac,\;bc)}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/afc8d09c7ab2a0d2a6a2d9e5b412d1d2229d0539)
Exponential Property
Define the relationship
![{\displaystyle C_{n}(a^{b},\;(R_{n}(a))^{b})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/ae14dfe8d9afc26aaca02aa757054f94d0ee1962)
where b is positive.
Proof:
Assume this relation holds for some b. Then
![{\displaystyle 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})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/6aa8b701892e38db992c42e3f700409de875f260)
Therefore, it follows that if this relation holds for b, it also holds for b + 1. Let b = 1. Then
![{\displaystyle C_{n}(a^{1},\;(R_{n}(a))^{1})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/ea191db10d5a73692b5f285339bdc0802c16a04d)
![{\displaystyle C_{n}(a,\;(R_{n}(a)))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/1283189f1a9e0ea69e92cd5f18df40626462fdaf)
This holds true. Therefore, this relation holds true for any positive b.
Corollary:
![{\displaystyle C_{n}(a,\;b)\iff {C_{n}(a^{c},\;b^{c})}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/88a83516b67be3a3d6392585c2e13fb081221c2d)
where c is positive.
Divisor Rule
Define the relationship
![{\displaystyle C_{xy}(a,\;b)\Rightarrow {C_{x}(a,\;b),\;C_{y}(a,\;b)}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/833082ae4e6f0ade8156fe5311974adbefc13106)
where x and y are positive.
Proof:
![{\displaystyle C_{xy}(a,\;b)\iff {R_{xy}(a)=R_{xy}(b)=r}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/849d16631573a9d5ac10c45dd1cc46238ef7ee71)
for some r. Let
![{\displaystyle {\begin{array}{rcl}a&=&cxy+r\\b&=&dxy+r\end{array}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/e17fcf1c7f146be801be9f3d467f23c9bdfa430e)
Then, it follows that
![{\displaystyle {\begin{array}{rcl}a&=&jx+r\\b&=&kx+r\end{array}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/df063830888357e4996aa586636da04ed8dc322b)
And
![{\displaystyle C_{x}(a,\;{jx+r},\;r)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/358ae1a6ff4034eed423bb06bc83d3e8f41b6153)
![{\displaystyle C_{x}(b,\;{kx+r},\;r)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5f4fe8f47db88a0212bafeb786400fd8c0d0d6a0)
Therefore
![{\displaystyle C_{x}(a,\;b)~\blacksquare }](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b5d42ec29d022a3df8f23bc3413fba07dcb49ac8)
Similarly for y.
Product Rule
Define the relationship
![{\displaystyle C_{x}(a,\;b),\;C_{y}(a,\;b),\;gcd(x,\;y)=1\Rightarrow {C_{xy}(a,\;b)}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b511c5820b30e39d3b1ec67af7858661aeb144fb)
where x and y are positive, and gcd is the greatest common divisor function.
Proof:
Let
![{\displaystyle {\begin{array}{rcl}a&=&b+k_{1}{x}\\a&=&b+k_{2}{y}\\k_{1}{x}&=&k_{2}{y}\end{array}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a9e4fa34242f3f4084d3953d3002948a642b8db5)
Then, by gcd(x, y) = 1,
![{\displaystyle {\begin{array}{rcl}k_{1}&=&ly\\k_{2}&=&lx\\a&=&b+lxy\end{array}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/22d0360ccb87f471cd7761c78c0d389fd6048c87)
Therefore
![{\displaystyle C_{xy}(a,\;b)~\blacksquare }](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/73af213aadb0ddd88932d976b78292099d6de6e3)
Exponential Identity
Define the relationship
![{\displaystyle C_{a^{q}}((a+b)^{p},\;\sum _{i=0}^{q-1}{\tbinom {p}{i}}\,a^{i}\,b^{p-i})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/be3d81398c7bc5286c4efa77be44c1787562b331)
where
![{\displaystyle 1<q<b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/f4fb005967001530051ee957483c648e524796da)
Proof:
This directly follows from the binomial theorem.
Exponential Congruence Theorem
If gcd(n, a) = 1, then there exists p such that
![{\displaystyle C_{n}(a^{p},\;1)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/381f9171016a8cdaf2d02c93312555988ab31f54)
Proof:
Assume there does not exist such p. By the Pigeonhole Principle, there exist p1 and p2 such that
![{\displaystyle p_{1}>p_{2}>0,\;C_{n}(a^{p_{1}},\;a^{p_{2}})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/377c987e953f09e03b8f9eca69b5f9fa84ae4467)
Then, it must be the case that either
![{\displaystyle C_{n}(a^{p_{1}-p_{2}},\;1)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5a43dcd8f49ec90aeba17ede2d8f44b1af82da0d)
or
![{\displaystyle C_{n}(a^{p_{1}},\;0)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/cfb68c8c2ba56939bfa0d7fd0a39020ec5d6fbe6)
But since p1 - p2 > 0, this case contradicts the assumption. Then, the second case must be true.
But
![{\displaystyle C_{n}(a^{p_{1}},\;0)\Rightarrow a^{p_{1}}=kn}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/aff73f84a76b1aec0ff1248349bdede0659905bf)
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
![{\displaystyle n=4x+2=y^{2}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4eb7e0a2ce77ed3b50c72f4068ca1b8479601516)
Then, if such n exists,
![{\displaystyle C_{4}(2,\;y^{2})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/85caec939acd0b22eecdb30bc276b6a24fdc247d)
Clearly, y = 2k. But
![{\displaystyle C_{4}(2,\;(2k)^{2},\;4k^{2},0)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a448bd0776fe35804fbadd3e836d4506ead8f3e4)
which is impossible. Therefore, n does not exist.
Problem 2
Given the function
![{\displaystyle f(x)={\begin{cases}1,&{\mbox{if }}x=1\\x^{f(x-1)},&{\mbox{if }}x>1\end{cases}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/7dabd61dbd8a00cf6dd6a7e7e68875305662e408)
find
![{\displaystyle R_{100}(f(2009))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4ee3c47e9f910a69f215f5ddd5655f5905a712df)
Note: this is equivalent to the last 2 base 10 digits of
![{\displaystyle 2009^{2008^{2007^{\cdot ^{\cdot ^{3^{2^{1}}}}}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/034fa98346c45d74024b3dc1fa617415be29a89b)
Solution:
![{\displaystyle C_{100}(f(2009),\;2009^{f(2008)},\;9^{f(2008)})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2ac6e17eba9651c27984db8c7cfe9fabd9fc9282)
To simplify this, we look for simpler congruences. By the exponential identity, we get
![{\displaystyle C_{100}(81^{p},\;1+80p,\;1)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/9e733cde1212bb5d4965a8987797d6567ab9dda6)
if p = 5k. Therefore
![{\displaystyle C_{100}(9^{f(2008)},\;9^{R_{10}(f(2008))}\,9^{10k},\;9^{R_{10}(f(2008))})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/62681ea319b8166d0cecc1d58108928d943f9cc5)
To proceed, we use the product rule to split up 10 into 2 and 5, getting
![{\displaystyle C_{2}(f(2008),\;2008^{f(2007)},\;0)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4e17f37717cb29e77f4c604568f014c1181f7ba1)
![{\displaystyle 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))})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a4c9fc0530a7e1f8a4eaaed24ac68f030fe823cd)
for some k. To proceed, we evaluate
![{\displaystyle C_{4}(f(2007),\;2007^{f(2006)},\;3^{f(2006)},\;3^{2k},\;9^{k},\;1)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2fe6b7826fdf6244df38feda0a540c8337f2507c)
for some k. Then
![{\displaystyle C_{5}(f(2008),\;3,\;8)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/53be3941ec24fa853608f3204c42bbe999da0deb)
![{\displaystyle C_{2}(f(2008),\;0,\;8)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4ba6ca1bd149f8bd5d63ce4fa5387f4eb8f36c5a)
Putting the product back together, we get
![{\displaystyle C_{10}(f(2008),\;8)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/08a07fca0fa3df8ba0cf09a9cb986151d106f669)
![{\displaystyle R_{10}(f(2008))=8}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5f7f1c3999edd0d6d7c22c3e72f30992ecaedd38)
![{\displaystyle C_{100}(f(2009),\;9^{f(2008)},\;9^{R_{10}(f(2008))},\;9^{8},\;81^{4},\;61^{2}\;,21)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/7168e7c2b9402cb6b0af8909b6edd16404bb570f)
Therefore, our desired result is
![{\displaystyle R_{100}(f(2009))=21}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/1783f343b30feded28eb4cc45a8b3c0d94409e84)