1.
Let \(n\) represent an integer with \(n \ge 2\text{.}\) Prove that \(n\) is prime if and only if \(n/m\) is not an integer for every integer \(m\) with \(2 \le m \lt \frac{n}{2}\text{.}\)
Exercises 6.12 Exercises
2.
Let \(n\) represent an integer with \(n \ge 2\text{.}\) Suppose \(p_1,p_2,\dotsc,p_\ell\) is a complete list of prime numbers which are less than or equal to \(n/2\text{.}\) Prove that \(n\) is prime if and only if none of the \(p_i\) divide \(n\text{.}\) Careful: Is the statement actually true in the case \(n=2\text{?}\) \(n=3\text{?}\) (Why should these cases be given special consideration?)
3.
Call two people twins if they share the same mother and the same birthdate. Consider the statement: “if two people are twins, then they share the same birthdate.”
(a)
Is the statement true?
(b)
What is the converse of this statement? Is it true?
4.
Prove directly: The sum of two rational numbers is a rational number.
5.
Prove directly: If \(n\) is even, then \(n^2\) is divisible by \(4\text{.}\)
6.
Recall that the triangle inequality states that \(\abs{x+y} \le \abs{x} + \abs{y}\) for all numbers \(x\) and \(y\text{.}\)
Use the triangle inequality to prove directly: \(\abs{x+y+z} \le \abs{x} + \abs{y} + \abs{z}\) for all numbers \(x,y,z\text{.}\)
7.
Prove by reduction to cases: \(n^3 - n\) is always divisible by \(3\text{.}\)
Hint.
Use cases \(n = 3m, 3m+1, 3m+2\text{.}\)
8.
Prove by proving the contrapositive: if \(2^n - 1\) is prime, then \(n\) is prime.
Hint.
You may find the following “difference of powers” factorization formula useful:
\begin{equation*}
x^m - y^m = (x-y)(x^{m-1} + x^{m-2}y + x^{m-3}y^2 + \dotsb + x^2y^{m-3} + x y^{m-2} + y^{m-1}).
\end{equation*}
9.
Prove by counterexample that the following statement is false.
The sum of any two irrational numbers is irrational.
(See Exercise 6.12.4.)
10.
Prove the biconditional: \(n\) is even if and only if \(n^2\) is divisible by \(4\text{.}\)
(See Exercise 6.12.5.)
11.
Prove by contradiction: If \(m\) and \(n\) are integers such that \(11m + 19n\) is odd, then either \(m\) or \(n\) (or both) must be odd.
12.
Prove by contradiction: For \(x,y>0\text{,}\) \(\sqrt{x+y} \ne \sqrt{x} + \sqrt{y}\text{.}\)
13.
Prove by contradiction: The sum of a rational number and an irrational number is irrational.
(See Exercise 6.12.4 and Exercise 6.12.9.)
14.
Prove that if \(\ell\text{,}\) \(m\text{,}\) and \(n\) are integers such that \(\ell\) divides \(m\) and \(\ell\) divides \(n\text{,}\) then \(\ell\) divides \(mn\text{.}\)
15.
Prove that if \(\ell\text{,}\) \(m\text{,}\) and \(n\) are integers such that \(mn\) divides \(\ell\text{,}\) then both \(m\) and \(n\) divide \(\ell\text{.}\)
16.
Suppose that \(m\) and \(n\) are integers, and \(p\) is a prime number. Prove that if \(p\) does not divide the product \(mn\text{,}\) then \(p\) cannot divide either of \(m\) or \(n\text{.}\)
Working with a definition.
Exercises 17–19 concern the following definitions.
A square number is an integer which is equal to the square of some integer. An integer is square free if it is not divisible by any square number other than \(1\text{.}\)
17.
For each of the following, provide a proof to justify your answer.
(a)
Is \(0\) a square number? Is it square free?
(b)
Does there exist a negative square number?
(c)
Is every negative number square free?
(d)
Is every prime number square free?
(e)
Is every square free number prime?
(f)
Does there exist an integer which is both a square number and square free?
18.
Prove that a positive number \(n\) is square free if and only if for every factorization \(n = ab\text{,}\) the integers \(a\) and \(b\) do not share a common factor other than \(1\text{.}\)
19.
Prove that a positive number is square free if and only if it is not divisible by the square of a prime number.
20.
A pair of prime numbers \(p_1,p_2\) is called a twin prime pair if \(p_2 = p_1 + 2\text{.}\) A prime number is called an isolated prime if it is not part of a twin prime pair.
(a)
Determine the first (i.e. smallest) four twin prime pairs.
(b)
Determine the first (i.e. smallest) two isolated primes.
(c)
Prove that if \(p, p+2\) is a twin prime pair with \(p \ge 5\text{,}\) then \(p+1\) is divisible by \(6\text{.}\)
(d)
Prove that if \(p, p+2\) is a twin prime pair, then \(p-2,p\) and \(p+2,p+4\) cannot be twin prime pairs.
