$n$ is both a square and a cube, I need to prove $n=7k$ or $n=7k+1$, for some integer $k$.
I need some guide lines.
Asked
Active
Viewed 2,098 times
3
-
3What remainders can a square have upon division by $7$, and what remainders a cube? – Daniel Fischer Sep 18 '13 at 15:52
-
1I don't think induction will help you here. Check all of the possible values of $x^2$ and $x^3$ modulo 7, as Daniel suggests. – user7530 Sep 18 '13 at 15:56
-
2This is to prove $n^6 = 7k$ or $n^6 = 7k + 1$. Look up Fermat's little theorem. – peterwhy Sep 18 '13 at 15:58
3 Answers
7
A number is a square and a cube iff it is a sixth power. According to Fermat's litte theorem, $z^6\equiv 1\pmod 7$ if $z\not\equiv 0\pmod 7$.
Hagen von Eitzen
- 374,180
6
If $n$ is both a square and a cube, it is a perfect $6$-th power.
Let $z$ be a number. Then $z$ has shape $7k$, or $7k+1$, or $7k+2$, and so on up to $7k+6$.
Then $z^6$ has shape (respectively) $7k$, $7k+1$, $7k+1$, $7k+1$, $7k+1$, $7k+1$, and $7k+1$.
To do the calculations, let us take the example $z$ of the shape $7k+2$.
Imagine expanding $(7k+2)^6$ using the Binomial Theorem. The first $6$ terms are obviously divisible by $7$, and the last term is $2^6=64$. This has remainder $1$ on division by $7$. So $(7k+2)^6$ has remainder $1$ on division by $7$, and therefore has shape $7t+1$.
The other calculations are very similar.
Remark: We do not need to work with $6$-th powers. The squares of numbers of shape $7k+a$, where $a$ goes from $0$ to $6$, are, in order, of shape $$7k \qquad 7k+1 \qquad 7k+4 \qquad 7k+2\qquad 7k+2 \qquad 7k+4\qquad 7k+1.$$ The cubes, are, in order, of the shape $$7k \qquad 7k+1 \qquad 7k+1 \qquad 7k+6\qquad 7k+1 \qquad 7k+6\qquad 7k+6.$$ Only $7k$ and $7k+1$ occur in both lists.
André Nicolas
- 507,029
1
Observe that:
Any square modulo 7 will be one of the following: $$0, 1, 4, 2$$ Any cube modulo 7 will be one of the following: $$0, 1, 6$$
Nathaniel Bubis
- 33,018