What is $\,a\bmod 63\,$ if $\,a\,$ is both a square and a cube? Let there be integers $a,m,n$ such that $a=m^2=n^3$. Show that $a\equiv 0,1,28,36\pmod{63}$.
I have established that $a$ must be a sixth power of an integer:
$$a=\frac{a^3}{a^2} = \frac{m^6}{n^6} =\left (\frac{m}{n}\right )^6$$
$n^6\mid m^6$ implies $n\mid m$ so $\frac{m}{n}=:b\in\mathbb{Z}$.
My objective is to show that $b\equiv 0,1,28,36\pmod{63}$. Then for every $f\in\mathbb{Z}[X]$:
$$b\equiv r\pmod{n}\Longrightarrow f(b)\equiv f(r)\pmod{n} $$
(just pick $f(x)=x^6$). Trouble is, I have no idea how to show $b$'s congruences. How to proceed?  
Alternatively, I could also state that $a = 63t+r, 0\leq r<63$, but I don't know how to tie in the fact that $a$ is a perfect cube/square at the same time. Advice?
 A: You must show $x^6\equiv 0,1,28,36\pmod{63}$ For $ 0 \leq x \leq 62$. By Fermat's little Theorem we conclude $x^6 \equiv 1 \pmod{7}$ if $x\neq 7k$ and it's easy to check $x^6 \equiv 1 \pmod{9}$ if $x\neq 3k$.
Now because of theorem :
 $a\equiv b \pmod {m_1}$ and $a\equiv b \pmod {m_2}$ then $a\equiv b \pmod {lcm (m_1,m_2)}$
It remains to show for $x=3 , 7$:
$3^6 \equiv 36\pmod{63}$ and $7^6 \equiv 28\pmod{63}$.  
For example :
$12^6 \equiv 9k \pmod{63}$ we have : $4^6 . 3^4 \equiv k \pmod{7} $  (Because of theorem says : $ak=bk \pmod m $ then $a=b \pmod {\frac{m}{\gcd(k,m)}}$ ) and because $ 4^6 \equiv 1 \pmod 7 , 81 \equiv 4 \pmod 7$ then $k=4$ and $12^6 \equiv 3^6 \equiv 36 \pmod {63}$.  
A: Alright, have been Trying to follow the hints and here's what I've come up with.
$Z_{63}\cong Z_9\times Z_7$ and looking at the remainders of 6th powers:
In $Z_7$ it's simple due to Fermat's theorem:
$0^6\equiv 0, 1^6\equiv 2^6\equiv\ldots \equiv 6^6\equiv 1\pmod{7}$.
In $Z_9$:
$0^6\equiv 3^6\equiv 6^6\equiv 0\pmod{9}$ and $1^6\equiv 2^6\equiv 4^6\equiv 5^6\equiv 7^6\equiv 8^6\equiv 1\pmod{9}$
Eureka!
The Chinese Remainder theorem gives us a way:
There are four cases to be considered: $(0,0),(0,1),(1,0),(1,1)$ which yield the remainders $0,28,36,1$ in $Z_{63}$
