## Description

Math 422: Introduction to Number Theory

Homework on 10–11

A. Write a program that takes as input a positive integer n and computes ϕ(n).

You may use brute force.

B. Compute

1. ϕ(81)

2. ϕ(20736)

3. ϕ(10000000000)

C. 1. Find all n for which ϕ(n) = 4.

2. Find all n for which ϕ(n) = 6.

D. Silverman 11.5.

E. Silverman 11.8. You may not use brute force.

F. Silverman 11.9.

G. Show that if gcd(m, n) > 1, then

ψ : Z/mn → Z/m × Z/n

[x] 7→ ([x], [x])

is never bijective.

1 of 1