# A problem on divisibility theorem

Verify that if an integer is simultaneously a square and a cube, then it must be either of the form ${7k}$ or ${7k +1}$.

I have no idea on how to proceed.

-
@PraphullaKoushik Please don't comment just to say that you upvoted something. You've done that both on the question and the accepted answer and it adds nothing beyond the upvote. If everybody commented to say they'd upvoted, the comment system would be unusable. – David Richerby Apr 29 '14 at 18:14
(an addendum to @DavidRicherby's comment): sometimes, people will write "+1: <reason here>" if there is an exceptional case, or something important about the question/answer that they want to draw out. This, done in extreme moderation, is considered acceptable, but only for special cases. – apnorton Apr 30 '14 at 3:16

If $n$ is simultaneously a cube,

$$n\equiv a^3\equiv -1,0,1\pmod{7}$$

and a square

$$n\equiv t^2\equiv 0,1,4,2\pmod{7}$$

Therefore $n$ is either $7k$ or $7k+1$

-
You forgot "square" after "simultaneously....". Note that it can be proved without brute-force checking all remainders/classes - see my answer. – Bill Dubuque Apr 29 '14 at 14:58

Suppose that $\,\color{#c00}{a^{k}} =n = \color{#0a0}{b^{k+1}}$ and $\ k(k\!+\!1)+1 = p\,$ is prime.  By $\ \color{#c0d}{\mu F} =$ little Fermat

mod $\,p\!:\ \,n\not\equiv 0\,\Rightarrow a,b\not\equiv 0\,\Rightarrow\ n\equiv\dfrac{n^{\large k+1}}{n^{\large k}\ \ \ \ }\equiv \dfrac{(\color{#c00}{a^{\large k}})^{\large k+1}}{(\color{#0a0}{b^{\large k+1}})^{\large k}}\equiv\dfrac{a^{\large p-1}}{b^{\large p-1}}\,\overset{\color{#c0f}{\mu F}}\equiv\, \dfrac{1}{1}\equiv 1\$

Hence $\ n\equiv 0\$ or $\,1\pmod p,\$ i.e. $\ n = pj\,$ or $\,1\!+\!pj\,$ for some $\,j\in \Bbb Z.\ \$ QED

Yours is the special case $\ k = 2,\,$ so $\, p = 7.$

-

If an integer $a$ is simultaneously a square and a cube, it must be the sixth power of an integer $b$

Now as $7$ is prime either $7|b$ or $(7,b)=1$

If $7|b, 7|b^n$ for integer $n\ge1$

Else by Fermat's Little Theorem , $7|(b^{7-1}-1)$

-
$n=m^2=l^3$ implies $l$ divides $m$ so $m=al$ and so $m^2=a^2l^2=l^3$ implies $a^2=l$ and so $l^3=a^6$ thus $m$ is a sixth power of an integer? Is this correct justification? – cello Mar 15 at 15:20
@cello, You are right – lab bhattacharjee Mar 15 at 15:23
It was just a guess that $l$ divides $m$.. Could not see why.. I think it is not that difficult.. I will try one more time.. Thanks.. – cello Mar 15 at 15:24

Check the integers mod $7$. Which are squares and which are cubes:

$$0^2=0^3=0$$ $$1^2=1^3=1$$ $$2^2 = 4,\qquad 2^3=8\equiv 1$$

$$3^2 = 9 \equiv 2,\quad3^3=27\equiv 6$$ $$4^2 = 16 \equiv 2,\quad 4^3= 64 \equiv 1$$ $$5^2 = 25 \equiv 4,\quad 5^3= 125 \equiv 6$$ $$6^2 = 36 \equiv 1,\quad 6^3=216\equiv 6.$$

So only $0, 1, 2$ and $4$ are squares, only $0, 1$ and $6$ are cubes (mod $7$). The ones that are both give the wanted answer.

-
I do not find this to be a convincing reason why squares and cubes mod 7 all follow this pattern. – VF1 Apr 30 '14 at 4:08
If $a\equiv b$, then $a^n\equiv b^n$, you only need to check one representatives of the residue classes ($0,1,...,6$). – ploosu2 Apr 30 '14 at 9:26