Using pseudoprimes, Carmichael's rule, and Miller's Test how would I go about solving Section 6.2 question 6
Extracted text: 6.2 Pseudoprimes 233 5. Show that if n is an odd composite integer and n is a pseudoprime to the base a, then n is a pseudoprime to the base n- a. 6. Show that if n= (a2P - 1)/(a² – 1), where a is an integer, a > 1, and p is an odd prime not dividing a (a – 1), then n is a pseudoprime to the base a. Conclude that there are infinitely many pseudoprimes to any base a. (Hint: To establish that a"-1 = 1 (mod n), show that 2p| (n-1), and demonstrate that a2P = 1 (mod n).) * | 7. Show that every composite Fermat number F, = 22" + 1 is a pseudoprime to the base 2. m 8. Show that if p is prime and 2P – 1 is composite, then 2P – 1 is a pseudoprime to the base 2. - - 9. Show that if n is a pseudoprime to the bases a and b, then n is also a pseudoprime to the base ab. 10. Suppose that a and n are relatively prime positive integers. Show that if n is a pseudoprime to the base a, then n is a pseudoprime to the base ā, where ā is an inverse of a modulo n. 11. Show that if n is a pseudoprime to the base a, but not a pseudoprime to the base b, where (a, n) = (b, n) = 1, then n is not a pseudoprime to the base ab. %3D 12. Show that 25 is a strong pseudoprime to the base 7. 13. Show that 1387 is a pseudoprime, but not a strong pseudoprime, to the base 2. 14. Show that 1,373,653 is a strong pseudoprime to both bases 2 and 3. 15/ Show that 25,326,001 is a strong pseudoprime to bases 2, 3, and 5. 16. Show that the following integers are Carmichael numbers. e) 278,545 = 5· 17 · 29 · 113 21 %3D