Primality testing

Question

Suppose we know that exactly one of the three integers 2^{1000} + 277, 2^{1000} + 291 and

2^{1000} + 297 is prime. How can we find which one is prime? None of these integers has a small prime factor (<10^8)

Answer 1

Let's denote n₁=2¹⁰⁰⁰+277, n₂=2¹⁰⁰⁰+291,n₃=2¹⁰⁰⁰+297.

To determine which one is prime, we can consider checking these numbers modulo small primes to eliminate some possibilities and identify patterns. This will allow us to check their behavior without directly factoring large numbers. For simplicity, let's examine the numbers modulo a few small primes like 3, 5, and 7.

Checking modulo 3:

We want to compute 2¹⁰⁰⁰mod  3 , as well as the three integers modulo 3.

Since

2≡−1(mod3)2 ,

we have:

2¹⁰⁰⁰=(−1)¹⁰⁰⁰ ≡1(mod3)

Now check the three numbers modulo 3: n₁

n₁=2¹⁰⁰⁰+277 = 1+277 ≡ 1+1 = 2(mod3)

n₂=2¹⁰⁰⁰+291 = 1+291 ≡1+0 = 1(mod3)

n₃=2¹⁰⁰⁰+297 = 1+297 ≡ 1+0=1(mod3)

Thus, n₁= 2(mod3), n₂ =1(mod3) and n₃ =1(mod3)

Since a prime number cannot be divisible by 3 unless it's 3 itself, n1 is not divisible by 3 and could potentially be prime, but n2 and n3​ are divisible by 3, making them composite.

Given that n₂ ≡ 0(mod3) n₃ ​ ≡ 0(mod3), both n2 ​ and n3 are divisible by 3, so they are not prime.

Thus, the only candidate left is n₁=2¹⁰⁰⁰+277, which is not divisible by 3, and since we are told that exactly one of the numbers is prime, n1 must be the prime number.

No need to check for other primes 5, 7, etc.