# Find least prime $p > 1000$ that divides $2^{1010} \cdot 23^{2020} + 1$

The Question (from Purple Comet math contest 2020):

Find the least prime $$p > 1000$$ that divides $$n = 2^{1010} \cdot 23^{2020} + 1$$.

What I tried:

So I want to figure out the least prime $$p > 1000$$ that divides that mess.

I first rewrote $$n$$ as $$((46 \cdot 23)^2)^{505} + 1$$ since this tells us that $$m = (46 \cdot 23)^2 + 1 \mid ((46 \cdot 23)^2)^{505} + 1$$.

So I was thinking if we could find the prime factors of $$m$$, they would also be prime factors for $$n$$, then maybe one of them is $$> 1000$$. But there is no guarantee that any would be the minimum.

I am stuck at this point as I have a feeling that tediously finding prime factors of $$m$$ is not a safe approach. I am a beginner at these kinds of questions, so I don't know/have experience with many number theory techniques for these sorts of problems.

My Question: What techniques/small hints would be useful for this problem?

• Trial and error works almost immediately.
– lulu
Aug 6, 2021 at 20:25
• Trial and error meaning just working my way up the list of primes > 1000 and checking if they divide? I think I am understanding wrong. @lulu Aug 6, 2021 at 21:09
• Yes, that's what it means. It works almost instantly.
– lulu
Aug 6, 2021 at 21:11
• To be clear: perhaps you don't know how to compute expressions like this modulo a prime. If that's the case, the you should first study modular arithmetic.
– lulu
Aug 6, 2021 at 21:13
• Yeh, I am not familiar with this. I guess that is why I got stuck. Thank you @lulu Aug 6, 2021 at 21:13

Recognize that for contest questions like this, you generally have to do trial and error, so you might as well get started with that.

• Even if you have some magical way of showing that some particular prime $$p > 1000$$ divides $$n$$, you'd still need to check all smaller primes just in case they might divide $$n$$. As such, you can't easily get away from trial and error.
• In addition, because you can't easily get away from trial and error, one would expect that the answer is one of the first few values that we try (in order for the question to be answerable within a reasonable time). I would be very surprised if you have to check 10 or more values.

(First bullet: Finding that particular prime)
In this case, we can let $$M = 2^2 \times 23^4$$ and observe that $$M + 1 \mid M^5 + 1 = n$$.
Then, since $$M+1 = 5 \times 13 \times 17 \times 1013$$, we conclude that $$1013 \mid n$$.

(Second bullet: Justifying that is truly the smallest)
However, we still do not know if $$1009 \mid n$$ as it might have divided the other factor.
So we'd still have to verify that $$1009 \not \mid n$$

Use FLT to conclude that $$2^{1010} \times 23^{2020} \equiv 2^2 \times 23^4 \equiv 383 \not \equiv -1 \pmod{1009}$$.

in order to conclude that 1013 is the smallest such prime.

Note: In my comment on river's solution, I suggest that FLT isn't that helpful in determining $$p$$. What I meant is that even if we know that $$2^{p-1} \equiv 1 \pmod{p}$$, all that we have is

$$2^{p -1011} \times 23^{ 2p - 2021} \equiv -1 \mod{p}$$

and will still need to check for various values of $$p$$.

FLT does help in that it makes $$p-1011$$ a lot smaller for $$p > 1000$$, so the case checking is a lot easier.
However, we'd still have to check each $$p$$ (as per above), as opposed to almost immediately solving for $$p$$.

Changing it to modular arithmetic will help:

$$p | n$$ is equivalent to $$n \equiv 0 \pmod p$$

so we want to find $$p$$ where

$$2^{1010} \cdot 23^{2020} \equiv -1 \pmod p$$

you can apply Fermat's little theorem in the search

• Ahh, I need to look up what Fermat's little theorem is. I will take your approach. Aug 6, 2021 at 20:20
• Can you elaborate on how FLT helps arrive at the answer? (And in particular, can you confirm that you've arrived at the answer, in order to know if FLT is a helpful hint.) Aug 6, 2021 at 22:37