1. How many integers between 1 and 10000, inclusive, are divisible by at least one of 2, 3, 5, or 7? 2. We encountered the totient function Suppose m ∈ Z≥1 evenly divides n. Define M := {k ∈ {1, . . ....

1. How many integers between 1 and 10000, inclusive, are divisible by at least one of 2, 3, 5, or 7?

2. We encountered the totient function

Suppose m ∈ Z≥1 evenly divides n. Define M := {k ∈ {1, . . . , n} : m | k}. Argue that |M| = n m .

3. (A number-theoretic interlude.) Let the prime factorization of n be n = p e1 1 · p e2 2 · p eℓ ℓ , for distinct prime numbers {p1, . . . , pℓ} and integers e1, . . . ,eℓ ≥ 1. Let k ≤ n be arbitrary. Argue that k and n have no common divisors greater than 1 if and only if, for all i, we have pi 6 | k.