For any integer $a$, $a^{37} \equiv a \left( \text{mod } 1729\right)$ 
For any integer $a$, $a^{37} \equiv a \left( \text{mod } 1729\right).$

We're asked to use Euler's Theorem to prove this.
What I've tried:
$\phi(1729)=\phi(7)\phi(13)\phi(19)=1296$.
If $(a,n)=1$ then $a^{1296} \equiv 1 \left( \text{mod } 1729\right)$. I note that $1296=36^2$ and that something equivalent to what I need to prove is
$$a(a^{36}-1)\equiv 0 \left( \text{mod } 1729\right).$$
I am now wondering what are the conditions for $a^n \equiv b^n \left( \text{mod } m\right)$ implying $a \equiv b \left( \text{mod } m\right)$ so then I can say $(a^{36})^{36} \equiv 1 (\text{mod } 1729)$ implies $a^{36} \equiv 1 (\text{mod }1729)$ at which point the equivalent statement would be true.
 A: I think it's better to think about this problem using the Chinese remainder theorem. That is, since we have the ring isomorphism $\mathbb{Z}/1729 \cong \mathbb{Z}/7 \times \mathbb{Z}/13 \times\mathbb{Z}/19$, via the map $m \mapsto (m \ \mathrm{mod} \ 7, \ m \ \mathrm{mod} \ 13, \ m \ \mathrm{mod} \ 19)$, it is enough to verify that $a^{37}=a \ \mathrm{mod} \ x$ where $x$ is any one of $7,13$ and $19$. But this follows from Fermat's little theorem.
A: It is not much more work (and more insightful) to prove the general case, a variant of which characterizes Carmichael numbers (composites that behave like primes do in little Fermat).
Theorem $ $ (Korselt's Pseudoprime Criterion) $\ $ For  $\rm\:1 < e,n\in \Bbb N\:$ we have
$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\  n\ \ is\ \  squarefree,\ \  and \ \ p\!-\!1\mid e\!-\!1\ \, for\  all \ primes\ \ p\mid n$$
Proof $\ \ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its 
prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ i.e. that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$ which, since $\rm\:p\!-\!1\mid e\!-1,\:$ follows from $\rm\:a \not\equiv 0\:\Rightarrow\: a^{p-1} \equiv 1\ \ ( mod\ p),\:$ by little Fermat.
$(\Rightarrow)\ \ $ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show 
$$\rm (1)\ \  n\,\ is\ squarefree,\quad  and\quad  (2)\ \  p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$ 
$(1)\ \ $ If $\rm\,n\,$ isn't squarefree then
$\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\:  a^2\mid a\:\Rightarrow\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$
$(2)\ \ $ Let $\rm\ a\ $ be a generator of the multiplicative group of $\rm\:\Bbb Z/p.\:$
Thus $\rm\ a\ $ has order $\rm\:p\!-\!1.\:$ Now  $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$  but $\rm\:p\nmid a,\:$ so $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ 
the order of $\rm\,\ a\,\ (mod\ p).\quad$  QED 
A: Fermat's Little Theorem is weak. No wonder it's called "little". Euler's Theorem is also pathetic. What you gotta use is Carmichael's Theorem. It states that if $(a,n)=1$, then $a^{\lambda(n)} \equiv 1 \mod n$. To calculate $\lambda(n)$, let the prime factorization of $n$ be $\prod p_i^{a_i}.$ Then we have
$$\lambda(n)=lcm[\lambda(p_1^{a_1}),\lambda(p_2^{a_2})...\lambda(p_k^{a_k})]$$
It may help to know that for $p>2$, $k \ge 0$, we have  $\lambda(p^k)=\phi(p^k)$.
Furthermore, $\lambda(2^n)=a\phi(2^n)$ where $a=1$ if $n \le 2$ and $a=0.5$ otherwise.
We compute $\lambda(1729)= lcm[\lambda(7),\lambda(13),\lambda(19)]=lcm(6,12,18)=36$ and the result follows.
As an added bonus, you cannot get any better than this. $\lambda(n)$ is the lowest number such that $\forall (a,n)=1, \ a^{\lambda(n)} \equiv 1 \mod n$
