Proof Check for Fermat's Little Theorem Admittedly, my proof is very ugly. You can skip Lemma 2 and 3 really. I just put them there for my own benefit. It's really a combination of Lemma 1 and the theorem itself. Anyway it's a bit long and clunky but I'd appreciate any feedback. I wanted to be sure that nothing was invalid as I haven't seen this proof before. Here is the link:
Fermat's Little Theorem
 A: Your proof of lemma 2 is pretty ugly to my eyes. The definition I like for $a \equiv  b \bmod n$ is that $n$ divides $b - a$. So to prove that $an + b \equiv b \bmod n$, you look at $b - (an + b) = -an$, which is evidently divisible by $n$, and you're done. I think you can similarly simplify Lemma 3. 
POST-COMMENT additions:
I went and looked at the proof itself. The gist is this: 


*

*Every number $a$ is congruent, mod $p$, to a number $r$ between $0$ and $p-1$.

*Such numbers all satisfy $r^p \equiv r \bmod p$. 

*By transitivity of congruence, $a^p \equiv a \bmod p$. 


The meat of the proof is in step 2, of course. 
If you shuffle things around to use my version of congruence, the proof of part 2 gets a good deal shorter and simpler, I believe. It looks like this: 
We claim that $r^p \equiv r \bmod p$ for $0 \le r \le p-1$. The proof is by induction. The cases $r = 0, 1$ are trivial. Now suppose we have some $r$ with $0 \le r \le p-1$, and that the claim is true for all $m$ with $0 \le m < r$. Taking $m = r-1$, we have
\begin{align}
r^p - r &= (m + 1)^p - (m+1) \\
&= \left( \sum_{i=0}^p \binom{p}{i} m^{p-i} 1^i \right)  - (m + 1)\\
&= \left( \sum_{i=1}^{p-1} \binom{p}{i} m^{p-i}  \right) +m^p + 1^p - m - 1\\
&= \left( \sum_{i=1}^{p-1} \binom{p}{i} m^{p-i}  \right) +m^p - m
\end{align}
Each combinatorial coefficient in the sum is a multiple $k_i p$ for some integer $k_i$, by the lemma, so we have
\begin{align}
r^p - r 
&= \left( \sum_{i=1}^{p-1} p k_i m^{p-i} \right) +m^p - m \\
&= p\left( \sum_{i=1}^{p-1} k_i m^{p-i} \right) +m^p - m \\
&\equiv m^p - m  \bmod p\\
&\equiv (r-1)^p - r  \bmod p\text{, by the choice of $m$} \\
&\equiv 0  \bmod p\text{, by the inductive hypothesis.} \\
\end{align}
