22.2 Modular arithmetic
Given that we now know that division really exists (as if there was ever any doubt), we can start to talk about remainders.
22.2.1 Core definitions
We say that for that
if and only if .
For , if and only if .
Proof: first we prove the \sayif direction; suppose that and where we define . In this case
and thus .
For the \sayonly if direction, things are marginally more hairy. Let us suppose that , then
Here we will apply the division algorithm (Theorem 22.1.1), which tells us that we have unique and such that
Then, it follows from that
which in turn implies that
Therefore, we can write that
from which we can show that ; as by definition there exists integer such that , and thus that
Then as it must be true that
and thus the desired equality holds.
22.2.2 The properties which make modular arithmetic
The first core property is this
If and , then
If and , then
This requires a bit of careful thinking about, but the result should be
22.2.3 Fermat’s little theorem
There is also Fermat’s non-little theorem (called Fermat’s Last Theorem which was unproven for 358 years).
Theorem 22.2.4 (Fermat’s little theorem)
Let and be two coprime integers (i.e. ) then
todo: proof (it’s by induction, or using some abstract algebra).
Find the value of
. That is, the remainder when is divided by .
The first thing to do is quickly write down that by Fermat’s Little Theorem (Theorem 22.2.4) we know that
Therefore, if we let be the quotient and the remainder of dividing by , we can then write
We have substantially simplified this problem because it is now only a problem of finding , which we can do by computing . This requires a bit of arithmetic, but (if you know the rules of modular arithmetic) nothing too horrible;
Therefore, the answer is that .
22.2.4 The Chinese remainder theorem (and related problems)
Consider the function , where is defined by . Prove or disprove whether is surjective.
This statement is false, and we can prove it like this; first note that for to be surjective it must be true that for every there exists some such that
which is equivalent to the system of congruence equations
I found it helpful to draw a number line here, e.g. something like this
Thinking about some values for and , to me at least, the problematic values will be those that are close to and (or multiples therefore). If we think about, for example, numbers which are divisible by , but one bigger than or a multiple of (i.e. divisible by with remainder ), we encounter a problem, which is this; for the specific values and we are trying to solve the system of modular equations
But there are no numbers which are both odd and even, so there exists no such that , i.e. cannot be surjective.