Jason Yuan's Math Blogs

Hello everyone! Today, I want to show you another advanced problem that can be solved using basic reasoning and logic. It comes from the 2019 AIME I, placed #14 out of 15:

Find the least odd prime factor of 2019⁸ + 1.

That’s the problem. Advanced number theory problems can be tricky on the AIME and often require bashing or lots of casework, but luckily, this one can be solved quickly if you know what you are doing. 

Let’s call the prime that satisfies the problem statement p. Since p divides 2019⁸ + 1, 2019⁸ is congruent to -1 mod p. Raising the congruence to the power of 2 on both sides, 2019¹⁶ is congruent to 1 mod p. 

Now, I want to find out if 2019¹⁶ is the least power of 2019 that is congruent to 1 mod p, and this will be useful later.

If a 2019^x is congruent to 1 mod p, x must be a factor of 16 so that we can raise the congruence to a power on both sides to get 2019¹⁶ to be congruent to 1 mod p. This reasoning isn’t bulletproof, but I don’t want to get deep into proving that statement in this short blog post. 

Since 2019⁸ is not congruent to 1 mod p, 2019¹, 2019², and 2019⁴ also cannot be congruent to 1 mod p, or else we could just raise the congruence to a power on both sides to get  2019⁸ is congruent to 1 mod p. Therefore, 2019¹⁶ is the least power of 2019 that is congruent to 1 mod p, AKA ord_p(2019) = 16. 

It is a well-known fact that ord_p(a) divides p – 1, and the proof might be a little too long to get into here, but using this, we get that 16 divides p-1. Now, it is time to test out some primes.

The least prime that works is 17. Testing it out, we get 2019⁸ is congruent to (-4)⁸ mod 17, which is congruent to 16⁴ mod 17 or (-1)⁴ = 1. So 2019⁸ + 1 is congruent to 2 mod 17, which doesn’t work.

The next one that works is 97. Testing it out, 2019⁸ is congruent to (-18)⁸ . Since (-18)² is congruent to 33 mod 97, this is congruent to 33⁴ which is congruent to 22², or 484. 484 is congruent to -1 mod 97, so 2019⁸ + 1 is congruent to 0 mod 97, which works. Therefore, the smallest odd prime factor of 2019⁸ + 1 is 97. Welcome to WordPress! This is a sample post. Edit or delete it to take the first step in your blogging journey. To add more content here, click the small plus icon at the top left corner. There, you will find an existing selection of WordPress blocks and patterns, something to suit your every need for content creation. And don’t forget to check out the List View: click the icon a few spots to the right of the plus icon and you’ll get a tidy, easy-to-view list of the blocks and patterns in your post.