I'm supposed to prove that $\displaystyle a^{37} \equiv a(mod\ 1729)$ for any integer $\displaystyle a$ using Euler's theorem. I'm trying to first prove it under the assumption that $\displaystyle gcd(a, 1729)=1$, which allows me to apply Euler's theorem. In this case, I showed that $\displaystyle a^{\phi(1729)}=a^{1296}=(a^{36})^{36} \equiv 1(mod\ 1796)$. What I want to do is get from here to $\displaystyle a^{36} \equiv 1(mod\ 1796)$ so I can multiply both sides by $\displaystyle a$ and get the result. However, I'm not sure how to fill in that gap. Is there some theorem I can use? Or am I going about this in the wrong way?

Also, I'm not sure how to handle the case where a and 1729 are not relatively prime. Any help there would be appreciated as well.