Mathlinks Day 2 Problem 4

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Mathlinks Day 2 Problem 4

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

951 posts

#1 h Jul 14, 2020, 12:35 AM

Y by

Find all integers $n$ such that $2n+1$ is a divisor of $(n!)^2 + 2^n$ .

Proposed by Silouanos Brazitikos

This post has been edited 1 time. Last edited by ghu2024, Jul 14, 2020, 3:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

390 posts

Lcz

#2 h Jul 14, 2020, 12:41 AM

Y by

Casework on $2n+1$ :

Hint.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

951 posts

#3 h Jul 14, 2020, 12:55 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hellomath010118

373 posts

hellomath010118

#4 h Jul 14, 2020, 2:01 AM • 5 Y

Y by chrono223, Pluto1708, jchang0313, math_comb01, Exposter

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

966 posts

lrjr24

#5 h Jul 14, 2020, 2:50 AM

Y by

ghu2024 wrote:

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

0, that is trivial progress.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

272 posts

#6 h Jul 14, 2020, 4:04 AM • 1 Y

Y by Mango247

:oops_sign:

This post has been edited 2 times. Last edited by CROWmatician, Jul 26, 2020, 9:24 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#7 h Jul 14, 2020, 4:11 AM

Y by

@above an odd number can have an even multiple.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

272 posts

#8 h Jul 14, 2020, 4:14 AM

Y by

:oops_sign:

This post has been edited 1 time. Last edited by CROWmatician, Jul 26, 2020, 9:25 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

473 posts

rd123

#9 h Jul 14, 2020, 4:16 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

xyc

#11 h Jul 14, 2020, 5:46 AM • 1 Y

Y by Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

232 posts

sshi

#12 h Jul 14, 2020, 5:56 AM

Y by

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 post has been edited 1 time. Last edited by sshi, Jul 14, 2020, 5:56 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4655 posts

#13 h Jul 14, 2020, 6:10 AM • 1 Y

Y by TheMath_boy

This problem was proposed by Silouanos Brazitikos.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

380 posts

#14 h Jul 14, 2020, 8:54 AM • 1 Y

Y by jchang0313

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

558 posts

#15 h Jul 14, 2020, 9:09 AM • 1 Y

Y by AlastorMoody

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

This post has been edited 5 times. Last edited by Aryan-23, Jul 14, 2020, 9:15 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

390 posts

Lcz

#16 h Jul 14, 2020, 1:57 PM

Y by

How many points for only getting the 3 mod 8 case

i knew 8 worked but forgot about it

This post has been edited 2 times. Last edited by Lcz, Jul 14, 2020, 1:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

635 posts

#18 h Jul 15, 2020, 11:00 AM

Y by

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.

This post has been edited 1 time. Last edited by Physicsknight, Jul 15, 2020, 11:40 AM
Reason: Submission

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

228 posts

#19 h Jul 15, 2020, 11:35 AM • 1 Y

Y by Mango247

Physicsknight wrote:

If $2n+1\mid(n!)^2+2n.$ Then $2n+1\nmid n!,$ so $2n+1$ is prime.

$9\nmid 4!$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a