Proving that Carmichael function divides Euler's totient function with division I was looking at a proof for $\lambda(n) | \phi(n)$ using division.
Assume $\lambda(n)  \not| \phi(n).$   Then $\phi(n) = \lambda(n) * q + r$ and $ 1 \leq r \leq \lambda(n) -1.$
$1 = a^{\phi(n)} = a^{\lambda(n)*q+r} = (a^{\lambda(n)})^q * a^r = a^r\ (mod\ n),$
but then $a^r$ is less than $a^{\lambda(n)}$ which is a contradiction.
For starters, why is this true? $1 = a^{\phi(n)} (mod\ n).$  Is this by Euler's generalisation of Fermat's little theorem? the gcd(a,n) was never specified, so i didn't want to assume.
Second confusing part is $(a^{\lambda(n)})^q.$ I assume this disappears because $a^{\lambda(n)}\ (mod\ n) = 1.$  But why does this equal 1 then?
I guess it's a contradiction since $\lambda(n)$ should be the smallest number n such that $a^m \equiv 1\ (mod\ n).$
 A: To answer your specific questions, firstly, 
$a^{\phi(n)}\equiv1 \pmod n$ is indeed Euler's generalization of Fermat's little theorem. 
The Carmichael function $\lambda(n)$ is defined as the least positive integer $m$ 
such that $a^m\equiv1\pmod n$ for all $a$ relatively prime to $n$, so that is why we assume gcd$(a,n)=1.$ 
Your second question was why $(a^{\lambda(n)})^q\times a^r\equiv a^r \pmod n.$ 
That is indeed because $a^{\lambda(n)}\ \equiv 1\pmod n,$ 
which follows from the definition of the Carmichael function $\lambda(n)$.
Thus $(a^{\lambda(n)})^q\times a^r\equiv 1^qa^r \equiv1a^r\equiv a^r\pmod n.$ 
Finally, yes, a contradiction occurs because we assumed that $a$ was any integer relatively prime to $n,$ 
and $\lambda$ is the least positive integer $m$ such that $a^m\equiv1 \pmod n$ for all such $a$, 
and yet we just showed that $a^r\equiv1\pmod n$ for all such $a,$ and $r$ is positive and less than $\lambda$.
A: Let $\,E=E_n\,$ be the set of all exponents $\,e>0\,$ such that: $\ a^{\large e}\equiv 1\pmod{\!n}\,$ for all $a$ coprime to $n.\,$ By definition $\, \lambda(n)\,$ is the least element of $E.\,$ Note $E$ is closed under positive subtraction, $ $ i.e.
$$\color{#0A0}j>\color{#C00}k\,\in\,E\ \Rightarrow\ j\!-\!k\,\in E,\ \ \ {\rm by}\ \ \  1\equiv \color{#0A0}{a^{\large j}} \equiv a^{\large j-k}\, \color{#C00}{a^{\large k}} \equiv a^{\large j-k}\qquad \qquad $$
Theorem below $\,\Rightarrow\,\lambda(n)\,$ divides all elements in $E,\,$ including $\,\phi(n)\in E\,$ (by Euler's Theorem).  
Remark $ $ $\lambda(n)$ and its above property are universal generalizations of the notion of order of an element in a group. Generally it is called the (universal) exponent of a group. It could also be called the universal order.  The proof in the OP is essentially Proof $2$ below - specialized to the case at hand.

Theorem $\ \ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\  n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$
Proof $\ {\bf 1}\  $ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra  $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \, $ 
Proof ${\bf\ 2}\,\rm\ \ \cal O\,$ closed under subtraction $\rm\,\Rightarrow\,\cal O\,$ closed under remainder (mod), when it is nonzero, since mod is computable by repeated subtraction $\rm\, a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\,$ Thus $\rm\,n\in \cal O\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is $\rm\,\in \cal O\,$ and smaller than $\rm\,\ell,\,$ contra mimimality of $\rm\,\ell.$ 
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$  \rm\begin{eqnarray} {\cal O}\rm\ closed\ under\ {\bf subtraction} &\Rightarrow\:&\rm {\cal O}\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\
&\Rightarrow\:&\rm {\cal O}\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$
Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. 
For more on the key innate structure  see this post on order ideals and denominator ideals.
