Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is homework from my number theory course.

Since $(x+1)^3-x^3=3x^2+3x+1$ and $x^3-(x+1)^3=-3x^2-3x-1$, to say that the difference of two cubes is divisible by 5 is the same as saying that $3x^2+3x+1\equiv 0\mod 5$ or $-3x^2-3x-1\equiv 0\mod 5$. Both of these statements imply that $x(x+1)\equiv 3\mod 5$. Thus I can finish this by showing that there are no such integers which satisfy $x(x+1)\equiv 3\mod 5$.

I want to say that it is sufficient to check by hand for the values 0,1,2,3, and 4 (for which it is not true), but other than following this by a messy induction I was wondering if there is an easier way to show that there are no integers such that $x(x+1)\equiv 3\mod 5$?

share|improve this question
    
The induction is not as messy as it might look; it's just one application of the binomial theorem (look at difference of $f(x+5)-f(x)$ with $f(x)=x(x+1)$), –  Peter Košinár Feb 24 at 2:15

8 Answers 8

up vote 8 down vote accepted

$$x^2+x\equiv 3\pmod 5\\ \implies x^2+x+4^{-1}\equiv 3+4^{-1}\pmod 5\\ \implies (x+2^{-1})^2=(x+3)^2\equiv 2\pmod 5$$

The quadratic residues modulo $5$ are $0,1,4$ and this list does not include $2$. QED

share|improve this answer

Note that by Little Fermat, $$ (x^3)^3\equiv x^{2\phi(5)+1}\equiv x\pmod{5} $$ Thus, if $x^3\equiv y^3\pmod{5}$, by cubing both sides, we must have $x\equiv y\pmod{5}$. Therefore, $$ 5\mid x^3-y^3\implies5\mid x-y $$

share|improve this answer

$x^3 - y^3 = (x - y)(x^2 + x y + y^2)$. Now $x^2 + x y + y^2 \equiv (x + 3 y)^2 - 3 y^2 \mod 5$, and since $3$ is not a quadratic residue mod $5$ we find that there are no solutions to $x^2 + x y + y^2 \equiv 0 \mod 5$ other than the trivial $(0,0)$. Thus
$x^3 \equiv y^3 \mod 5$ only when $x \equiv y \mod 5$.

share|improve this answer

Since you are considering things like $(x+1)^3-x^3$, I assume the problem should be to show that the difference of two consecutive cubes is never divisible by $5$.

You could finish the problem in this way: $$\eqalign{ x(x+1)\equiv3\pmod5\quad &\Rightarrow\quad 4x(x+1)+1\equiv 3\pmod5\cr &\Rightarrow\quad (2x+1)^2\equiv 3\pmod5\cr}$$ which implies that $3$ is a square (the technical term is "quadratic residue") modulo $5$. But it isn't, so this is impossible.

How do you know that $3$ is not a square modulo $5$?

Method $1$: calculate $0^2,1^2,\ldots,4^2$ modulo $5$ and observe that you never get $3$. This is no easier than what you suggested!

Method $2$: use the Legendre symbol and quadratic reciprocity. This is probably more work than what you suggested, though if you had a larger modulus instead of $5$ it would probably be better.

share|improve this answer

Hint $\ \ x\mapsto x^3\,$ is onto by $\,\{0,1,2,3,4\}^3\!\equiv\{0,1,3,2,4\},\,$ therefore $\,1$-$1$.

Hence $\,x ^3\equiv y^3\,\Rightarrow\, x\equiv y\,\Rightarrow\, 5\mid x-y.\,$ In particular, $\ x-y\ne \pm1.$

share|improve this answer
1  
Is surjectivity really easier to see directly than injectivity? –  Marc van Leeuwen Feb 24 at 14:05

x = 5n + k, then x^2 + x - 3 = (5n + k)^2 + 5n + k - 3 = k^2 + k - 3(mod5) now check k = 0, 1, 2, 3, and 4 you don't get 0(mod5).

share|improve this answer

If you've already checked 0,1,2,3,4 by hand, you don't have to do any induction, because $x(x+1) \equiv y(y+1)$ for some $y \in [0..4]$. Likewise, couldn't you do exactly the same thing on the original question? Cubes mod 5 are just as easy to compute as squares mod 5.

share|improve this answer

$5$ is a really small number: checking all the values mod $5$ is the easy way.

You could have even avoided doing all of the work you had done, by just listing all possible cubes mod $5$, and seeing that no consecutive cubes are equal.

  • $0^3 = 0$
  • $1^3 = 1$
  • $2^3 = 8 = 3$
  • $3^3 = 9 \cdot 3 = 4 \cdot 3 = 2$
    • or $3^3 = (-2)^3 = -2^3 = -3 = 2$
  • $4^3 = \cdots = 4$
  • $0^3 = 0$

Notice that every number was a cube; if we had already known that, it would have been obvious no two consecutive cubes could be equal mod $5$. We could prove a theorem:

(Assuming $m > 1$) if every number modulo $m$ is an $n$-th power, then no integer $n$-th powers can be divisible by $m$

One simple sufficient condition for this is if $\gcd(\varphi(m), n) = 1$. This would let us quickly prove similar facts for very large moduli and exponents!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.