Casework on $2n+1$:

Hint.

How many points for proving $2n+1$ is prime?

You can show that $n!^2 \equiv (-1)^n (2n)! \pmod{2n+1}$. This shows that $2n+1$ is prime. Let $p=2n+1$. Then by Wilson in that case $n!^2 \equiv (-1)^{n+1} \pmod p$ Also $$2^{\frac{p-1}{2}}\equiv \left( \dfrac{2}{p} \right) \equiv (-1)^{\frac{p^2-1}{8}} \pmod p $$Thus you need two powers of $-1$ summing to $0$ so there sum must be odd. Casework mod $8$ should give $p \equiv 1/3 \pmod 8$ so the answer is $\boxed{n=\frac{p-1}{2} \quad p\equiv 1/3 \pmod 8}$.

ghu2024 wrote: How many points for proving $2n+1$ is prime? 0, that is trivial progress.

@above an odd number can have an even multiple.

$2$ is a multiple of $1$, so yes.

I’ve got 4 answers for this one and i am quite sure they are correct. First show 2n+1 is prime, then consider the parity of n, then use Wilson to get the mod for (n!)^2, finally a quadratic residue.

Hello, where can I find all of the problems to this contest? A link? It seems to me that the problems are quite nice.

This problem was proposed by Silouanos Brazitikos.

If $2n+1$ is composite, then write $2n+1 = ab$ for odd numbers $a$ and $b$. Since $a \leq n$, it divides $n!$. Obviously, it does not divide $2^n$, so therefore $2n+1$ does not divide $(n!)^2 + 2^n$. Now suppose $2n+1 = p$ for a prime $p$. Let $k$ be the number of even positive integers less than or equal to the $\frac{p-1}{2}$. Then the crucial fact is that \begin{align*} 2^{\frac{p-1}{2}} \left( \frac{p-1}{2} \right)! &= 2 \cdot 4 \cdots (p-1) \\ &\equiv (2 \cdot 4 \cdots 2k) \cdot (2k+2) \cdot (2k+4) \cdots (p-1) \\ &\equiv (2 \cdot 4 \cdots 2k) \cdot (p - 2k - 2) \cdot (p - 2k - 4) \cdots 1 (-1)^k\\ &\equiv \left(\frac{p-1}{2}\right)! (-1)^k \pmod{p} \end{align*}Thus $2^{\frac{p-1}{2}} = (-1)^k \pmod{p}$. It is a straightforward casework check to see that \[ (-1)^k = \begin{cases} 1 &\text{if $p \equiv \pm 1 \pmod{8}$} \\ -1 &\text{if $p \equiv \pm 3 \pmod{8}$} . \end{cases} \]On the other hand \[ \left(\frac{p-1}{2} \right)!^2 \equiv (-1)^{\frac{p-1}{2}} (p-1)! \equiv (-1)^{\frac{p+1}{2}} \pmod{p} . \]By Wilson's Theorem (or the very simple fact that every invertible element has one unique inverse), we know that $(p-1)! \equiv -1 \pmod{p}$. Therefore \[ (n!)^2 + 2^n \equiv (-1)^{\frac{p+1}{2}} + (-1)^{\frac{p^2-1}{8}}. \]A manual check reveals that this is 0 if and only if $p \equiv 1,3 \pmod{8}$. Therefore the answer is $n = \frac{p-1}{2}$ for all $p \equiv 1,3 \pmod{8}$.

Alternatively one can use that for all $k<p$ , we have $$(p-k)! (k-1)! \equiv (-1)^k \pmod p \implies \left(\left(\frac {p-1}{2}\right)!\right)^2 \equiv(-1)^{\frac {p+1}{2}} \pmod p$$ Now just check $p \equiv 1,3,5,7 \pmod 8$ (Keeping in mind the relevant quadratic reciprocity condition). Cute problem btw

How many points for only getting the 3 mod 8 case i knew 8 worked but forgot about it

Note, $n=\frac {(p-1)}{2} $ where $p $ is an odd prime such that $n$ is odd. If $2n+1$ is not prime, then it has a divisor less than $n,$ which divides $n!.$ If $2n+1$ is prime, then it has to be $3\pmod{4}.$ It can easily be proved that's sufficient. Because it's $\equiv -1 $ not being a quadratic residue.

Physicsknight wrote: If $2n+1\mid(n!)^2+2n.$ Then $2n+1\nmid n!,$ so $2n+1$ is prime. $9\nmid 4!$