11
$\begingroup$

Yeah so I'm kind of stuck on this problem, and I have two questions.

  1. Is there a way to define a number mathematically so that it cannot be a multiple of $7$? I know $7k+1,\ 7k+2,\ 7k+3,\ \cdots$, but that will take ages to prove for each case.

  2. Is this a proof? $$(7k + a)^3 \equiv (0\cdot k + a)^3 \equiv a^3 \bmod 7$$

Thank you.

$\endgroup$
4
  • 1
    $\begingroup$ 2. Anyway, $7k+a\equiv a \bmod 7$. $\endgroup$ Commented Jun 30, 2016 at 19:58
  • 1
    $\begingroup$ Right. Now look at the nonzero cubes mod 7. You can just do the computations by hand and see the result. $\endgroup$
    – user4894
    Commented Jun 30, 2016 at 19:58
  • $\begingroup$ As to "defining" the non-multiples of $7$ mathematically, one could say $a^6\equiv 1\pmod{7}$. This could be then used as a basis for a proof, but the computations suggested in the answers are much the better way. $\endgroup$ Commented Jun 30, 2016 at 20:08
  • 1
    $\begingroup$ For your 2), I'd prefer: $\quad(7k + a)^3 \equiv 7^3k^3 + 3\cdot7^2k^2a+ 3\cdot7ka^2+a^3 \equiv a^3 \bmod 7$ $\endgroup$
    – Joffan
    Commented Jun 30, 2016 at 20:09

8 Answers 8

17
$\begingroup$

Actually there is a more general theorem.

THEOREM. Let $p = 2a+1$ be a prime number. Then $n^a \equiv \pm 1 \pmod p$ for all $n \not \equiv 0 \pmod p$

PROOF. Because $p$ is a prime number, $\mathbb Z_p$ is a field and $\mathbf U_p$ is a cyclic multiplicative group. Hence there exists an integer, $g$ such that $\mathbf U_p = \{g, g^2, g^3, \dots g^{p-1}\}$. Hence the polynomial $x^{p-1} - 1$ has $p-1$ distinct roots; namely the members of $\mathbf U_p$.

Since $\dfrac{p-1}{2} = a$, $x^{p-1} - 1 \equiv (x^a-1)(x^a+1) \pmod p$. Hence $a$ of the members of $\mathbf U_p$ are roots of $x^a-1$ and the other $a$ members of $\mathbf U_p$ are roots of $x^a+1$. The theorem follows.

$\endgroup$
2
  • $\begingroup$ You seem to deduce that x^(p - 1) = 1 for all x in the multiplicative group mod p from the fact that this group is cyclic. But I don't know any way to show that this group is cyclic that doesn't require FIRST showing that x^(p - 1) = 1 for each x. I'd be interested to know of any such proof, though, if there is one. $\endgroup$ Commented Jul 1, 2016 at 5:34
  • $\begingroup$ @SridharRamesh - No, my only point was that the group contained p-1 elements. $\endgroup$ Commented Jul 1, 2016 at 5:51
15
$\begingroup$

By Fermat's little theorem, if $p$ is prime, $$x\not\equiv 0\pmod p \Leftrightarrow x^{p-1}\equiv 1\pmod p$$

Further,$$y^2\equiv 1\pmod p \Leftrightarrow y\equiv \pm 1\pmod p$$

As 7 is prime, we can enter the value into the first expression and the result follows from the second.

$$x^6\equiv 1\pmod 7 \Rightarrow x^3\equiv \pm 1\pmod 7$$

Calculation of cases is unnecessary.

$\endgroup$
1
  • 2
    $\begingroup$ Since the OP's question only requires the basics of modular arithmetic, they might not know Fermat's little theorem so it might be worth mentioning it by name. $\endgroup$
    – Silverfish
    Commented Jul 1, 2016 at 0:44
14
$\begingroup$

That's part of a proof. For a full proof, you should check the cases $a=1,2,3,4,5,6$. Actually, you only need three of these since $(7-a)^3 \equiv (-a)^3 \equiv -a^3 \mod 7$.

$\endgroup$
2
  • 2
    $\begingroup$ +1 You beat me to it yesterday on the "only three" point. I am always amazed at the "but that will take ages to prove for each case". Have they any idea what is involved in say the first proof of the ABC result! But even basic math requires some effort :) $\endgroup$
    – almagest
    Commented Jul 1, 2016 at 12:55
  • 1
    $\begingroup$ @almagest There are those who would balk at considering cases in base 2. $\endgroup$ Commented Jul 1, 2016 at 14:29
6
$\begingroup$

We only need to check the cubes $1^3,2^3,\ldots ,6^3$ modulo $7$. The result is $$ 1^3=2^3\equiv 1\bmod 7, 3^3\equiv -1 \bmod 7, 4^3\equiv 1\bmod 7,5^3\equiv -1 \bmod 7, 6^3\equiv -1 \bmod 7. $$

$\endgroup$
5
$\begingroup$

Just to write the complete steps of the proof.

Well, first as you said, we have $$(7k + a)^3 \equiv (0*k + a)^3 \equiv a^3 \bmod 7.$$

Then, we need to show that the statement is true for each $a=1,\ 2,\ 3,\ 4,\ 5,\ 6$. For this, as Joffan stated, you may compute the cubes that leads to

$1^3\equiv 1\bmod 7,$

$2^3\equiv 1\bmod 7,$

$3^3\equiv -1 \bmod 7,$

$4^3\equiv 1\bmod 7,$

$5^3\equiv -1 \bmod 7,$

$6^3\equiv -1 \bmod 7.$

This completes the proof.

$\endgroup$
5
$\begingroup$

Say $a$ is a number not a multiple of $7$.

Then we have that $$a \equiv \pm 1 ,\pm 2,\pm 3 \pmod7 $$ $$\implies a^3 \equiv (\pm 1)^3 ,(\pm 2)^3,(\pm 3)^3\equiv \pm 1 ,\pm 8,\pm 27 \pmod7 $$ $$\implies a^3 \equiv \pm 1 \pmod7 $$

Hope this is the shortest proof possible.

$\endgroup$
3
$\begingroup$

You can first show this for $\{1,2,3,4,5,6\}$ and then show that applies to all non-multiples of $7$. \begin{align} 1^3 &= 1\\ 2^3 &= 8 = 7+1\\ 3^3 &= 27 = 4\cdot 7 -1\\ 4^3 &= 64 = 9\cdot 7+1\\ 5^3 &= 125 = 18\cdot 7 -1\\ 6^3 &= 216 = 31\cdot 7 -1 \\ \end{align}

Then use your construction to complete the proof for all numbers not multiples of $7$,

$\endgroup$
2
$\begingroup$

You only have to consider: $1^3 = 1, 2^3 = 1, 3^3 = -1, 4^3 = 1, 5^3 = -1, 6^3 = -1 \pmod 7$ .

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .