Read Microsoft Word - HW 09--Phi and pseudoprimes text version

Euler's Function

1) Factor 21 000 000 and use the factorization to find (21 000 000).

2) Calculate 1717 (mod 48). Calculate 3535 (mod 48)

3) Calculate 650650 (mod 240)

4) 137 is prime. What are the possibilities for a68 (mod 137)? Explain.

5) Verify that 25 is a base 7 pseudoprime. Do not use a calculator.

6) Verify that 2047 = 2389 is a base two pseudoprime. (Hint: try working mod 23 and mod 89, reassembling the results with the Chinese Remainder Theorem.)

7) Show that no multiple of 4 can be a base two pseudoprime. (There are even base two pseudoprimes, such as 161038, but they are extremely rare.)

8) Show that 561 = 31117 is a pseudoprime to every base. (Be careful about whether or not the base is relatively prime to 561.)

Information

Microsoft Word - HW 09--Phi and pseudoprimes

3 pages

Find more like this

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

25273