<s>[INST] Prove $13|19^n-6^n$ by congruences I am trying to prove  $13|19^n-6^n$. With induction its not so bad but by congruences its quite difficult to know how to get started.
Any hints?
 [/INST] Modular Arithmetic is an extremely useful way of thinking about numbers. It can be used to calculate the last three digits of $2011^{2011}$ by hand. The day of the week, the time of the day, and the flipping of a light switch are all based upon modular arithmetic. The day of the week is in $\mod 7$ (cycles in a period of $7$), the time of the day is in $\mod 24$, and a light switch is either on or off; $\mod 2$. 
Two integers are congruent modulo $n$ if their difference is a multiple of $n$. We write this as $$a \equiv b \pmod{n}$$
For example, $36 \equiv 71 \pmod{7}$, because $71 - 36 = 35$, and $\dfrac{35}{7} = 5$. 
We can alternatively write this as $a-b = qn$, for an integer $q$, or $a = b + qn$ (by adding $b$ to both sides). Notice that for any integers $x$ and $y$, if $x \equiv y \pmod{n}$, $x$ and $y$ leave the same remainder when divided by $n$. This is sometimes used as another definition for modular arithmetic. Since modular arithmetic is only defined for integers, let all variables be integers unless otherwise specified.
$\textbf{Addition}$
$\textbf{Theorem 1:}$ If $a \equiv b \pmod{n}$, then $a+c \equiv b+c \pmod{n}$. 
If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $(a+c) - (b+c) = a-b = qn$, so $a+c \equiv b+c \pmod{n}$. $\blacksquare$
If we know that $123$ leaves a remainder of $2$ when divided by $11$, and want the remainder when $127$ is divided by $11$, we can simply use Theorem 1: $123 \equiv 2 \pmod{11} \implies 123 + 4 \equiv 2 + 4 \pmod{11}$, so $127 \equiv 6 \pmod{11}$. A similar proof can be used to prove a stronger theorem:
$\textbf{Theorem 2:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $a+c \equiv b+d \pmod{n}$.
We know that $a-b = qn$ for some integer $q$ and $c-d = rn$ for some integer $r$. Adding the equations gives $(a+c) - (b+d) = qn + rn = (q+r)n$. This means that the difference of $a+c$ and $b+d$ is a multiple of $n$, so $a+c \equiv b+d \pmod{n}$. $\blacksquare$
Theorem 2 can be generalized even further:
$\textbf{Theorem 3:}$ If $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, $\cdots , \ a_k \equiv b_k \pmod{n}$ then $a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$.
By the definition of modulos, we get $a_1 - b_1 = q_1 n$, $a_2 - b_2 = q_2 n$, $\cdots , \ a_k - b_k = q_k n$. Adding these, we get $(a_1 + a_2 + \cdots + a_k) - (b_1 + b_2 + \cdots + b_k) = (q_1 + q_2 + \cdots + q_k)n$, so $a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$. $\blacksquare$
Similar theorems hold for muliplication as well, but the proofs are different.
$\textbf{Theorem 4:}$ If $a \equiv b \pmod{n}$, then $ac \equiv bc \pmod{n}$. 
If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $ac-bc = qcn$, so $ac \equiv bc \pmod{n}$. $\blacksquare$
There is also another proof of this:
We know that $$\underbrace{a \equiv b \pmod{n}, \ a \equiv b \pmod{n}, \cdots , \ a \equiv b \pmod{n}}_{\text{c statements}}$$
From Theorem 3, we get $$\underbrace{a+a+a+a+\cdots + a}_{\text{c "a"s}} \equiv \underbrace{b+b+b+b+\cdots + b}_{\text{c "b"s}}$$
or $ac \equiv bc \pmod{n}$. $\blacksquare$
$ \textbf{Theorem 5:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $ac \equiv bd \pmod{n}$.
We repeatedly use Theorem 4: Since $a \equiv b$, $ac \equiv bc$, and since $c \equiv d$, $bc \equiv bd$. Therefore, $ac \equiv bc \equiv bd$, or $ac \equiv bd \pmod{n}$. $\blacksquare$
$\textbf{Theorem 6:}$ If $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, $\cdots , \ a_k \equiv b_k \pmod{n}$ then $a_1 a_2 \cdots  a_k \equiv b_1  b_2  \cdots  b_k \pmod{n}$.
We repeatedly use Theorem 5: Because $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, we get $a_1a_2 \equiv b_1b_2 \pmod{n}$. We also know $a_3 \equiv b_3 \pmod{n}$, so $a_1a_2a_3 \equiv b_1b_2b_3 \pmod{n}$. Also, $a_4 \equiv b_4 \pmod{n}$, so $a_1a_2a_3a_4 \equiv b_1b_2b_3b_4 \pmod{n}$. Continuing to do this will give $a_1 a_2 \cdots  a_k \equiv b_1  b_2  \cdots  b_k \pmod{n}$. $\blacksquare$
Note that a corollary of Theorem 6, when $a_1 = a_2 = \cdots = a_k$ and $a_1 = a_2 = \cdots = a_k$, is that
$\textbf{Theorem 7:} $ If $a \equiv b \pmod{n}$, then $a^k \equiv b^k \pmod{n}$.
$\textbf{Main Proof:}$
Using this corollary, we have $19^k \equiv 6^k \pmod{13}$, because $19 \equiv 6 \pmod{13}$. By definition, this means that $$13 | (19^k - 6^k)$$ as desired. $\blacksquare$
</s>