Please help with these questions. Thanks in advance!!!!

 

 

Homework 3
Math 467 Due: 9 September, 2016 1.
a) Show that if a, b ∈ N have remainders in the set {1, 4} after division by
5, then so does their product.
b) Show that there are infinitely many primes which have remainders 2 or
3 when divided by 5.
Hint: Imitate the proof of Euclid’s Theorem by forming a product involving
primes (each with remainder 1 or 4) and possibly something else so that when
we add, say, 2, we obtain a number N with remainder 2 after division by 5.
Then apply part a).
n 2. Set Fn denote the nth Fermat number Fn = 22 + 1.
a) Show that if m < n, then Fm divides Fn − 2.
b) Deduce once more that there exist infinitely many primes.
Hint: We have seen in class that bk + 1 | b2k − 1 and that, when k | l,
bk − 1 | bl − 1.
3. Implement our Algorithm 5, the Sieve of Eratosthenes, and find all the
primes between 1600 and 3600.
How many pairs of primes differ by 2?
4. Prove by a careful induction that if r ∈ N, then
r 2 r−1 b2 − 1 = (b − 1)(b + 1)(b2 + 1)(b2 + 1) · · · (b2 + 1). You may use either the Well-Ordering Principle or standard Mathematical
Induction.
5. Let a ≡ r mod m and b ≡ s mod m. Prove the following:
(a) a + b ≡ r + s mod m.
(b) ab ≡ rs mod m.
(c) Generalize the proof of Euclid’s Lemma to show that if gcd(a, m) = 1
and ac ≡ 0 mod m, then c ≡ 0 mod m.
(d) Conclude that if gcd(a, m) = 1 and ab ≡ ac mod m, then b ≡ c
mod m.

Attachments:

• 1492650529-hw03.pdf