Lakehead University Prime Factorization Discrete Math Worksheet 2

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.