The following is from Meru Alagalingam, who for some strange reasons doesn't want to register here and told me to post it: Let $p$ be a prime. Then we write $p^{k}\parallel n$ iff $p^{k}|n$ but $p^{k+1}\not|n$. We will prove a stronger statement than requested in the problem: For each natural number $n$, $n\geq 2$, there is a natural number $x\not\equiv 0\mod 3$ for which $f\left(x\right)$ is divisible by $3^{n}$ but not by $3^{n+1}$. And we will prove that by mathematical induction on $n$ whereas the basis case is trivial as $3^{2}\parallel f\left(1\right)$ with $1\not\equiv 0\mod 3$. So given any $x\not\equiv 0\mod 3$ for which $3^{n}\parallel f\left(x\right)$ we want to construct a $y\not\equiv 0\mod 3$ for which $3^{n+1}\parallel f\left(y\right)$ and if we succeed we're done: \[a\not\equiv 0\mod 3\Longrightarrow 3^{b}a^{2}\equiv 3^{b}\mod 3^{b+1}\] \[\Longrightarrow\left(a+3^{b-1}\right)^{3}=a^{3}+3a^{2}3^{b-1}+3a3^{2b-2}+3^{3b-3}\equiv a^{3}+3^{b}\mod 3^{b+1}\ \ (1)\] $3^{n}\parallel x^{3}+17$, i.e. you can distinguish two cases: Case 1: $x^{3}+17\equiv 2\cdot 3^{n}\mod 3^{n+1}$ \[3^{n}\parallel x^{3}+17\Longrightarrow x\not\equiv 0\mod 3 \\ \Longrightarrow \left(x+3^{n-1}\right)^{3}+17\equiv x^{3}+3^{n}+17\equiv 2\cdot 3^{n}+3^{n}\equiv 0\mod 3^{n+1}\\ \Longrightarrow y: =x+3^{n-1}\] Case 2: $x^{3}+17\equiv 3^{n}\mod 3^{n+1}$ \[\left(x+2\cdot 3^{n-1}\right)^{3}+17 = \left(\left(x+3^{n-1}\right)+3^{n-1}\right)^{3}+17\equiv\left(x+3^{n-1}\right)^{3}+3^{n}+17\\ \equiv x^{3}+3^{n}+3^{n}+17\equiv 3^{n}+3^{n}+3^{n}\equiv 0\mod 3^{n+1}\\ \Longrightarrow y: =x+2\cdot 3^{n-1}.\] In both cases $y\equiv x\not\equiv 0\mod 3$. Case 1: $3^{n+2}\not|y^{3}+17$ and we are done. Case 2: $3^{n+2}|y^{3}+17$ and $3^{n+1}\parallel z^{3}+17$ whereas $z: =y+3^{n}$: \[z\equiv y\equiv x\not\equiv 0\mod 3\] \[z^{3}+17=\left(y+3^{n}\right)^{3}+17=\left(y+3^{n-1}+3^{n-1}+3^{n-1}\right)^{3}+17\equiv y^{3}+3^{n}+3^{n}+3^{n}+17\equiv 0\mod 3^{n+1}\] follows by applying (1) repeatedly, i.e. $3^{n+1}|z^{3}+17$ but (1) also yields $z^{3}+17=\left(x+3^{n}\right)^{3}+17\equiv x^{3}+3^{n+1}+17\not\equiv x^{3}+17\equiv 0\mod 3^{n+2}$, i.e. $3^{n+2}\not|z^{3}+17$.

ZetaX wrote: We will prove a stronger statement than requested in the problem: For each natural number $n$, $n\geq 2$, there is a natural number $x\not\equiv 0\mod 3$ for which [...] That's not really stronger, is it? If $x\equiv0\pmod3$ then automatically $3\not|f(x)$.

Here's my solution. Sorry, i don't know Latex type setting, so i've attached my solution as a word document.

Help me! I don't understand ZetaX wrote: Case 1: $3^{n+2}\not|y^{3}+17$ and we are done. Case 2: $3^{n+2}|y^{3}+17$ and $3^{n+1}\parallel z^{3}+17$ whereas $z: =y+3^{n}$.

tanrock wrote: Help me! I don't understand ZetaX wrote: Case 1: $3^{n+2}\not|y^{3}+17$ and we are done. Case 2: $3^{n+2}|y^{3}+17$ and $3^{n+1}\parallel z^{3}+17$ whereas $z: =y+3^{n}$. me too . please explain more

We will prove the problem by mathematical induction on $n$. The basis case, $n=2$, is successful when $x=1$. Let $x_0$ be the number satisfying $3^n \parallel f(x)$. And we will find $a$ such that $3^{n+1} \parallel f(x_0 + a) $. $(x_0 + a)^3 + 17 = a^2 ( a+ 3x_0 ) + 3ax^2 + (x^3 +17)$. Obviously, $3 \not | x_0$. If $3^n | a$, $a^2 ( a+ 3x_0 ) + 3ax^2 + (x^3 +17) \equiv 3a + k \times 3^n \mod 3^{n+2}$ where $k<3$. Then, when $a = 3^n - k \times 3^{n-1}$, the proof finishes since $3a + k \times 3^n \equiv 3^{n+1} \mod 3^{n+2}$.

so, what should we do when 3<k ????

Equivalent statement:Suppose $n\in \mathbb N$,and $n\ge 2$,prove:there are $m\in \mathbb N$ such that $3^n||m^3+17$. Induction:$n=2$,take $m=1$. Suppose the statement is true for $n(\ge 2)$,that is there exists $m\in \mathcal N$ such that $m^3+17=3^n(3q+r)$,$r\in \{1,2\},q\in \mathbb N$.Then $3$ does not divide $m$,implies $m^2\equiv 1(mod 3)$. For any positive integer $s$,we have $(m+3^{n-1}s)^3+17=m^3+17+3^nm^2s+3^{2n-1}ms^2+3^{3n-3}s^3\equiv 3^n(3q+r)+3^ns=3^n(r+s)(mod 3^{n+1})$. If $s=3-r$,let $x_1=m+3^{n-1}(3-r)$,easily $3^{n+1}|x_1$.If $s=6-r$,let $x_2=m+3^{n-1}(6-r)$,also $3^{n+1}|x_2$.We prove at least one of $x_1,x_2$ is not divided by $3^{n+2}$ is Ok.Assume sake of contradiction,then $0\equiv x_2^3+17=(x_1+3^n)^3+17=x_1^3+17+3^{n+1}x_1^2+3^{2n+1}x_1+3^3n\equiv x_1^3+17+3^{n+1}\equiv 3^{n+1}(mod 3^{n+2})$.Contradiction.

we prove it using induction. the base step for $n=1$ is obvious, now assume that we have proved it for $n=k,k>3$ and we prove it for $n=k+1$. according to induction $\exists a : 3^k \mid a^3 +17 , 3^{k+1} \nmid a^3+17 \implies a^3+17=3^k \times r$ that $3 \nmid r$ now we prove that for some $n : 3^{k+1} \mid (n\times 3^{k-1}+a)^3+17, 3^{k+2} \nmid (n\times 3^{k-1}+a)^3+17$ which is equivalent to proving that: $(n\times 3^{k-1}+a)^3+17 \equiv 3^{k+1} \mod 3^{k+2}$ $(n\times 3^{k-1}+a)^3+17=n^3 \times 3^{3k-3} + 3a(n\times 3^{k-1})(n\times 3^{k-1}+a) + a^3+17 \equiv$ $(a^3+17) +3a^2(n\times 3^{k-1}) \equiv r\times 3^k + 3^k\times (a^2n) \equiv 3^{k+1} \mod 3^{k+2} \iff r + a^2n \equiv 3 \mod 9$ and we easily see because $a,r$ are constants and $3\nmid r,a \implies \exists b : ba^2 \equiv 1 \mod 9 \implies n \equiv (3-r)\times b \mod 9$