Congruence
Fix an integer \( m \) called the modulus, then say \( a \equiv b \left ( \operatorname{mod} m \right ) \) if and only if \( m | b - a \)

It is not immediately clear why we prefer the above definition, it's most important property follows below:

congruence iff same remainder
\( a , b \in \mathbb{Z} \) are congruent modulo \( m \) if and only if \( a \% m \) \( = b \% m \)

note: this means that \( a \) and \( b \) have the same remainder upon division by \( m \)

Suppose that \( a \equiv b \left ( \operatorname{mod} m \right ) \), so we know \( m | b - a \), then we can write \( b = k_{b} m + r_{b} \) and \( a = k_{a} m + r_{a} \) so that \( b - a = m \cdot \left ( k_{b} + k_{a} \right ) + k_{b} - k_{a} \) thus \( m | k_{b} - k_{a} \).

Notice that \( 0 \le k_{a} , k_{b} \lt \left | m \right | \) also we know that \( k_{a} \ne k_{b} \) therefore \( k_{b} - k_{a} \ne 0 \) so then \( - \left | m \right | \lt k_{b} - k_{a} \lt \left | m \right | \)

Congruence Commutes
Let \( a, b, m \in \mathbb{ Z } \) then \[ a \equiv b \left( \operatorname{ mod } m \right) \iff b \equiv a \left( \operatorname{ mod } m \right) \]
Division iff Congruent Mod 0
Let \( a, b \in \mathbb{ Z } \) such that \( a \neq 0 \), then \[ a \mid b \iff b \equiv 0 \left( \operatorname{ mod } a \right) \]
\( a \mid b \) if and only if \( a \mid b - 0 \) iff \( 0 \equiv b \left( \operatorname{ mod } a \right) \) iff \( b \equiv 0 \left( \operatorname{ mod } a \right) \) as needed.
Congruence is Transitive
Let \(a, b, c, m \in \mathbb{Z} \) such that \( a \equiv b \left( \operatorname{ mod } m \right) \) and \( b \equiv c \left( \operatorname{ mod } m \right) \), then we have that \[ a \equiv c \left( \operatorname{ mod } m \right) \]
TODO
Sum of Two Congruent Numbers are Congruent
Suppose that \( a \equiv b \left( \operatorname{ mod } m \right) \) and that \( c \equiv d \left( \operatorname{ mod } m \right) \) then we know that \[ a + c \equiv b + d \left( \operatorname{ mod } m \right) \]
Product of Two Congruent Numbers is Congruent
Suppose that \( a \equiv b \left( \operatorname{ mod } m \right) \) and that \( c \equiv d \left( \operatorname{ mod } m \right) \) then we know that \[ a c \equiv b d \left( \operatorname{ mod } m \right) \]

Note that we don't have the same theorem about division, we can observe that in general this is false, because any odd square has remainder 1, upon division by four, so that \( 5 ^ 2 \equiv 3 ^ 2 \left( \operatorname{ mod } 4 \right) \) but we can see that \( 5 \equiv 3 \left( \operatorname{ mod } 4 \right) \) is false.

Congruent Numbers raised to Congruent Powers may not be Congruent
Suppose that \( a \equiv b \left( \operatorname{ mod } n \right) \) and \( c \equiv d \left( \operatorname{ mod } n \right) \), then its NOT true that \[ a ^ c \equiv b ^ d \left( \operatorname{ mod } n \right) \]
Consider \( 2 \equiv 5 \left( \operatorname{ mod } 3 \right) \) but then \( 2 ^ 5 \equiv 2 \) whereas \( 5 ^ 2 \equiv 1 \) so \( 2 ^ 5 \not \equiv 5 ^ 2 \left( \operatorname{ mod } 3 \right) \)
If two Two Numbers are Congruent, they are still Congruent mod a divisor of the Original Mod
Suppose that \( a \equiv b \left( \operatorname{ mod } n \right) \) and \( m \mid n \) then \( a \equiv b \left( \operatorname{ mod } m \right) \)
Since \( a \equiv b \left( \operatorname{ mod } n \right) \) then we know that \( n \mid b - a \) but also \( m \mid n \) so that \( m \mid b - a \) therefore \( a \equiv b \left( \operatorname{ mod } m \right) \) as needed.

Note that if instead we required that \( n \mid m \) then the above would not be true because we see that \( 3 \equiv 6 \left( \operatorname{ mod } 3 \right) \) but \( 3 \not \equiv 6 \left( \operatorname{ mod } 6 \right) \)

If Two Numbers are Congruent Using Two Different Moduli they are Congruent Using the LCM
Suppose that \( a \equiv b \left( \operatorname{ mod } n \right) \) and that \( a \equiv b \left( \operatorname{ mod } m \right) \) then \[ a \equiv b \left( \operatorname{ mod } \operatorname{ lcm } \left( n, m \right) \right) \]
We have that \( m, n \mid a - b \) but the definition of the LCM then states that \( lcm \left( n, m \right) \mid a - b \)
Switching Prime Powers
Let \( p \neq q \in \mathbb{ P } \) then \[ p ^ { q - 1 } + q ^ { p - 1 } \equiv 1 \pmod{ pq } \]
FLT tells us that \[ p ^ { q - 1 } \equiv 1 \pmod{ q } \text{ and } q ^ { p - 1 } \equiv 1 \pmod{ p } \] but since \( p - 1, q - 1 \ge 1 \) then we know that \[ q ^ { p - 1 } \equiv 0 \pmod{ q } \text{ and } p ^ { q - 1 } \equiv 0 \pmod{ p } \] therefore we know that \[ p ^ { q - 1 } + q ^ { p - 1 } \equiv 1 \pmod{ q } \text{ and } q ^ { p - 1 } + p ^ { q - 1 } \equiv 1 \pmod{ p } \] since \( \operatorname{ lcm } \left( p, q \right) = pq \cdot \gcd \left( p, q \right) \) and we know that \( p \neq q \in \mathbb{ P } \) then \( \gcd \left( p, q \right) = 1 \) so that \( \operatorname{ lcm } \left( p, q \right) = p \cdot q \) then we conclude that \[ p ^ { q - 1 } + q ^ { p - 1 } \equiv 1 \pmod{ pq } \]
a p q
Suppose that \( a \in \mathbb{ Z } \) and that \( p \neq q \in \mathbb{ P } \), then \[ a ^ { pq } - a ^ p - a ^ q + a \equiv 0 \pmod{ pq } \]
By FLT, we know that \[ a ^ { pq } - a ^ p - a ^ q + a \equiv \left( a ^ p \right) ^ q - a ^ p - a ^ q + a \equiv a ^ q - a - a ^ q + a = 0 \pmod{ p } \] and symetrically the same thing occurs mod \( q \) therefore \[ a ^ { pq } - a ^ p - a ^ q + a \equiv 0 \pmod{ pq } \]
Division by a Common Factor Maintains Congruence
Suppose that \( a \equiv b \left( \operatorname{ mod } m \right) \) then if \( k \mid a, b, m \) then we have that \[ \frac{a}{k} \equiv \frac{b}{k} \left( \operatorname{ mod } \frac{m}{k} \right) \]
Recall that \( \frac{a}{k} \equiv \frac{b}{k} \left( \operatorname{ mod } \frac{m}{k} \right) \) iff \( \frac{m}{k} \mid \frac{a}{k} - \frac{b}{k} \) but we know that statement is true because since \( m \mid a - b \) and we by linearity we know that \( k \mid a - b \) therefore it holds true.
Division by a Common Factor Maintains Congruence if Mod is Divided by GCD
Let \( a, b, m, k \in \mathbb{ Z } \) such that \( k \neq 0 \) and suppose that \( a \equiv b \left( \operatorname{ mod } m \right) \) then if \( k \mid a, b \) then \[ \frac{a}{k} \equiv \frac{b}{k} \left( \operatorname{ mod } \frac{m}{\gcd \left( m, k \right) } \right) \]

Let \( g := \gcd \left( m, k \right) \) our goal is to prove that \( \frac{m}{g} \mid \frac{a}{k} - \frac{b}{k} \), towards this note that we have \( a \equiv b \left( \operatorname{ mod } m \right) \) which means that \( m \mid a - b \) so there is some \( r \in \mathbb{ Z } \) such that \( a - b = m r \) therefore dividing by \( g \neq 0 \) we have \[ \frac{a - b}{g} = \frac{m}{g} r \]

Recall that we want \( k \) in the denominator, to get there we recall that \( g \mid k \) and so there is some \( j \in \mathbb{ Z } \) such that \( k = g j \), since \( k \neq 0 \) then \( gj \neq 0 \) so \( j \neq 0 \) thus we divide our previous equation by \( j \) to obtain \[ \frac{a - b}{gj} = \left( \frac{m}{g} r \right) \frac{1}{j} \iff \frac{a - b}{k} = \left( \frac{m}{g} r \right) \frac{1}{j} \] Since \( k \mid a, b \) then \( k \mid a - b \) so \( \frac{a - b}{k} \in \mathbb{ Z } \) thus \( \left( \frac{m}{g} r \right) \frac{1}{j} \in \mathbb{ Z } \) and therefore \( j \mid \frac{m}{g} r \).

Note that \( j \mid k \) and \( \frac{m}{g} \mid m \) therefore \( \gcd \left( j, \frac{m}{g} \right) = 1 \) therefore \( j \mid r \) so that \( \frac{r}{j} \in \mathbb{ Z } \) thus we have the equation \[ \frac{a - b}{k} = \frac{a}{k} - \frac{b}{k} = \frac{m}{g} \frac{r}{j} \] where we know the left hand side is an integer, \( \frac{r}{j} \) is and so is \( \frac{m}{g} \) therefore \( \frac{m}{g} \mid \frac{a}{k} - \frac{b}{k} \) so that \[ \frac{a}{k} \equiv \frac{b}{k} \left( \operatorname{ mod } m \right) \] as needed.

Multiplicative Cancellation if Mod Prime
Suppose that \( p \) is prime and that \( ka \equiv kb \left( \operatorname{ mod } p \right) \) and \( p \nmid k \) then \[ a \equiv b \left( \operatorname{ mod } p \right) \]
Since \( p \nmid k \) then we know that \( \gcd \left( p, k \right) = 1 \) therefore the result follows from the previous proposition.
n Consecutive Numbers have Unique Remainders Mod n
For any \( m \in \mathbb{ N } _ 1 \) \[ \forall x, y \in \left[ 0, \ldots m - 1 \right], \left( x \neq y \iff x \not \equiv y \left( \operatorname{ mod } m \right) \right) \]

\( \implies \) Suppose that \( x \neq y \) but that \( x \equiv y \left( \operatorname{ mod } m\right) \) for the sake of contradiction, without loss of generality assume that \( x \gt y \). Since they're congruent we have \[ m \mid x - y \] but we know that \( x - y \le m - 1 - 0 = m - 1 \) but if \( m \mid x - y \) we have \( m \le x - y \le m - 1 \) so \( m \le m - 1 \) which is impossible, therefore we must have that \( x \not \equiv y \left( \operatorname{ mod } m \right) \).

\( \impliedby \) Now suppose that \( x \not \equiv y \left( \operatorname{ mod } m \right) \) therefore \( x ~\%~ m \neq y ~\%~ m \) but since \( x, y \in \left[ 0, \ldots, m - 1 \right] \) then \( x = x ~\%~ m \) and \( y = y ~\%~ m \) therefore \( x \neq y \) as needed.

When a Linear Modular Equation has a Solution
The equation \[ ax \equiv b \left( \operatorname{ mod } m \right) \] has a solution iff \( \gcd \left( a, m \right) \mid b \)
Note that \( ax \equiv b \left( \operatorname{ mod } m \right) \) iff \( m \mid ax - b \) so there is some \( k \in \mathbb{ Z } \) such that \( ax - b = mk \) so that \( ax - mk = b \) this has a solution iff \( \gcd \left( a, m \right) \mid b \)
Relatively Prime Modular Equation has a Solution
Suppose that we have the equation: \[ ax \equiv b \left( \operatorname{ mod } m \right) \] where \( \gcd \left( a, m \right) = 1 \) then it has a solution.
Since \( \gcd \left( a, m \right) = 1 \mid b \) it has a solution.
Modular Inverse
Given \( a, m \in \mathbb{ Z } \) we say that an integer \( x \in \mathbb{ Z } \) is a the modular inverse for \( a \) mod \( m \) when: \[ a \cdot x \equiv 1 \left( \operatorname{ mod } m \right) \]

When a given number has an inverse we say that it is invertible.

When a Rational Can be Converted to a Modular Inverse
Suppose that \( a, b \in \mathbb{ Z } \) and \( m \in \mathbb{ N } _ 1 \) such that \( b \) is invertible mod \( m \) and \( \frac{a}{b} \in \mathbb{ Z } \) then: \[ a \cdot b ^ { -1 } \equiv \frac{a}{b} \pmod{ m } \] where the right hand side is interpreted as division of integers.
Note that since \( b \mid a \) then there is some \( k \in \mathbb{ Z } \) such that \( a = bk \) therefore \[ a \equiv bk \pmod{ p } \iff b ^ { -1 } a \equiv k \iff a b ^ { -1 } \equiv \frac{a}{b} \pmod{ p } \]
2p Choose p
Prove that \[ \binom{2p}{p} \equiv 2 \pmod{ p } \]
We have that \[ \binom{2p}{p} = \frac{\left( p + 1 \right) \cdots \left( p + p - 1 \right) \left( 2p \right) }{p!} = \frac{\left( p + 1 \right) \cdots \left( p + p - 1 \right) 2 }{\left( p - 1 \right) !} \in \mathbb{ Z } \] therefore \[ \begin{align} \frac{\left( p + 1 \right) \cdots \left( p + p - 1 \right) 2 }{\left( p - 1 \right) !} &\equiv \left( p + 1 \right) \cdots \left( p + p - 1 \right) 2 \left[ \left( p - 1 \right) ! \right] ^ { -1 } \\ &\equiv 2 \left( p - 1 \right) ! \left[ \left( p - 1 \right) ! \right] ^ { -1 } \\ &\equiv 2 \pmod{ p } \end{align} \]
Every Non Zero Number is Invertible Mod a Prime
For any \( p \in \mathbb{ P } \) \( a \in \mathbb{ Z } \) such that \( p \nmid a \) there exists \( b \in \left[ 1, \ldots , p - 1 \right] \) such that \[ ab \equiv 1 \pmod{ p } \]
Consider the equation \( a x \equiv 1 \pmod{ p } \), since \( \gcd \left( a, p \right) = 1 \) then it has a solution, as needed.
A Linear Modular Equation with a Solution has GCD many Solutions
Suppose that \[ ax \equiv b \left( \operatorname{ mod } m \right) \] has a solution \( x _ 0 \) , then it has exactly \( g := \gcd \left( a, m \right) \) solutions mod \( m \). Moreover the unique solutions are given by the remainders of \[ x _ 0, x _ 0 + \frac{1m}{g} , x _ 0 + \frac{2m}{g} , \ldots , x _ 0 + \frac{\left( g - 1 \right) m }{g} \] when taken mod \( m \)

Since it has a solution, we have an \( x _ 0 \in \mathbb{ Z } \) such that \( a x _ 0 \equiv b \left( \operatorname{ mod } m \right) \), so therefore \( m \mid a x _ 0 - b \) so that \( a x _ 0 - b = m k \) for some \( k \in \mathbb{ Z } \) therefore \( a x _ 0 + m \left( -k \right) = b \).

Recall that we have a method of obtaining more solutions once we have one, and hence are given by \[ \left( x _ 0, -k \right) + \left( \frac{m}{g}, - \frac{a}{g} \right) t, \text{ where } t \in \mathbb{ Z } \] Note that for each new solution \( \overline{ x } , \overline{ y } \) it satisfies \( a \overline{ x } + m \overline{ y } = b \) so that \( a \overline{ x } - b = - \overline{ y } m \) so that \( m \mid a \overline{ x } - b \) so that \( a \overline{ x } \equiv b \left( \operatorname{ mod } m \right) \), therefore we only need to observe the \( x \) component of each of solutions obtained from the equation

With this we observe the solutions: \[ \ldots x _ 0 - \frac{m}{g} , x _ 0, x _ 0 + \frac{1m}{g} , x _ 0 + \frac{2m}{g} , \ldots , x _ 0 + \frac{\left( g - 1 \right) m }{g} , x _ 0 + \frac{gm}{g} = x _ 0 + m, \ldots \] and note that for any \( t \in \mathbb{ Z } \) such that \( t \ge g \) then \( t = qg + r\) where \( r \in \left[ 0, \ldots g - 1 \right] \) \[ x _ 0 + \frac{tm}{g} = x _ 0 + qm + \frac{r}{g} \equiv x _ 0 + \frac{r}{g} \left( \operatorname{ mod } m \right) \] which is to say that it is congruent to a solution of the form \( x _ 0 + \frac{jm}{g} \) where \( j \in \left[ 0, \ldots , g - 1 \right] \) similarly any solution that is of the form \( x _ 0 + \frac{nm}{g} \) where \( n \lt 0 \) can be turned into one of these solutions by repetitively adding \( m \).

This shows that the entire solution set mod \( m \) is given by \[ x _ 0, x _ 0 + \frac{1m}{g} , x _ 0 + \frac{2m}{g} , \ldots , x _ 0 + \frac{\left( g - 1 \right) m }{g} \] we'll now verify that every pair of solutions are incongruent mod \( m \) to show that there are \( g \) total solutions.

So suppose for the sake of contradiction that \( x _ 0 + \frac{lm}{g} \equiv x _ 0 + \frac{pm}{g} \left( \operatorname{ mod } m \right) \) where \( l, p \in \left[ 0, \ldots , g - 1 \right] \) and without loss of generality \( l \gt p \) so that \( m \mid \frac{lm}{g} - \frac{pm}{g} = \frac{m}{g} \left( l - p \right) \) since \( l, p \in \left[ 0, \ldots g - 1 \right] \) then \( l - p \le g - 1 \) so that \( \frac{m}{g} \left( l - p \right) \lt \frac{m}{g} g = m \) which means that \( m \) divides a number smaller than it, which is impossible so that \( x _ 0 + \frac{lm}{p} \not \equiv x _ 0 + \frac{pm}{g} \) as needed.

Note that modulo a prime, since the gcd is always one, then this shows that every element has a unique inverse mod p.

24 and 60
Find all incongruent solutions of the linear congruence given by \[ 24 x \equiv 60 \pmod{ 102 } \]

First we verify that the above has a solution, since \( 102 = 17 \cdot 6 \), then \( \gcd \left( 24, 102 \right) = 6 \) and so \( \gcd \left( 24, 102 \right) \mid 60 \), so we deduce that \( 24 x \equiv 60 \pmod{ 102 } \) has a solution, call it \( x _ 0 \).

Since it has a solution, then we know that it actually has \( \gcd \left( 24, 102 \right) = 6 \) solutions explicitly given by \[ x _ 0 + \left( \frac{102}{6} \right) k \] for \( k \in \left[ 0, \ldots, 5 \right] \). Now to actually find a solution, we can divide through by \( 6 \) which yields \( 4x \equiv 10 \pmod{ 17 } \) since \( 17 \) is prime, then we know that \( 4 \) has an inverse, we can see that \( -4 \) works, so that \( x \equiv -40 \equiv 11 \pmod{ 17 } \) so our solutions are given by \[ 11 + 17k \] for \( k \in \left[ 0, \ldots , 5 \right] \) mod \( 102 \)

Chinese Remainder
Suppose that for some \( l \in \mathbb{ N } _ 1 \) we have that \( x \equiv c _ i \left( \operatorname{ mod } m _ i \right) \) for each \( i \in \left[ 1, \ldots , l \right] \) such that for any \( i \lt j \in \left[ 1, \ldots , l \right] \) we have \( \gcd \left( m _ i, m _ j \right) = 1 \), then there is a unique \( x \) satisfying the modular equations \( \left( \operatorname{ mod } \prod _ { i = 1 } ^ { l } m _ i \right) \)

Set \( M = \prod _ { i = 1 } ^ { l } m _ i \), then clearly we have that \( M \equiv 0 \left( \operatorname{ mod } m _ i \right) \). Now recall the following fact, and that it can be extended to finite products by induction which shows that \( \gcd \left( \frac{M}{m _ j}, m _ j \right) = 1 \) for any \( j \in \left[ 1, \ldots , l \right] \). Therefore we obtain a solution to the equation \( \frac{M}{m _ j} x \equiv 1 \left( \operatorname{ mod } m _ j \right) \), let this solution be denoted by \( x _ j \).

As just discussed we obtained a solution \( x _ j \) such that \( \frac{M}{m _ j} x _ j \equiv 1 \left( \operatorname{ mod } m _ j \right) \), in other words \( \frac{M}{m _ j} x _ j c _ j \equiv c _ j \left( \operatorname{ mod } m _ j \right) \) and so we've found \( l \) different solutions to each of the congruence equations we required, but we need to find one solution to all of them.

Note that \( \frac{M}{m _ j} \equiv 0 \left( \operatorname{ mod } m _ i \right) \) for any \( i \neq j \) so that \( \frac{M}{m _ j} x _ j c _ j \equiv 0 \left( \operatorname{ mod } m _ i \right) \) as well, with this fact we see that \[ S := \sum _ { i = 1 } ^ { l } \frac{M}{m _ j} x _ j c _ j \] has the following property \[ S \equiv 0 + 0 + \cdots c _ j + 0 + 0 \equiv c _ j \left( \operatorname{ mod } m _ j \right) \] in other words using \( x = S \) works.


We now show that the solution is unique. Suppose that \( y \) is another solution to all of the modular equations then we'll prove that \( x \equiv y \left( \operatorname{ mod } \prod _ { i = 1 } ^ { l } m _ i \right) \)

Seven Divides Ones and Threes
Show that \[ 7 \mid \left( 111 ^ { 333 } + 333 ^ { 111 } \right) \]

\( 111 = 7 \cdot 15 + 6 \) therefore \( 111 \equiv 6 \equiv -1 \left( \operatorname{ mod } 7 \right) \) therefore \( 111 ^ { 2 k + 1 } \equiv -1 \) so therefore \( 111 ^ { 333 } \equiv -1 \left( \operatorname{ mod } 7 \right) \).

Now note that \( 333 \equiv 3 \left( 111 \right) \equiv 3 \left( -1 \right) \equiv -3 \left( \operatorname{ mod } 7 \right) \), consider the following \[ \begin{align} -3 ^ 1 &\equiv -3 \left( \operatorname{ mod } 7 \right) \\ -3 ^ 2 &\equiv 2 \left( \operatorname{ mod } 7 \right) \\ -3 ^ 3 &\equiv 1 \left( \operatorname{ mod } 7 \right) \end{align} \] therefore \[ \left( -3 \right) ^ { 3 k + i } \equiv \begin{cases} -3 &\text{ if } i = 1 \\ 2 &\text{ if } i = 2 \\ 1 &\text{ if } i = 0 \end{cases} \] since the sum of the digits of \( 111 = 3 \) then \( 3 \mid 111 \) and therefore \( 3 ^ { 111 } \equiv 1 \) therefore \[ 111 ^ { 333 } + 333 ^ { 111 } \equiv -1 + 1 \equiv 0 \] therefore \( 7 \mid 111 ^ { 333 } + 333 ^ { 111 } \) as needed.

Alternating Congruence Again
Prove that \[ 39 \mid \left( 53 ^ { 103 } + 103 ^ { 53 } \right) \]
Note that \( 53 = 39 + 14 \) thus \( 53 \equiv 14 \left( \operatorname{ mod } 39 \right) \), looking at \( 14 ^ 2 = \left( 10 + 4 \right) 14 = 140 + 56 = 196 \), then since \( 39 \cdot 5 = \left( 40 - 1 \right) 5 = 200 - 5 = 195 \) then we see that \( 196 = 39 \cdot 5 + 1 \) so that \( 14 ^ 2 \equiv 1 \left( \operatorname{ mod } 39 \right) \) therefore we have that \[ 14 ^ k \equiv \begin{cases} 14 &\text{ if } k \text{ odd }\\ 1 &\text{ if } k \text{ even } \end{cases} \] therefore \( 53 ^ { 103 } \equiv 14 ^ { 103 } \equiv 14 \). Now we look at \( 103 = 2 \cdot 39 + 25 \) so that \( 103 \equiv 25 \) now \( 25 ^ 2 = 625 \) since we see that \( 16 \cdot 39 = 16 \left( 40 - 1 \right) = \left( 400 + 240 \right) - 16 = 640 - 16 = 624 \) then \( 625 = 16 \cdot 39 + 1 \) so that \( 25 ^ 2 \equiv 1 \) so we deduce that \[ 25 ^ k \equiv \begin{cases} 25 &\text{ if } k \text{ odd }\\ 1 &\text{ if } k \text{ even } \end{cases} \] therefore \( 103 ^ { 53 } \equiv 25 ^ { 53 } \equiv 25 \) so then \[ 53 ^ { 103 } + 103 ^ { 53 } \equiv 14 + 25 \equiv 39 \equiv 0 \] therefore we know that \( 39 \mid 53 ^ { 103 } + 103 ^ { 53 } \)
43 Divides a Sum of Powers of 6 and 7
Show that \[ 43 \mid \left( 6 ^ { n + 2 } + 7 ^ { 2 n + 1 } \right) \]
Note that \[ \begin{align} 6 ^ 1 &\equiv 6 \left( \operatorname{ mod } 43 \right) \\ 6 ^ 2 &\equiv 36 \left( \operatorname{ mod } 43 \right) \\ 6 ^ 3 &\equiv 3 \cdot 36 \equiv 130 + 36 \equiv 216 \left( \operatorname{ mod } 43 \right) \\ \end{align} \]

Note that \( 216 = 43 \cdot 5 + 1 \) therefore \( 6 ^ 3 \equiv 1 \left( \operatorname{ mod } 43 \right) \) therefore the modular power sequence is given by \( \left( 6, 36, 1, 6, 36, 1, \ldots \right) \). Therefore if we look at \( a _ n = 6 ^ { n + 2 } \) then \( \left( a _ n \right) = \left( 1, 6, 36, 1, 6 , 36, \ldots \right) \)

Now we'll look at \( 7 \) power sequence mod \( 43 \) we have \[ \begin{align} 7 &\equiv 7 \left( \operatorname{ mod } 43 \right) \\ 7 ^ 2 &\equiv 49 \equiv 6 \left( \operatorname{ mod } 43 \right) \\ 7 ^ 3 &\equiv 6 \cdot 7 \equiv 42 \equiv -1 \left( \operatorname{ mod } 43 \right) \\ 7 ^ 4 &\equiv -1 \cdot 7 \equiv -7 \left( \operatorname{ mod } 43 \right) \\ 7 ^ 5 &\equiv 7 ^ 3 7 ^ 2 \equiv \left( -1 \right) 6 \left( \operatorname{ mod } 43 \right) \\ 7 ^ 6 &\equiv 7 \left( -6 \right) \equiv -42 \equiv 1 \left( \operatorname{ mod } 43 \right) \end{align} \] therefore it's power sequence mod \( 43 \) is \( \left( b _ n \right) = \left( 7, 6, -1, -7, -6, 1, 7, 6, -1, -7, -6, 1, \ldots \right) \), therefore the power sequence of \( 7 ^ { 2n + 1 } \) is given by \( \left( c _ n \right) = \left( -1, -6, 7, -1, -6, 7, \ldots \right) \), therefore \( x _ n = 6 ^ { n + 2 } + 7 ^ { 2n + 1 } \) is given by \[ \begin{align} \left( x _ n \right) &= \left( 1, 6, 36, 1, 6, 36, \ldots \right) \\ &+ \left( -1, -6, 7, -1, -6, 7, \ldots \right) \\ &= \left( 0, 0, 43, 0, 0, 43, \ldots \right) \end{align} \] Since \( x _ n \equiv 0 \left( \operatorname{ mod } 43 \right) \) for every \( n \) as needed.

Remainder of a Sum of Powers
Find \[ \left( \sum _ { i = 1 } ^ { 100 } i ^ 5 \right) ~\%~ 4 \]
For \( i \) odd, then recall that \( i ^ 2 \) is an odd perfect square and thus \( i ^ 2 ~\%~ 4 = 1 \) therefore \( i ^ 5 = i ^ 2 i ^ 2 i = i \), also when \( i \) is even, then \( i ^ 5 ~\%~ 4 = 0 \) therefore we know that \[ \left( \sum _ { i = 1 } ^ { 100 } i ^ 5 \right) \equiv 1 + 3 + 5 + \ldots + 2 \left( 50 \right) - 1 = 50 ^ 2 \] using this fact since \( 50 ~\%~ 4 = 2 \) then we know that \( 50 ^ 2 ~\%~ 4 = 0 \) so we deduce that \[ \left( \sum _ { i = 1 } ^ { 100 } i ^ 5 \right) ~\%~ 4 = 0 \]
Remainder of a Sum of Factorials
Determine \[ \left( \sum _ { i = 1 } ^ { 100 } i ! \right) ~\%~ 15 \]
Observe that for any \( i \ge 5 \) we see that \( 15 = 3 \cdot 5 \mid i! \) therefore we reduce it to \[ \left( \sum _ { i = 1 } ^ { 100 } i ! \right) \equiv \sum _ { i = 1 } ^ { 4 } i ! \left( ~\%~ 15 \right) \] But we know that \( 1! + 2! + 3! + 4! = 33 \equiv 3 \left( ~\%~ 15 \right) \) so that \[ \left( \sum _ { i = 1 } ^ { 100 } i! \right) \equiv 3 \left( ~\%~ 15 \right) \]
Modular Inverse iff GCD 1
Suppose that \( a, m \in \mathbb{ Z } \) and that \( a \) has a modular inverse mod \( m \), iff \( \gcd \left( a, m \right) = 1 \).

\( \implies \) We know that \( a \cdot x \equiv 1 \left( \operatorname{ mod } m \right) \) therefore by definition \( m \mid \left( 1 - a \cdot x \right) \) therefore \( 1 - a x = k \cdot m \) for some \( k \in \mathbb{ Z } \).

Therefore \( x a - k m = 1 \), so now suppose that \( g = \gcd \left( a, m \right) \), so by definition \( g \mid a \) and \( g \mid m \) so that \( g \mid x a - k m = 1 \) which implies that \( g = 1 \) as needed.


\( \impliedby \) We have some \( s, t \in \mathbb{ Z } \) such that \( 1 = \gcd \left( a, m \right) = as + mt \) so that \( 1 - as = mt \) which means that \( m \mid 1 - as \) so that by definition we have that \[ as \equiv 1 \left( \operatorname{ mod } m \right) \] which means that \( s \) is \( a \)'s inverse mod \( m \).

Not Relatively Prime iff No Modular Inverse
\( \gcd \left( a, m \right) \neq 1 \) iff \( a \) doesn't have an inverse mod \( m \)
This follows by the contra-positive of the above.
Complete System of Residues Modulo n
A collection of \( R = \left\{ r _ 1, \ldots, r _ n \right\} \subseteq \mathbb{ Z } \) is said to be a complete system of residues modulo \( n \) if they are pairwise incongruent modulo \( n \), meaning that for any \( x, y \in R \), if \( x \neq y \) then \( x \not \equiv y \left( \operatorname{ mod } n \right) \)
Equality is the Same as Congruent in a Complete System of Residues Modulo n
Suppose that \( R \subseteq \mathbb{ Z } \) is a complete system of residues modulo \( n \), then for any \( x, y \in R \) \[ x = y \iff x \equiv y \left( \operatorname{ mod } n \right) \]
\( \implies \) Suppose that \( x = y \) therefore we have that \( x \equiv y \left( \operatorname{ mod } n \right) \). \( \impliedby \) Suppose that \( x \equiv y \left( \operatorname{ mod } n \right) \) we want to show that \( x = y \), but if it was that \( x \neq y \) then by the definition of complete system of residues we would have \( x \not \equiv y \left( \operatorname{ mod } n \right) \) which would be a contradiction, therefore \( x = y \)
Complete and Incomplete Systems Modulo n
Prove that \( 0, 2 ^ 1, \ldots, 2 ^ 9 \) is a complete system of residues modulo \( 11 \) but \( 0, 3 ^ 1, \ldots, 3 ^ 9 \) is not.

Suppose for the sake of contradiction that the former was not a complete system, before doing anything else note that \( 0 \not \equiv 2 ^ z \left( \operatorname{ mod } 11 \right) \) for any \( z \in \left[ 1, \ldots 9 \right] \) since \( 11 \nmid 2 ^ z \) and therefore instead there would exist some \( x, y \in \left[ 0, \ldots 9 \right] \) such that \( x \neq y \) and that \( 2 ^ x \equiv 2 ^ y \left( \operatorname{ mod } 11 \right) \) therefore \( 11 \mid 2 ^ x - 2 ^ y \) and without loss of generality assume that \( x \gt y \) then \( 2 ^ x - 2 ^ y = 2 ^ y \left( 2 ^ { x - y } - 1 \right) \), since \( 11 \) is prime then \( 11 \mid 2 ^ y \) or \( 11 \mid 2 ^ { x - y } - 1 \), we know that \( 11 \mid 2 ^ y \) is impossible as noted before so we must have that \( 11 \mid 2 ^ { x - y } - 1 \).

We'll show that \( 11 \mid 2 ^ { x - y } - 1 \) also leads to a contradiction, because if we look at \( 2 \)'s power sequence modulo \( 11 \) we see that it is \( \left( 2, 4, 8, 5, -1, -2, -4, -8, -5, 1 \right) \) therefore since \( x - y \in \left[ 0, \ldots , 9 \right] \) and the smallest integer such that \( 2 ^ k \equiv 1 \) is \( k = 10 \) then \( 2 ^ { x - y } \not \equiv 1 \) and thus is in contradiction with the fact that \( 11 \mid 2 ^ { x - y } - 1 \iff 2 ^ { x - y } \equiv 1 \left( \operatorname{ mod } 11 \right) \). Therefore our assumption is false and so the former is a complete system of residues.


Following a similar thread we note that \( 3 ^ k \not \equiv 0 \left( \operatorname{ mod } 11 \right) \) which is impossible by the uniqueness of the prime factorization. We want to find some \( x, y \in \left[ 0, \ldots 9 \right] \) such that \( 3 ^ x \equiv 3 ^ y \left( \operatorname{ mod } 11 \right) \) again without loss of generality assume that \( x \gt y \) and therefore we have \( 11 \mid 3 ^ x - 3 ^ y = 3 ^ y \left( 3 ^ { x - y } - 1 \right) \) since \( 11 \) is prime then it divides one of the factors, but as just noted the factor it divides must be \( 3 ^ { x - y } - 1 \) by looking at \( 3 \)'s power sequence modulo \( 11 \) we get some insight \( 3 , 9, 5, 4, 1, 3, 9, 5, 4, 1, \ldots \) so if \( x - y = 5 \) then \( 11 \mid 3 ^ { x - y } - 1 \) so let \( y = 1 \) and \( x = 6 \) therefore \( 3 ^ 6 \equiv 3 ^ 1 \left( \operatorname{ mod } 11 \right) \) and we've proven that the latter is not a complete system of residues.

A Complete System of Residues Modulo n Hits all Possible Residues
Suppose that \( r _ 1, r _ 2, \ldots , r _ n \) is a complete system of residues modulo \( n \), then prove that for each \( r \in \left[ 0, \ldots , n - 1 \right] \) there exists some \( i \in \left[ 1, \ldots n \right] \) such that \[ r _ i \equiv r \left( \operatorname{ mod } n \right) \] Moreover this mapping \( f : R \to \left[ 0, \ldots , n - 1 \right] \) is a bijection.
Suppose that for the sake of contradiction that there exists some \( r \in \left[ 0, \ldots , n - 1 \right] \) such that no \( r _ i \) was congruent to, then: \[ X = \left\{ r _ i ~\%~ n: i \in \left[ 1, \ldots , n \right] \right\} \subset \left[ 0, \ldots , n - 1 \right] \] therefore we deduce that \( \left\lvert X \right\rvert \lt n \) therefore there must exist some \( i, j \in \left[ 1, \ldots , n \right] \) such that \( i \neq j \) and \( r _ i ~\%~ n = r _ j ~\%~ n \) but that's a contradiction since the \( r _ i \)'s are pairwise incongruent therefore it must be that \( X = \left[ 0, \ldots, n - 1 \right] \) therefore for any \( r \in \left[ 0, \ldots , n - 1 \right] \) there exists some \( r _ j \in X \) such that \( r _ j \equiv r \left( \operatorname{ mod } n \right) \)

As per the statement the above mapping is denoted by \( f: R \to \left[ 0, \ldots, n \right] \) what we've shown is that \( \operatorname{ im } \left( f \right) = \left[ 0, \ldots , n - 1 \right] \) and since \( \left\lvert \operatorname{ dom } \left( f \right) \right\rvert = \left\lvert \operatorname{ im } \left( f \right) \right\rvert = \left\lvert \operatorname{ ran } \left( f \right) \right\rvert \) then \( f \) is a bijection.

Note the mapping \( f \left( r _ i \right) \) is simply \( r _ i ~\%~ n \).

The Multiples of a Complete System of Residues Mod \( n \) is still a Complete System of Residues Mod \( n \)
Suppose that \( R = \left\{ r _ 1, r _ 2, \ldots r _ n \right\} \) is a complete system of residues modulo \( n \) and \( a \in \mathbb{ Z } \) such that \( \gcd \left( a, n \right) = 1 \) then \( A = \left\{ ar_1 , ar_2 , \ldots , ar_n \right\} \) is a complete system of residues modulo \( n \)
Let \( ar _ i, a r _ j \in A\) such that \( i \neq j \), since \( R \) is a complete system of residues, we know that \( r _ i \not \equiv r _ j \left( \operatorname{ mod } n \right) \), now suppose for the sake of contradiction that \( a r _ i \equiv a r _ j \left( \operatorname{ mod } n \right) \), then since \( \gcd \left( a, n \right) = 1 \) we have \( r _ i \equiv r _ j \left( \operatorname{ mod } \frac{n}{1} \right) \) which is a contradiction, therefore we must have \( a r _ i \not \equiv a r _ j \left( \operatorname{ mod } n \right) \) as needed.
Product of Non-Zero Residues Yields Factorial
Suppose that \( R = \left\{ r _ 1, r _ 2, \ldots r _ n \right\} \) is a complete system of residues modulo \( n \) such that \( r _ n ~\%~ n = 0 \), then \[ \prod _ { i = 1 } ^ { n - 1 } r _ i \equiv \left( n - 1 \right)! \left( \operatorname{ mod } n \right) \]
Recall that there is a unique \( r \in \left[ 0, \ldots , n - 1 \right] \) for each \( r _ i \) such that \( r _ i \equiv r \). In this case since we've removed \( r _ n \) then there is a unique \( r \in \left[ 1, \ldots, n - 1 \right] \), let this mapping be denoted as \( f : R \to \left[ 1, \ldots, n \right] \) since it is a bijection then we note that \[ \begin{align} \prod _ { i = 1 } ^ { n - 1 } r _ i &\equiv \prod _ { i = 1 } ^ { n - 1 } f \left( r _ i \right) \\ &\equiv \prod _ { i = 1 } ^ { n - 1 } i \\ &\equiv \left( n - 1 \right) ! \end{align} \] as needed.
There are 22 Possibilities for the Last Two Digits of a Square
As per title.
We compute \[ \begin{align} 0 ^ 2 = 0 &\equiv 0 \pmod{ 100 } \\ 1 ^ 2 = 1 &\equiv 1 \pmod{ 100 } \\ 2 ^ 2 = 4 &\equiv 4 \pmod{ 100 } \\ 3 ^ 2 = 9 &\equiv 9 \pmod{ 100 } \\ 4 ^ 2 = 16 &\equiv 16 \pmod{ 100 } \\ 5 ^ 2 = 25 &\equiv 25 \pmod{ 100 } \\ 6 ^ 2 = 36 &\equiv 36 \pmod{ 100 } \\ 7 ^ 2 = 49 &\equiv 49 \pmod{ 100 } \\ 8 ^ 2 = 64 &\equiv 64 \pmod{ 100 } \\ 9 ^ 2 = 81 &\equiv 81 \pmod{ 100 } \\ 10 ^ 2 = 100 &\equiv 0 \pmod{ 100 } \\ 11 ^ 2 = 121 &\equiv 21 \pmod{ 100 } \\ 12 ^ 2 = 144 &\equiv 44 \pmod{ 100 } \\ 13 ^ 2 = 169 &\equiv 69 \pmod{ 100 } \\ 14 ^ 2 = 196 &\equiv 96 \pmod{ 100 } \\ 15 ^ 2 = 225 &\equiv 25 \pmod{ 100 } \\ 16 ^ 2 = 256 &\equiv 56 \pmod{ 100 } \\ 17 ^ 2 = 289 &\equiv 89 \pmod{ 100 } \\ 18 ^ 2 = 324 &\equiv 24 \pmod{ 100 } \\ 19 ^ 2 = 361 &\equiv 61 \pmod{ 100 } \\ 20 ^ 2 = 400 &\equiv 0 \pmod{ 100 } \\ 21 ^ 2 = 441 &\equiv 41 \pmod{ 100 } \\ 22 ^ 2 = 484 &\equiv 84 \pmod{ 100 } \\ 23 ^ 2 = 529 &\equiv 29 \pmod{ 100 } \\ 24 ^ 2 = 576 &\equiv 76 \pmod{ 100 } \end{align} \] this shows that there are in total there are \( 25 \) elements in the list above, 0 is counted two times two many, and 25 is counted once too many therefore there are exactly \( 22 \) unique endings in the above, and lets denote the collection of unique last two digits as \( LD \) Notice that if we continued we would have \[ \begin{align} 25 ^ 2 = 625 &\equiv 25 \pmod{ 100 } \\ 26 ^ 2 = 676 &\equiv 76 \pmod{ 100 } \\ 27 ^ 2 = 729 &\equiv 29 \pmod{ 100 } \\ 28 ^ 2 = 784 &\equiv 84 \pmod{ 100 } \\ 29 ^ 2 = 841 &\equiv 41 \pmod{ 100 } \end{align} \] notice that after \( 25 \) the order in which the endings arrive is in a mirrored fashion. Notice that every time a multiple of 25 is reached some special is happening. Specifically we claim that for any \( n \in \mathbb{ N } _ 1 \) and \( k \in \left[ 1, \ldots , 24 \right] \) we have \[ \left( 25n + k \right) ^ 2 \equiv \left( 25n - k \right) ^ 2 \pmod{ 100 } \] this is clear because \( \left( 25 n + k \right) ^ 2 = 25 ^ 2 n ^ 2 + 50kn + k ^ 2 \) whereas \( \left( 25 n - k \right) ^ 2 = 25 ^ 2 n ^ 2 - 50kn + k ^ 2 \) therefore \[ \left( 25n + k \right) ^ 2 - \left( 25n - k \right) ^ 2 = 100kn \equiv 0 \pmod{ 100 } \] this fact allows us to show that given any \( k \ge 25 \) that \( k ^ 2 ~\%~ 100 \in LD \), we do it by induction based on where it lies with respect to consecutive multiples of \( 25 \).

We use the predicate : \[ P \left( k \right) : \forall n \in \left[ 25k ,\ldots, 25k + 24 \right], n ^ 2 ~\%~ 100 \in LD \] and show it holds true for all \( k \in \mathbb{ N } _ 1 \)

For the base case \( k = 0 \) then as verified in the huge table we know that for any \( n \in \left[ 0, \ldots 24 \right] \) that \( n ^ 2 ~\%~ 100 \in LD \). Now onto the induction step where we assume that \( P \left( k \right) \) holds true for some \( k \in \mathbb{ N } _ 1 \) and then we prove that \( P \left( k + 1 \right) \) hold true, so suppose that \( n \in \left[ 25 \left( k + 1 \right), \ldots , 25 \left( k + 1 \right) + 24 \right] \), in other words \( n = 25 \left( k + 1 \right) + j \) where \( j \in \left[ 0, \ldots , 24 \right] \) if it so happens that \( j = 0 \) then \( n = 25 \left( k + 1 \right) \) and so when you square it it ends in \( 25 \), on the other hand if \( j \in \left[ 1, \ldots , 24 \right] \) then we know that \[ (25 \left( k + 1 \right) + j) ^ 2 \equiv \left( 25 \left( k + 1 \right) - j \right) ^ 2 \] but \( 25 \left( k + 1 \right) - j = 25k + 25 - j \) and since \( j \ge 1 \) then by the induction hypothesis \( 25 \left( k + 1 \right) - j ~\%~ 100 \in LD \) so therefore so is \( 25 \left( k + 1 \right) + j \) as needed.