Find all $n$ for which $n^2+n+1$ is divisible by 73

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

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$.

Answer 4

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$.