# 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.

• I removed my answer, I had to have a coffee instead :P – Paolo Leonetti Sep 12 '15 at 14:19

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$.

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}$.

• very nice - thank you - chinese remainder theorem is not covered until 10 pages after this problem in the text so this will provide additional motivation for it for me. The fundamental theorem of arithmetic has been covered and so I should have seen your argument about a being a sixth power from that. – topoquestion Sep 11 '15 at 20:44