Lemma: Let $p$ be a prime number satisfying $p \equiv 5 \pmod 6$ and $m_1,m_2$ be positive integers. Then ${m_1}^3 \equiv {m_2}^3 \pmod p \: \Longrightarrow \: m_1 \equiv m_2 \pmod p$ Proof: If there exist positive integers $m_1,m_2$ such that ${m_1}^3 \equiv {m_2}^3 \pmod p \; , \; m_1 \not\equiv m_2 \pmod p$ $\Longrightarrow \: (m_1-m_2)({m_1}^2+m_1m_2+{m_2}^2) \equiv 0 \pmod p$ $\Longrightarrow \: {m_1}^2+m_1m_2+{m_2}^2 \equiv 0 \pmod p$ $\Longrightarrow \: (2m_1+m_2)^2 \equiv -3{m_2}^2 \pmod p $ This means that $-3$ is a square residue modulo $p.$ But we know that this is impossible since $p \equiv 5 \pmod 6$ The proof of the lemma is done. By this lemma, if we choose a prime number $p \equiv 5 \pmod 6$ with $p \nmid n,$ there exists a natural number $m$ such that $n \equiv m^3 \pmod p$ Solution is done.

For each $p \nmid n$ there exists such $m$ because $1^3, 2^3, 3^3, \ldots, (p-1)^3 $ are distinct (modulo $p$).

I have just copied and pasted my post. SKhan wrote: Here is my solution for problem 3. Let $q$ be the smallest prime number ($5\mod 12$) which does not divide $n$. $5$ and $12$ are coprime so there are infinitely many primes of the form $5 \mod 12$ (by Dirichlet's Theorem) so there exists a smallest prime of that form which does not divide $n$. LEMMA 1: There does not exist an integer $k$ such that $k^2\equiv -3\mod q$ By the law of quadratic reciprocity: $\left(\frac{3}{q}\right)\cdot \left(\frac{q}{3}\right)=(-1)^{\frac{3-1}{2}\cdot\frac{q-1}{2}}=1$ $\left(\frac{q}{3}\right)=-1$ because $q\equiv 2\mod 3$ Hence $\left(\frac{3}{q}\right)=-1$ $q\equiv 1\mod 4$ so $\left(\frac{-1}{q}\right)=1$ So $\left(\frac{-3}{q}\right)=-1$ Hence there does not exist an integer $k$ such that $k^2\equiv -3\mod q$ LEMMA 2: If $q\not|a-b$ then $q\not|a^3-b^3$, where $a$ and $b$ are integers. Suppose that $q$ divides both $a$ and $b$ then $q|a-b$ so $q$ cannot divide both $a$ and $b$. W.l.o.g. we can assume that $q\not|b$ Suppose on the contrary that $q|a^3-b^3$ then because $q\not|a-b$ we get $q|a^2+ab+b^2$ Then $q|(2a+b)^2+3b^2$ $b$ and $q$ are coprime so there exists integers $c$ and $d$ such that $bc+qd=1$ $q|(2a+b)^2+3b^2$ so $q|(2ac+bc)^2+3(bc)^2$ Then $0\equiv (2ac+bc)^2+3(bc)^2\equiv (2ac+bc)^2+3(1-qd)^2\equiv (2ac+bc)^2+3 \mod q$ So $(2ac+bc)^2\equiv -3 \mod q$ CONTRADICTION (by lemma 1) So $q\not|a-b\implies q\not|a^3-b^3$ Now consider the sequence $1^3, 2^3, 3^3, \cdots, (q-1)^3$ Let $m_1$ and $m_2$ be any two terms (distinct) of the sequence then none of them are divisible by $q$. By lemma 2: $m_1\not\equiv m_2 \mod q$ So each term of the sequence is different $\mod q$ So if $q\not|n$ there exists an integer $m$ such that $n\equiv m^3 \mod q$ By letting $p=q$ we are done.

Can't you just say that any number of the form $6k+5$ has a prime factor of that same form? Then, all we need to do is find an m such that $m^3-n=6k+5$. But this is easy as every number from $0$ to $5$ is a cube mod $6$. Thus $m$ could be any number congruent to a specific value $C$ mod $6$. Now we have to make sure the prime $p$ dividing $m^3-n$ doesn't divide $n$. But if it did, it would have to divide $m^3$, so it would have to divide $m$. But we could have let $m$ be any number congruent to $C$ mod $6$, so there is obviously some $m$ where $p\nmid m$. So if we pick this $m$ then $p \nmid n$. Of course, I think you both proved a stronger statement, that for any given $p \equiv 5 \pmod 6$ where $p\nmid n$ we can find an $m$.

Choose an arbitrary $p\equiv 5\pmod 6$. (Actually any $p$ not congruent to 1 (mod 3) will work.) Since $p-1$ and 3 are relatively prime, there exist positive integer $u$ and integer $v$ such that $(p-1)u+3v=1$. Thus $n\equiv n^{(p-1)u+3v}\equiv\((n^v)^3\pmod p$. Choose $m$ such that $m\equiv n^v\pmod p$, and we are done.

consider a prime $p=-1(mod6)$ that doesn't divide $n$ then we claim that , there are exactly $p-1$ ''cubic residues'' $(mod p)$ [not counting 0] suppose $r,s$ are in {$1,2,...,p-1$}.math=inline]$r \neq s$[/math. then suppose $r^3=s^3 (mod p)$ then $r^2+s^2+rs=0(mod p)$ . so , $p$ divides $4r^2+4rs+4s^2$ i.e. $-3$ is a q.r. moduldo $p$ , which is a contradiction as $p=-1(mod 6)$ . so , the ''cubic residues '' $mod p$ are ${1,2,...,p-1}$ now , let $n=t(mod p)$. using our claim , we get , there exists $m$ such that $m^3=t (modp)$. . hence done

Let $p$ be any prime of the form $6k-1$ which is coprime to $n$. Let $a$ be the integer with $an \equiv 1 \pmod p$ Now, $(n,p)=1 \Rightarrow (a,p) = 1$, so $a^{p-1} \equiv 1 \pmod p$ Or, $a^{6k-2} \equiv 1 \pmod p \Rightarrow a^{6k-3} \equiv \frac 1a \pmod p$ So, $n \equiv a^{6k-3} \pmod p \Rightarrow n \equiv (a^{2k-1})^3 \equiv m^3 \pmod p$, and we are done.

I'm sorry to revive this thread, but isn't $p \equiv 2 ($ $mod$ $3)$ enough? Here is my solution: Since $p \nmid n$, $n^{2p-1} \equiv n($ $mod$ $p)$. Let $p=3k+2$ and then $2p-1=3(2k+1)$, so $n^{2p-1}=(n^{2k+1})^3 \equiv n($ $mod$ $p)$, and just choose $m=n^{2k+1}$.