6
$\begingroup$

This is a very interesting word problem that I came across in an old textbook of mine:

Show that, for any two integers $a$ and $b$, at least one of the expressions $a^3, b^3, a^3+b^3$ or $a^3-b^3$ will be divisible by $7$.

So I know it's got something to do with Euler's totient function and the Euler-Fermat theorem, which yields the shortest, simplest proofs, but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance.

$\endgroup$
16
$\begingroup$

If $a$ or $b$ is a multiple of 7 then it's obvious, else $a^6\equiv b^6 \equiv 1 \pmod 7$ and $(a^3+b^3)(a^3-b^3)=a^6-b^6\equiv 0 \pmod 7$. Since 7 is prime it divides $a^3+b^3$ or $a^3-b^3$.

$\endgroup$
  • $\begingroup$ this is better solution! $\endgroup$ – MAN-MADE Aug 26 '17 at 7:11
  • $\begingroup$ This is truly elegant. Nice job. $\endgroup$ – AlwaysLearning Aug 26 '17 at 20:36
4
$\begingroup$

Hint:

Note that, $a^3\equiv 0,1^3,2^3,3^3,4^3,5^3,6^3(\mod 7)\Rightarrow a^3\equiv 0,1,1,-1,1,-1,-1(\mod 7)$


More explanation :

Then $7\mid a\Rightarrow 7\mid a^3$ or $7\mid b\Rightarrow 7\mid b^3$.

If $7$ divides none of $a,b$, then either $a^3+b^3\equiv 0(\mod 7)$ or $a^3-b^3\equiv 0(\mod 7)$.

$\endgroup$
1
$\begingroup$

Only $\overline1$ and $\overline6$ show up for $c^3$ if $c\neq\overline0$ (working in $\mathbb Z_7$).

This implies: $$\overline0\in\{a^3,b^3,a^3+b^3,a^3-b^3\}$$

$\endgroup$
0
$\begingroup$

Let $p$ be an odd prime number, then for any arbitrary integer $a$; we have: $$ \color{Blue} { a^{\dfrac{p-1}{2}}\overset{p}{\equiv}\pm1\ \ \text{or} \ \ 0. } $$


Your question concerns the special case $p=7$; in this case we have $\dfrac{p-1}{2}=3$.



Remark(I): $x^2 \overset{p}{\equiv}1 \Longleftrightarrow x \overset{p}{\equiv}\pm1$ .


Remark(II):

  • If $p \mid a$, then $p \mid a^{\dfrac{p-1}{2}}$.

  • If $p \nmid a$, then $a^{p-1} \overset{p}{\equiv}1$.
    Now let $x:=a^{\dfrac{p-1}{2}}$; we know that $x^2\overset{p}{\equiv}a^{p-1} \overset{p}{\equiv}1$
    so by the remark(I) we can conclude that:
    $$a^{\dfrac{p-1}{2}} \overset{p}{\equiv}\pm1.$$

Remark(II) says that for any arbitrary integer $a$; we have: $$ \color{Blue} { a^{\dfrac{p-1}{2}}\overset{p}{\equiv}\pm1\ \ \text{or} \ \ 0. } $$





Now we have the following cases:

  • $p \mid a$ or $b \mid p$;
    then $p \mid a^{\dfrac{p-1}{2}}$ or $p \mid b^{\dfrac{p-1}{2}}.$

  • $p \nmid a$ and $b \nmid p$;
    if $a^{\dfrac{p-1}{2}} \overset{p}{\equiv} b^{\dfrac{p-1}{2}}$ then
    $$a^{\dfrac{p-1}{2}} - b^{\dfrac{p-1}{2}} \overset{p}{\equiv} 0;$$ if $a^{\dfrac{p-1}{2}} \overset{p}{\equiv} -b^{\dfrac{p-1}{2}}$ then
    $$a^{\dfrac{p-1}{2}} + b^{\dfrac{p-1}{2}} \overset{p}{\equiv} 0.$$

$\endgroup$
0
$\begingroup$

There's always brute force:

If $m \equiv 0 \mod 7$ then $m^3 \equiv 0 \mod 7$.

If $m \equiv \pm 1,\pm 2, \pm 3$ then $m^3 \equiv \pm 1, \pm 8, \pm 27 \equiv \pm 1, \pm 1, \mp 1 \mod 7$.

So either i) $a^3 \equiv 0 \mod 7$ and $7|a^3$, ii) $b^3 \equiv 0 \mod 7$, and $7|b^3$, iii) $a^3 \equiv b^3 \mod 7$ and $7|a^3 - b^3$, or iv) $a^3 \equiv -b^3 \mod 7$ and $7|a^3 + b^3$.

But it's probably more practical to note:

For $p$ an odd prime, either $a \equiv 0 \mod p$ and $p|a^{\frac {p-1}2}$. Or $b \equiv 0 \mod p$ and $p|b^{\frac {p-1}2}$ or neither $a$ not $b$ is congruent modulo $p$ so $a^{p-1}\equiv b^{p-1} \equiv 1 \mod p$ in which case $a^{p-1}- b^{p-1} = (a^{\frac {p-1}2} + b^{\frac {p-1}2})(a^{\frac {p-1}2} - b^{\frac {p-1}2}) \equiv 0 \mod p$.

So if neither $p|a^{\frac {p-1}2}$ or $p|b^{\frac {p-1}2}$ then $p|a^{\frac {p-1}2} + b^{\frac {p-1}2}$ or $p|a^{\frac {p-1}2} - b^{\frac {p-1}2}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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