Elementary Foundations: An introduction to topics in discrete mathematics

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<\frac{n}{2}\text{.}$

Let $n$ represent an integer with $n\ge 2\text{.}$ Suppose $p_1,p_2,\dots ,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?)

Prove directly: The sum of two rational numbers is a rational number.

Prove directly: If $n$ is even, then $n^2$ is divisible by $4\text{.}$

Recall that the triangle inequality states that $|x+y|\le \left|x\right|+\left|y\right|$ for all numbers $x$ and $y\text{.}$

Use the triangle inequality to prove directly: $|x+y+z|\le \left|x\right|+\left|y\right|+\left|z\right|$ for all numbers $x,y,z\text{.}$

Prove by reduction to cases: $n^3-n$ is always divisible by $3\text{.}$

Prove by proving the contrapositive: if $2^n-1$ is prime, then $n$ is prime.

Prove by counterexample that the following statement is false.

(See Exercise 6.12.4.)

Prove the biconditional: $n$ is even if and only if $n^2$ is divisible by $4\text{.}$

(See Exercise 6.12.5.)

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.

Prove by contradiction: For $x,y>0\text{,}$ $\sqrt{x+y}\ne \sqrt{x}+\sqrt{y}\text{.}$

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.)

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{.}$

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{.}$

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{.}$