Prove that any integer that is both square and cube is congruent modulo 36 to 0,1,9,28 This is from Burton Revised Edition, 4.2.10(e) - I found a copy of this old edition for 50 cents. 
Prove that if an integer $a$ is both a square and a cube then $a  \equiv 0,1,9, \textrm{ or } 28  (\textrm{ mod}\ 36)$ 
An outline of the proof I have is
Any such integer $a$ has $a = x^2$ and $a = y^3$ for some integers $x,y$
Then by the Division Algorithm, $x = 36s + b$ for some integers $s,b$ with $0 \le b \lt 36$ and $y = 36t + c$ for some integers $t,c$ with $0 \le c \lt 36$
Using binomial theorem, it is easy to show that $x^2 \equiv b^2$ and $y^3 \equiv c^3$
Then $a \equiv b^2$ and $a \equiv c^3$
By computer computation (simple script), the intersection of the possible residuals for any value of $b$ and $c$ in the specified interval is 0,1,9,28 
These residuals are possible but not actual without inspection which shows $0^2 = 0^3 \equiv 0$ , $1^2 = 1^3 \equiv 1$ , $27^2 = 9^3 \equiv 9$, and $8^2 = 4^3 \equiv 28$ $\Box$
There is surely a more elegant method, can anyone hint me in the right direction.
 A: What you did is correct, but yes, a lot of the work (especially the computer check) could have been avoided.
Firstly, if $a$ is both a square and a cube, then it is a sixth power.
This is because, for any prime $p$, $p$ divides $a$ an even number of times (since it is a square), and a multiple of 3 number of times (since it is a cube), so $p$ divides $a$ a multiple of 6 number of times altogether, and since this is true for any prime $p$, $a$ is a perfect sixth power.
So write $a = z^6$.
Next, rather than working mod $36$, it will be nice to work mod $9$ and mod $4$ instead; this is equivalent by the chinese remainder theorem.
So:


*

*Modulo $9$, $z^6 \equiv 0 \text{ or } 1$. You can see this just by checking every integer or by applying the fact that $\varphi(9) = 6$.

*Modulo $4$, $z^6 \equiv 0 \text{ or } 1$. This is easy to see; $0^6 = 0$, $1^6 = 1$, $(-1)^6 = 1$, and $2^6 \equiv 0$.
So $a = z^6$ is equivalent to $0$ or $1$ mod $4$ and mod $9$.
By the chinese remainder theorem, this gives four possibilities:


*

*$a \equiv 0 \pmod{4}, a \equiv 0 \pmod{9} \implies a \equiv 0 \pmod{36}$

*$a \equiv 0 \pmod{4}, a \equiv 1 \pmod{9} \implies a \equiv 28 \pmod{36}$

*$a \equiv 1 \pmod{4}, a \equiv 0 \pmod{9} \implies a \equiv 9 \pmod{36}$

*$a \equiv 1 \pmod{4}, a \equiv 1 \pmod{9} \implies a \equiv 1 \pmod{36}$.
A: First establish that $a$ must be a sixth power. We have $a=b^2=c^3$ so that $a^3=b^6$ and $a^2=c^6$ whence $$a=\cfrac {a^3}{a^2}=\cfrac {b^6}{c^6}=\left(\cfrac bc\right)^6$$
And if $q$ is a rational number whose sixth power is an integer, it must be an integer itself. [see below]
Now, let's have a look at the sixth powers modulo $36$. Every integer is congruent to a number of the form $6a+b$ where $-2\le a,b \le 3$. Then a simple application of the binomial theorem gives that:
$$(6a+b)^6\equiv b^6 \bmod 36$$
Finally, checking all the possibilities for $b$ we see $$(-2)^6=2^6=64\equiv 28; (-1)^6=1^6=1; 0^6=0; 3^6=81^2\equiv 9^2=81\equiv 9$$

Suppose $a,m,n \in \mathbb N$ with $a=\left(\frac mn\right)^6$ with $\frac mn$ in lowest terms and suppose $p$ is a prime factor of $n$ so that $n=pd$ with $d\in \mathbb N$. Then we have $an^6=m^6=ap^6d^6$ whence $p|m^6$ and because $p$ is prime $p|m$. But this is a contradiction since $m$ and $n$ were constructed to have no common factor. Hence $n$ has no prime factors and $n=1$.
