0
$\begingroup$

Would I use the quotient remainder theorem for this? How can I figure out the remainders perfect cubes leave when divided by a certain number without just listing perfect cubes and dividing by $7$ to find the remainder?

I know that after $10^3$ the final digit of the cubes 'resets' and follows a cycle - but just dividing the first $10$ cubes (of the natural numbers) by $7$ seems a bit shabby to me.

$\endgroup$
2
  • 3
    $\begingroup$ Just calculate $0^3,1^3,\dots,6^3$ modulo $7$. $\endgroup$ – Sil Apr 2 '16 at 7:51
  • 1
    $\begingroup$ They leave $x^3 \equiv 0, 1, 6 \mod 7$ $\endgroup$ – TheRandomGuy Apr 2 '16 at 8:27
1
$\begingroup$

A number can be 0 mod 7, and then so is its cube. Similarly for 1 mod 7. For numbers that are 2 mod 7 we get their cube is 8 mod 7, so in fact 1 mod 7, and so on.

You just need to check 0 to 6 mod 7 and what their cubes are in the group $\mathbb{Z}_7$.

$\endgroup$
7
  • 1
    $\begingroup$ There are only 7 possible remainders. If a number has remainder $x$ mod 7, then its cube has remainder $x^3$ mod 7. Yes for 25 as well. Then you need to check all 25 options for remainders. $\endgroup$ – Henno Brandsma Apr 2 '16 at 7:57
  • 1
    $\begingroup$ @EkalAnwa Because $(7+x)^3 = 7^3 + 7^2 x \times 3 + 7 \times x^2 \times 3 + x^3$, and the first three terms do not contribute modulo $7$. $\endgroup$ – Patrick Stevens Apr 2 '16 at 8:19
  • 2
    $\begingroup$ The remainder upon division by $r$ is by definition a number from 0 to $r-1$. $\endgroup$ – Henno Brandsma Apr 2 '16 at 8:20
  • 1
    $\begingroup$ I'm close to getting it I think - is that to do with the quotient remainder theorem? All so I know the site says to not put "thanks" in this section but I really appreciate your patience in helping me. $\endgroup$ – Wharf Rat Apr 2 '16 at 8:24
  • 2
    $\begingroup$ In my view this indeed follows from the quotient remainder theorem. $\endgroup$ – Henno Brandsma Apr 2 '16 at 8:26
2
$\begingroup$

By Fermat's little theorem, $$0\equiv n^7-n=n(n^3-1)(n^3+1)\pmod 7.$$ Because $7$ is prime, either $n\equiv0$, $n^3\equiv1$ or $n^3\equiv-1$, so the only possible cubic residues modulo $7$ are $-1,0,1$. These are all possible, as they are the residues of $(-1)^3,0^3,1^3$.

In general, things aren't that easy and one has to compute a list of residues mod $p$. Number theory tells us the following:

If $p$ is prime, then there are exactly $\frac{p-1}{\gcd(n,p-1)}$ nonzero $n$th power residues modulo $p$ (which, together with $0$ makes $1+\frac{p-1}{\gcd(n,p-1)}$).

In the case of $(p,n)=(7,3)$ as above, this is $1+\frac63=3$.

$\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.