---
tags: mth350, homework
---

# MTH 350 Homework 4

Instructions for this Homework set are on Blackboard where this is posted. The due date is on the class calendar, which is linked on Blackboard.

## Problem 1

:::warning
This problem is an **independent** problem. As described in [the Syllabus](https://docs.google.com/document/d/1Rest_DodWnDy7Y8EVhp2lEOVnWcTEjLAGfWV2khuQQY/edit?usp=sharing) (top of page 14) this means that **on this problem, the only help you can get is from the professor.**
:::

This one has two parts:
1. Consider the list of prime numbers $2, 3, 5, 7, 11, \dots$ and let $p_i$ denote the $i$th prime in the list. So $p_1 = 2$, $p_2= 3$, $p_3 = 5$, and so on. **Prove or disprove:** for all $n \in \mathbb{N}$, the number $(p_1p_2p_3\cdots p_n) + 1$ is also a prime number.
2. **Prove** that there are infinitely many prime numbers.

Notes on this:
- Make sure you understand part 1 by first calcuating several examples of $(p_1p_2p_3\cdots p_n) + 1$ with a calculator or computer. This will also help you search for counterexamples, if there are any.
- [Here's a list of all the primes less than 10000](https://www.mathsisfun.com/numbers/prime-numbers-to-10k.html). If you need larger primes, you can Google them, or go to Wolfram|Alpha and enter in `Prime[n]` to get the $n$th prime number. [Here's an example](https://www.wolframalpha.com/input?i=Prime%5B100000%5D). Note the square brackets around the `n`.
- For the second part: Proving that a set or list is infinite often works by contradiction. Assume the list is finite, so in this case there are only $n$ primes: $p_1, p_2, \cdots, p_n$. Now look at $(p_1p_2p_3\cdots p_n) + 1$ from part 1. Prove that this number is neither prime, nor is it a product of primes. Remember you are operating under the assumption that there are no other prime numbers besides $p_1, p_2, \cdots, p_n$.

## Problem 2

:::success
This problem is a **collaborative** problem. This means that **you can work on it in a small group, as long as you stay within the bounds of academic honesty** laid out in [the Syllabus](https://docs.google.com/document/d/1Rest_DodWnDy7Y8EVhp2lEOVnWcTEjLAGfWV2khuQQY/edit?usp=sharing) (starting on page 13).
:::

**Choose exactly one of the following statements** and write a complete, correct, and clear proof.

You can (and should) test-drive each of these problems in your notes to see which one feels best for you, but please only turn in work on one of these (in addition to Problem 1).

1. Prove that for every $y \in \mathbb{N}$, there exists an odd integer $n$ and a nonnegative integer $k$ such that $y = 2^kn$. (For example: $100 = 2^2 \cdot 25$, and $32 = 2^5 \cdot 1$.) In other words, we can write every natural number as an odd number times a power of $2$.
2. Prove that if $n > 1$ is composite, then $n$ has a prime factor $p$ that is less than or equal to $\sqrt{n}$. (Theorem A.4 tells us the prime factor exists; what you're proving is the size limit on the factor.)

**Additional options for Problem 2 may be added through Tuesday, depending on class activities.**

## Submission instructions

You are turning in two items:

1. Both parts of Problem 1.
2. Your choice of proof in Problem 2.

Remember to type up your work using $\LaTeX$, and create a single PDF document with each problem on a separate page. (Use the command `\pagebreak` to start a new page.)

Then upload your PDF to the "Homework 4" assignment area, and remember to hit **Submit**.