# What possible remainders do perfect cubes leave when divided by $7$?

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.

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

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

• 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. – Henno Brandsma Apr 2 '16 at 7:57
• @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$. – Patrick Stevens Apr 2 '16 at 8:19
• The remainder upon division by $r$ is by definition a number from 0 to $r-1$. – Henno Brandsma Apr 2 '16 at 8:20
• 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. – Wharf Rat Apr 2 '16 at 8:24
• In my view this indeed follows from the quotient remainder theorem. – Henno Brandsma Apr 2 '16 at 8:26

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