Problem 5 (Pseudoprimes and Carmichael Numbers!). We have seen that an integer n is prime when it is not divisible by any prime p with p n. Unfortunately, using this criterion to show that a given integer is prime is inefficient. We can use the converse of Fermat's Little Theorem (with p = 2) to obtain an alternative primality test. Fermat Primality Test (p = 2): Let n> 1 be an odd integer. If 2-1 # 1 (modn), then n is composite. Notice - this gives us a way to determine if a number is composite without knowing a single factor of n - Neat! a. Using the Fermat Primality Test along with the Modular Exponentiation Algorithm, either your own (Activ- ity/Project 4) or the built in Sage Algorithm, show the following numbers are composite. i. Jenny x (Jenny + 2) = 75261003596099 ii. Jenny x Devil's Prime 8675309000000577775579400000008675309 iii. RSA 100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 iv. RSA 230 = 1796949159794106673291612844957324615636756180801260007088891883553172646034149093349337224786865075523085586419992 9221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689 RSA 230 has 230 decimal digits (762 bits) and was (recently) factored on August 15, 2018. See RSA Numbers/RSA Factoring Challenge. b. Unfortunately, there are composite integers n such that 2"-1 = 1 (mod n). Such integers are called 2- pseudoprimes. i. Show that n = 341 is a 2-pseudoprime. That is, show that 341 is composite (not prime) and 2841-1 = 1 (mod 341). ii. There are seven 2-pseudoprimes less than 2000. Find them. (341 is the smallest pseudoprime.) Hint: Start with non-prime numbers and test if 2-1 = 1(mod n) iii. Determine the number of 2-pseudoprimes that do not exceed 10000. c. A natural question now arises, if n is composite, is there some b such that b1 #1(mod n)? The easy answer is 'yes' since we can take b to be a prime divisor of n and then bis 0 modulo n (i.e., it is not 1). However, if we know ged(n, b) # 1, then we know a factor of n! We are primarily worried about whether we can pick a few values of b with the hope of finding one that will fail the Fermat Test. Definition 2. A composite n> 1 is called a Carmichael number if b-1 = 1 (mod n) for all integers b with god(b, n) = 1. i. Show that 561 = 3-11-17 is a Carmichael number. We see that 561 is composite so it remains to show that 6561-1 = 1(mod 561) for all integers b with gcd (561, b) = 1. ii. Show that 1729 7 13 19 is a Carmichael number iii. Write and implement a program with input n that returns True if n is a Carmichael number and False if n is prime or not a Carmichael number. iv. List and count the number of Carmichael numbers up to 10000. Count the number of Carmichael numbers up to 1000000. Count the number of Carmichael numbers up to 10.