Show the following number 𝑁 is either possibly prime or definitely composite using the two parts of the Fermat Primality test.

Question

𝑁 = 19

Answer 1

The primality test is to select a value a relatively prime to N and not equal to 1 or N-1 and see if a ^ N-1 ≡ 1 (mod N)

We choose a = 2.

Let's calculate (2^6)^3 mod (19)

2^6 = 64, and 64 ≡ 7 (mod 19) (3 * 19 + 7 = 64)

7^3 = 343 and 343 ≡ 1 (mod 19) (19 * 18 + 1 = 343)

Thus, 2 ^ 18 ≡ 1 (mod 19), and 19 is a possible prime.