Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
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$.
