Show that the following numbers with given prime factorizati

Show that the following numbers, with given prime factorizations, are pseudoprimes (i.e., pass the base 2 test).

561 = 3 · 11 · 17

Solution

First we look at N= 561 = 3.11.17

We can find that

a⁵⁶⁰ 1 mod 561

for any a with gcd(a, N) = 1.

Such a number is known a \"Carmichael Number\". We see that 561 is a Carmichael number, because we first observe 560 = 2.260 = 10.56 = 16.35

Again it is implied from Fermat’s Little Theorem that

a⁵⁶⁰1 mod 3

a⁵⁶⁰1 mod 11

a⁵⁶⁰1 mod 17

For each of the integer that is coprime to 561 = 3·11·17. The result is now obtained by the Chinese Remainder Theorem.