time is the most important

For this homework assignment, you may write your answers however you like (

b

y hand,typed, whatever). Subsequent assignments will be submitted in LATEX but I haven’t shownyou how to use that yet!

b Name:

Math 235

Homework 2

Due Friday, September 11 2020, 12:20 PM

For this homework assignment, you may write your answers however you like (by hand,

typed, whatever). Subsequent assignments will be submitted in LATEX but I haven’t shown

you how to use that yet!

3.2 Find the prime factorization of the following numbers:

(a) 856

(b) 2323

(c) (28 − 1)20

3.5 Let a and b be integers, and let p be a prime. Answer true or false and explain:

(a) If p | a11 , then p | a.

(b) If p | a and p | (a2 + b2 ), then p | b.

(c) If p | (a9 + a17 ), then p | a.

3.7 A Mersenne prime is any prime number of the form 2p − 1, where p is itself a prime

number. For example, 7 is a Mersenne prime, because 7 = 23 −1, as is 31 = 25 −1. These

numbers are named after Father Marin Mersenne (1588 1648), who was apparently

very interested in numbers of the form 2n − 1.

(a) Use high-school algebra to show that 215 − 1 is not prime.

(b) Show that if 2n − 1 is prime, then n itself must be prime.

(c) Show by example that if p is prime, then 2p − 1 may be composite. You may

Google this one.

(d) Are there innitely many Mersenne primes? Nobody knows! This is a famous

open question. As of this writing, the largest known prime number is a Mersenne

prime. What is it? Again, Google is OK.

3.9 Imagine a hallway with 100 light switches each connected to an overhead lamp. Initially, all the lamps are o. Then, 100 people walk down the hall. The rst person

ips every switch. The second person ips every second switch (the second, the fourth,

etc.). The third person ips every third switch (the third, the sixth, etc.). This continues until all 100 people have walked down the hall. At the end of all this weirdness,

which lights are on?

3.10 The sieve of Eratosthenes is an ancient algorithm for nding prime numbers. Start

by listing all the numbers from 2 up to 100 (a 10 × 10 grid works nicely). Circle 2,

then cross out every second number after 2 (so cross out 4, 6, etc.). Then circle 3 and

cross out every third number after 3. Some of these numbers will already be crossed

out; that’s ne. Next circle 5 and cross out every fth number after 5. And nally,

circle 7 and cross out every seventh number after 7. At this point, any number that

hasn’t been crossed out is prime, so we’ve found all the primes less than 100.

(a) Why does this work? In particular, after crossing out the multiples of 2, 3, 5, and

7, how do you know all the remaining numbers are prime?

(b) If we wanted to nd all primes up to, say, 200, would it suce to cross out only

the multiples of 2, 3, 5, and 7? Explain.