How to choose a special modulus to show that $6n^3 +3 = m^6$ has no solutions in the integers I was stuck on a problem from Mathematical Circles: Russian Experience, which reads as follows:

Prove that the number $6n^3 + 3$ cannot be a perfect sixth power of an integer for any natural number n. 

The problems previous to this dealt with proving that numbers cannot be a cube and cannot be a square. The hints offered to these problem said that a square leaves a remainder of 0 or 1 when divided by 3 or 4, and that a cube leaves a remainder of 0, 1 or 8 when divided by 9. However, for this problem, the hint states that the reader should "experiment by dividing the number by 7 and comparing it remainders of sixth powers divided by 7". 
Where did that come from? How would the solver figure out that $6n^3 + 3$ should be divided by 7? Moreover, why are 3 and 4 used in proving facts about squares, and why is 9 used when proving facts about cubes? Was this mainly through trial and error over the years, or is there some obvious fact that I'm blanking out on? 
Thanks!
 A: Here is some motivation for the choice of $7$ as the modulus, as you asked. The equation that you want to show that has no solutions in the integers is $$6n^3 +3 -m^6=0.$$ When it comes to polynomial Diophantine equations, especially of the olympiad variety, a common trick is to take everything to one side, look at the equation in a certain modulus $q,$ substitute in all possible combinations of the residues and show that the expression never equals the zero residue. Both because you want to be efficient in your computations and because you want to reduce the chances of everything cancelling out to zero (this heuristic is not rigorous), the idea is to pick a modulus where the various terms in the expression will take on very few distinct values.
As far as I know, there is no general known method of finding the ideal modulus, but there are two general techniques of which I am aware: take advantage of Sophie Germain primes and Fermat's little theorem. Sophie Germain primes $p$ satisfy the fact that $2p+1$ is also a prime, and $3$ is a such a prime. By Fermat's little theorem, if $p$ is a Sophie Germain prime, then $$x^{2p}\equiv 1 \pmod{2p+1}$$ or $x\equiv 0\pmod{2p+1}.$ So $$x^p\equiv \pm 1 \pmod{2p+1}$$ or $x\equiv 0\pmod{2p+1}.$ This means $7$ is a really nice modulus because you have a cube whose resides can only be $0,1,-1,$ and a sixth power whose residues can only be $0,1.$ Then just compute the $2\cdot 3=6$ cases and none will work out. 
By the way, years ago I asked the general question on MathOverflow in this thread. (Sadly, I deleted the email address associated with that account and so can no longer access the account, sigh.)
A: I guess that the power is chosen because when working with modular arithmetic, one would directly consider euler's theorem (which is a generalization of fermat's little theorem) and see if it helps:
$$a^{\phi(n)} \equiv 1 \pmod{n}$$
If $a$ and $n$ are relatively prime, and $\phi(n)$ is euler's totient function. Now seeing that the problem required $m^6$, one would see which $n$ in euler's theorem would give him $\phi(n)=6$. The well known property of the totient function is that for any prime $p$, $\phi(p)=p-1$ and this works with us so we have to check modulo $7$. As far as I know, there isn't a secret formula to see which modulo would be the most useful. However, there are some useful things to consider, check the brilliant wiki "Diophantine equations: modular arithmetic considerations".
Now, back to the problem!
Hint: try the case $7|6n^3+3$ and prove there's a contradiction to get $7 \nmid6n^3+3$ so you can use fermat's little theorem/euler's theorem and modular arithmetic to prove that it can't be.
Solution:
$$6n^3+3=m^6$$
If $7| 6n^3+3$, we have 
$$6n^3 \equiv-3 \pmod{7} \implies 2n^3 \equiv-1 \equiv6 \pmod{7}$$
$$\implies n^3 \equiv3 \pmod{7}$$
which is impossible. So $7 \nmid 6n^3+3 \implies 7 \nmid m^6$
$$\implies m^6 \equiv1 \pmod{7} \tag{FLT}$$
$$\implies 6n^3 \equiv2 \pmod{7} \implies 3n^3 \equiv1\equiv8\equiv15 \pmod{7}$$
$$\implies n^3 \equiv5 \pmod{7}$$
which is also impossible.
A: $6n^3+3=m^6\tag{1}$ 
$n^3\equiv {0,1,6} \pmod{7}$ then $6n^3+3\equiv {2,3,4} \pmod{7}$.
On the other hand, $m^6\equiv {0,1} \pmod{7}$
Hence $LHS$ is not equal to $RHS$ $\pmod{7}.$
Therefore equation $(1)$ has no intger solution.
