1. Consider the veracity or falsehood of each of the
fol lowing statements , and argue for those that you believe are true while
providing a counterexample for those that you believe are false.
• φ(n) is even for all . n ≥ 3.
• There are 3- digit numbers that no matter how we permute those digits, the
number is prime .
• There are as many primes between 100,000 and 200,000 as between 200,000 and
300,000.
• Of the odd primes less than 100, half of them are 1 mod 4 and half of them
are 3 mod 4.
• There exist 3 consecutive integers each divisible by a perfect square other
than 1.
2. Given |a|m=20, find |a4|m, |a6|m, |a11|m and |a15|m.
3. On Pseudoprimes. We saw that 561 satisfied the
conclusion of Fermat’s Little Theorem without being prime, namely a561 ≡
a mod 561
for any a. For an arbitrary modulus m, letX(m) = {x > 0 | ax ≡ a mod m for
every a} A number
m is called a pseudoprime if m ∈Ε(m).
• Give 4 elements of X(5), namely find 4 positive integers x such that ax ≡
a mod 5
for every a. Hint: This is very easy.
• Prove p ∈X(p) if p is prime. Hint: This is also very easy.
• Prove that if x, y ∈X(m), then xy ∈X(m). Hint: Still very easy.
• Prove that if x,y,z ∈X(m), then for any j = 0,1,…,z, we have jx + (z - j)y ∈X(m).
Hint: Be careful with negative exponents .
• Prove that if
, and if
for each i,
then x ∈X(m).
• Factor 1729 and use • to prove that 1729 is a pseudoprime. Observe of course
it is not a prime.
4. For a positive integer n, define a(n) to be the number
of ways of writing n as a sum of consecutive integers. E.g., a(9) = 3 since 9 =
2 + 3 + 4, 9 = 4 + 5, and . 9 = 9.
• Compute a(n) for n = 2,…,10.
• Show that a(n) is the number of odd divisors of n.
• Compute α(8), α(125) and α(1000).
• Also compute a(10) and a(100).
5. Assume that p=16035002279 is a prime (which it is), and
that q=32070004559 divides 2p - 1 (which it does). Prove that q is a prime.
