Problem:
Find the least odd prime factor of 20198+1.
Solution:
Suppose prime p>2 divides 20198+1. Then 20198β‘β1(modp). Squaring gives 201916β‘1(modp). If 2019mβ‘1(modp) for some 0<m<16, it follows that
2019gcd(m,16)β‘1(modp)
But 20198β‘β1(modp), so gcd(m,16) cannot divide 8 , which is a contradiction. Thus 201916 is the least positive power of 2019 congruent to 1 (modp). By Fermat's Little Theorem, 2019pβ1β‘1(modp). It follows that p=16k+1 for some positive integer k. The least two primes of this form are 17 and 97 . The least odd prime factor of 20198+1 is not 17 because
2019β‘13(mod17) and 132β‘169β‘β1(mod17)
which implies 20198β‘1ξ β‘β1(mod17). But 2019β‘β18(mod97), so
(β18)2=324332=1089222=484ββ‘33(mod97),β‘22(mod97), and β‘β1(mod97)β
Thus the least odd prime factor is 97 .
In fact, 20198+1=2β
97β
p, where p is the 25 -digit prime
1423275002072658812388593.
The problems on this page are the property of the MAA's American Mathematics Competitions