Question

How do i prove that 1,000,009 is NOT a prime number in the Simpliest way possible? pleasee help

Answer 1

and please show all work

Answer 2

Divide it by the prime numbers until you find one that is a factor.

Answer 3

All primes except 2 can be written in the form 4k+1 or 4k+3. If you divide 1000009 by 4, you see that it belongs to the 4k+1 family because the remainder is 1. So since it belongs to this family, it can be written as the sum of two squares in two ways: 1000^2 +3^2 and 972^2 + 235^2 . Therefore according to Euler, it is composite.