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?

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$
