a. A Mersenne prime is a prime number of the form 2" 1 where p is itself prime. (Note that these are the only possible primes of the form 2-1 where n is a positive integer.) They are called this because Marin Mersenne was the first person to list these primes systematically: he clalmed that for p 257, 2P - 1 s prime If and only if pe 12,3,5,7,13, 17,19,31,67,127,257 This list turns out to be incorrect; write Sage code to compute the correct list. In [ ] : |# your code goes here 232017-1 3b. On January 3, 2018, the Great Intemet Mersenne Prime Search announced that 2 3c. Fermat's itle theorem states that if p is prime, then 21 (mod p). This can be used as a test for primality (the Fermat test) which has no false negatives, but does have some false positives (see part () Explain why the following code cannot be used to apply the Fermat test to the number p 221701 1, then give an alternate approach that does work. 1 is the "50th known Mersenne prime". Why didn't they announce that it is the "50th Mersenne prime"? In [ ] : |p-2^21101-1 print (2" (p-1) % p) # This won't work! 3d. Find all integers up to 2000 which are false positives for the Fermat test. These include Carmichael numbers, in case you want to read more about this phenomenon. in [ ]:|# your code goes here a. A Mersenne prime is a prime number of the form 2" 1 where p is itself prime. (Note that these are the only possible primes of the form 2-1 where n is a positive integer.) They are called this because Marin Mersenne was the first person to list these primes systematically: he clalmed that for p 257, 2P - 1 s prime If and only if pe 12,3,5,7,13, 17,19,31,67,127,257 This list turns out to be incorrect; write Sage code to compute the correct list. In [ ] : |# your code goes here 232017-1 3b. On January 3, 2018, the Great Intemet Mersenne Prime Search announced that 2 3c. Fermat's itle theorem states that if p is prime, then 21 (mod p). This can be used as a test for primality (the Fermat test) which has no false negatives, but does have some false positives (see part () Explain why the following code cannot be used to apply the Fermat test to the number p 221701 1, then give an alternate approach that does work. 1 is the "50th known Mersenne prime". Why didn't they announce that it is the "50th Mersenne prime"? In [ ] : |p-2^21101-1 print (2" (p-1) % p) # This won't work! 3d. Find all integers up to 2000 which are false positives for the Fermat test. These include Carmichael numbers, in case you want to read more about this phenomenon. in [ ]:|# your code goes here
