Factorise the following integers:
(a) $18^2 + 1 = 325$
(b) $30^2 + 1 = 901$
(c) $53^2 + 1 = 2810$
(d) $60^2 + 1 = 3601$
(e) $24^2 + 1 = 577$
(f) $104^2 + 1 = 10 817$
(g) $302^2 + 1 = 91 205$
(h) $1014^2 + 1 = 1 028 197$
We use the fact that odd prime factors $p$ of an integer of the form $x^2 +1$ satisfy $p \equiv 1 \pmod 4$. The first of these are
$$ 5 , 13 , 17, 29 , 37 , 41 , 53 , 61 , 73 , 89 , \ldots$$
(a) We try prime factor 5.
$ 325 = 5^2 \times 13 $
(b) We try factors 13 and 17.
$ 901 = 17 \times 53 $
(c) We try factor 5 which leads to an even number, leaving 281 as prime.
$ 2810 = 5 \times 2 \times 281 $
(d) We try factor 13.
$ 3601 = 13 \times 277 $
(e) Trying all the primes up to $\lfloor \sqrt{577} \rfloor=24$ tells us 577 is prime.
(f) We try factor 29.
$ 10817 = 29 \times 373 $
Trying all the primes up to $ \lfloor \sqrt{373} \rfloor = 19$ tells us 373 is prime.
(g) We try factors 5, 17, 29, 37.
$ 91205 = 5 \times 17 \times 29 \times 37 $
(h) We try factor 109.
$ 1028197 = 109 \times 9433 $
Trying primes up to $ \lfloor \sqrt{9433} \rfloor = 97 $ tells us 9433 is prime.