Determine all $k$ such that $k^3+k+1$ is divisible by 11 The task is the following:
Determine all $\ k\in\mathbb Z$ such that $k^3+k+1$ is divisible by 11
I assumed that "$k^3+k+1$ is divisible by 11" is saying $11|k^3+k+1$. That means I can rewrite it as a linear combination $$k^3+k+1 = 11n\quad\forall n\in\mathbb Z$$
I was thinking of factoring the polynomial on the left to make it easier to handle, but I don't think it's factorable. My guess is to use the Euclidean algorithm, but the polynomial on the left is making me uneasy.
Can someone show me how to proceed with this task?
 A: You can solve this faster by using modular arithmetic, but I won't use it:
Let $k=11t+r$ with $0\le r\le 10$. $$k^3+k+1=11\left(11^2t^3+3\cdot 11t^2\cdot r+3\cdot t\cdot r^2+t\right)+r^3+r+1$$
Therefore: $$11\mid k^3+k+1\iff 11\mid r^3+r+1$$
Now check cases $r=0,1,\ldots, 10$.
E.g., $11\nmid 0^3+0+1$ and $11\nmid 1^3+1+1$, but $11\mid 2^3+2+1$, etc.
You'll find that only $r=2$ works. Therefore, the answer is $k=11t+2$ for any $t\in\mathbb Z$.
If you could use modular arithmetic, you could solve this by checking cases $k\equiv 0,1,2,\ldots,10\pmod{11}$.
E.g., if $k\equiv 0\pmod{11}$, then $k^3+k+1\equiv 0^3+0+1\equiv 1\not\equiv 0\pmod{11}$, etc.
You would find that only $k\equiv 2\pmod{11}$ works.

Here's another solution. I could explain it without modular arithmetic, but I'll use it:
$$k^3+k+1\equiv k^3+k-10\equiv (k-2)\left(k^2+2k+5\right)\pmod{11}$$
By Euclid's Lemma:
$$\iff \left(k\equiv 2\pmod{11}\ \text{ or }\ k^2+2k+5\equiv 0\pmod{11}\right)$$
$$\iff \left(k\equiv 2\pmod{11}\ \text{ or }\ (k+1)^2\equiv 7\pmod{11}\right)$$
The second congruence has no solutions, because $7$ is not a quadratic residue mod $11$. This can be proved by checking $0^2, (\pm 1)^2, (\pm 2)^2,\ldots, (\pm 5)^2$ mod $11$ (none of these can be congruent to $7$ mod $11$), or by using Quadratic Reciprocity:
$$\left(\frac{7}{11}\right)=-\left(\frac{11}{7}\right)=-\left(\frac{4}{7}\right)=-\left(\frac{2^2}{7}\right)=-1$$
