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).$
Best Answer
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$.