Benelux Mathematical Olympiad competition problems

Solution:

a.
Let $g$ be a positive integer with the given property. So for each odd prime number $p$ there exists a positive integer $n$ such that $p \mid g^{n}-n$ and $p \mid g^{n+1}-(n+1)$.
If $g$ has an odd prime factor $p$, then from $p \mid g^{n}-n$ it follows that $p \mid n$, while from $p \mid g^{n+1}-(n+1)$ we deduce that $p \mid n+1$. But $p$ cannot divide both $n$ and $n+1$; contradiction. So $g$ is a power of $2$: $g=2^{k}$ for some $k \geqslant 0$.
If $g=2^{0}=1$, then $p \mid 1-n$ and $p \mid 1-(n+1)$, which is again a contradiction.
Suppose $k \geqslant 2$. Then $g-1$ has an odd prime factor $p$, therefore $g \equiv 1\pmod{p}$ so $0 \equiv g^{n}-n \equiv 1-n\pmod{p}$ and $0 \equiv g^{n+1}-(n+1) \equiv 1-(n+1)\pmod{p}$, which is again a contradiction.
Now we prove that $g=2^{1}=2$ does satisfy the condition. Let a prime $p>2$ be given. Choose $n=(p-1)^{2}$, then we have $n \equiv(-1)^{2}=1\pmod{p}$. By Fermat's little theorem (using $\gcd(2, p)=1$) we know that $2^{p-1} \equiv 1\pmod{p}$, so
$$2^{n}=2^{(p-1)^{2}}=\left(2^{p-1}\right)^{p-1} \equiv 1 \equiv n \quad(p)$$
Multiplying both sides by $2$, we see that also
$$2^{n+1} \equiv 2 n=n+n \equiv n+1 \quad(p)$$
We conclude that only $g=2$ has the given property.

b.
Let $g$ be a positive integer with the given property. So for each odd prime number $p$ there exists a positive integer $n$ such that $p \mid g^{n}-n^{2}$ and $p \mid g^{n+1}-(n+1)^{2}$.
If $g$ has an odd prime factor $p$, then from $p \mid g^{n}-n^{2}$ it follows that $p \mid n^{2}$, so also $p \mid n$, while from $p \mid g^{n+1}-(n+1)^{2}$ we deduce that $p \mid(n+1)^{2}$, so also $p \mid n+1$.
But $p$ cannot divide both $n$ and $n+1$; contradiction. So $g$ is a power of $2$: $g=2^{k}$ for some $k \geqslant 0$.
If $g=2^{0}=1$, then for any odd prime $p$ we have $p \mid 1-n^{2}=(1-n)(1+n)$ and $p \mid 1-(n+1)^{2}=(1-(n+1))(1+(n+1))$. Now take $p=5$. The first statement says that $n \equiv 1$ or $n \equiv-1 \equiv 4\pmod{5}$, and the second that $n \equiv 0$ or $n \equiv-2 \equiv 3$ $\pmod{5}$. But this yields a contradiction.
If $g=2^{1}=2$, then for any odd prime $p$ we have $p \mid 2^{n}-n^{2}$ and $p \mid 2^{n+1}-(n+1)^{2}$. Now take $p=3$. As $3 \nmid 2^{n}$ and $3 \nmid 2^{n+1}$, we know that $3 \nmid n^{2}$ and $3 \nmid(n+1)^{2}$. So these two squares must be $1$ modulo $3$ (as $2$ can never be a square modulo $3$). Therefore also $2^{n}$ and $2^{n+1}$ must be $1$ modulo $3$, which gives $2 \cdot 1 \equiv 2 \cdot 2^{n}=2^{n+1} \equiv 1\pmod{3}$; contradiction.
Now suppose $k \geqslant 2$. Then $g-1$ has an odd prime factor $p$, therefore $g \equiv 1\pmod{p}$ so $0 \equiv g^{n}-n^{2} \equiv 1-n^{2}=(1-n)(1+n)\pmod{p}$ and $0 \equiv g^{n+1}-(n+1)^{2} \equiv 1-(n+1)^{2}=(1-(n+1))(1+(n+1))\pmod{p}$. Suppose $p \geqslant 5$. The first statement says that $n \equiv 1$ or $n \equiv-1\pmod{p}$, and the second that $n \equiv 0$ or $n \equiv-2\pmod{p}$. But $n$ can only be congruent to at most one of the numbers $-2,-1,0$ and $1$, since $p \geqslant 5$; contradiction. We conclude that $p=3$, so $g-1$ contains only prime factors $3$. Hence $2^{k}-1=3^{\ell}$ for some $\ell>0$. We see that $2^{k}-1 \equiv(-1)^{k}-1\pmod{3}$, while $3^{\ell} \equiv 0\pmod{3}$. So $k$ has to be even, say $k=2 m$, and our equation becomes $2^{2 m}-1=3^{\ell}$, or equivalently $\left(2^{m}-1\right)\left(2^{m}+1\right)=3^{\ell}$. Not both factors on the left-hand side can be divisible by $3$, so $2^{m}-1=1$ and $2^{m}+1=3^{\ell}$, so $m=1$. Hence $g=2^{2}=4$.
Now we show that $g=4$ does have the given property. For this we use that $g=2$ is a solution to part (a): for any odd prime $p$ there exists a positive integer $n$ such that
$$n \equiv 2^{n} \quad\pmod{p} \quad \text{ and } \quad n+1 \equiv 2^{n+1} \quad\pmod{p} .$$
Taking the square of both congruences, we obtain
$$n^{2} \equiv\left(2^{n}\right)^{2}=\left(2^{2}\right)^{n}=4^{n} \quad\pmod{p}$$
and
$$(n+1)^{2} \equiv\left(2^{n+1}\right)^{2}=\left(2^{2}\right)^{n+1}=4^{n+1} \quad\pmod{p}$$
as desired.
We conclude that only $g=4$ has the given property.