Find all $n$ for which $n^2+n+1$ is divisible by 73 Find all $n$ for which $n^2+n+1$ is divisible by $73$.
Any suggestions how to solve it without trying all the numbers from $0$ to $72$ and checking divisibility?
 A: Note that $73=k^2+k+1$ with $k=8$. 
$$k^2+k+1|n^2+n+1\implies k^2+k+1|n^2-k^2+n-k,$$
which implies that $$k^2+k+1|(n-k)(n+k+1).$$
So, the roots are $n\equiv k$ and $n\equiv -k-1$ mod $73$. 
A: The equation implies $$73\ |\ n^3-1$$
That is $$n^3\equiv 1\bmod 73$$
Since $73$ is an odd prime, the group $(\Bbb Z/p\Bbb Z)^*$ is cyclic, of order $72$ which is a multiple of $3$, and therefore there are exactly two elements of order $3$, which are square of each other.
One of them is $8$ and the other $64$.
A: We can write:
$$n^2 + n + 1 = \frac{n^3 - 1}{n-1}$$
Therefore, we're seeking solutions of:
$$n^3 = 1 \bmod 73$$
other than $n = 1$. The solutions can be obtained by taking a primitive element $u$ of $\mathbb{Z}_{73}$ and raising that to the powers $\frac{72}{3}= 24$ and  $2\times\frac{72}{3}=48$. E.g. the number 5 is a primitive element, we can easily compute that:
$$5^{24} = 8 \bmod 73$$
and squaring gives:
$$5^{48} = 8^2 \bmod 73 = 64 \bmod 73$$
The solutions are thus $n = 8$ and $n = 64$.
A: You do not need very many trials at all.  You can see that if $n^2+n+1$ is to be divisible by $73$ then the value of the polynomial must be at least $73$, but $n^2+n+1$ must also lie between $n^2$ and $(n+1)^2$ for all positive $n$.  So instead of starting your trials at $n=0$ start them at $n=n_1$ choosing $n_1$ as the smallest positive whole number for which $(n_1+1)^2$ exceeds $73$.  If that doesn't work You next try $n=n_2$ such that $(n_2+1)^2$ exceeds $2×73$ but $n_2^2$ is less.  And so on.  Soon, you get a value of $n$ for which the polynomial hits something divisible by $73$.  (How many trials do you need? My lips are sealed on that one!)
Having found some value of $n$ such that $n^2+n+1$ is divisible by $73$, you then note that with $73$ being prime the quadratic equation can have roots for only two separate residues $\bmod 73$, and their sum, following the coefficients of the equation, must be $-1\equiv 72$.  So once you have one root you immediately infer the second with no more trials.
