Chapter 3

Prove that if the cube of an integer is odd, then that integer is odd.

Prove that every prime number other than 2 and 3 has the form \(6 q+1\) or \(6 q+5\) for some integer \(q\). (Hint: this problem involves thinking about cases as well as contrapositives.)

Recall that a quadratic equation \(a x^{2}+b x+c=0\) has two real solutions if and only if the discriminant \(b^{2}-4 a c\) is positive. Prove that if \(a\) and \(c\) have different signs then the quadratic equation has two real solutions.

Prove that 129 is odd.

Prove that whenever a prime \(p\) does not divide the square of an integer, it also doesn't divide the original integer. \(\left(p \nmid x^{2} \Longrightarrow p \nmid x\right)\)

Show that the sum of any three consecutive integers is divisible by 3 .

The alternating sum of factorials provides an interesting example of a sequence of integers. $$ \begin{array}{c} 1 !=1 \\ 2 !-1 !=1 \\ 3 !-2 !+1 !=5 \\ 4 !-3 !+2 !-1 !=19 \end{array} $$ et cetera Are they all prime? (After the first two 1 's.)

Prove (by contradiction) that there is no largest integer.

Prove that the sum of two rational numbers is a rational number

There is a graph known as \(K_{4}\) that has 4 nodes and there is an edge between every pair of nodes. The pebbling number of \(K_{4}\) has to be at least 4 since it would be possible to put one pebble on each of 3 nodes and not be able to reach the remaining node using pebbling moves. Show that the pebbling number of \(K_{4}\) is actually \(4 .\)

Prove that for all integers \(a, b,\) and \(c,\) if \(a \mid b\) and \(a \mid(b+c),\) then \(a \mid c\).

Prove that the sum of an odd number and an even number is odd.

Prove (by contradiction) that there is no smallest positive real number.

Prove that if the sum of two integers is even, then so is their difference.

Show that if \(x\) is a positive real number, then \(x+\frac{1}{x} \geq 2\).

Prove (by contradiction) that the sum of a rational and an irrational number is irrational.

A vampire number is a \(2 n\) digit number \(v\) that factors as \(v=x y\) where \(x\) and \(y\) are \(n\) digit numbers and the digits of \(v\) are precisely the digits in \(x\) and \(y\) in some order. The numbers \(x\) and \(y\) are known as the "fangs" of \(v\). To eliminate trivial cases, both fangs can't end with \(0 .\) Show that there are no 2 -digit vampire numbers. Show that there are seven 4 -digit vampire numbers.

Prove that for all real numbers \(a, b,\) and \(c,\) if \(a c<0,\) then the quadratic equation \(a x^{2}+b x+c=0\) has two real solutions.

Prove (by contraposition) that for all integers \(x\) and \(y,\) if \(x+y\) is odd, then \(x \neq y\).

Lagrange's theorem on representation of integers as sums of squares says that every positive integer can be expressed as the sum of at most 4 squares. For example, \(79=7^{2}+5^{2}+2^{2}+1^{2} .\) Show (exhaustively) that 15 can not be represented using fewer than 4 squares.

Show that \(\left(\begin{array}{c}n \\ k\end{array}\right) \cdot\left(\begin{array}{c}k \\ r\end{array}\right)=\left(\begin{array}{c}n \\\ r\end{array}\right) \cdot\left(\begin{array}{c}n-r \\\ k-r\end{array}\right)\) (for all integers \(r, k\) and \(n\) with \(r \leq k \leq n)\).

Prove that if \(x\) is an odd integer, then \(x^{2}\) is of the form \(4 k+1\) for some integer \(k\).

Prove (by contraposition) that for all real numbers \(a\) and \(b\), if \(a b\) is irrational, then \(a\) is irrational or \(b\) is irrational.

In proving the product rule in Calculus using the definition of the derivative, we might start our proof with: $$\begin{array}{c} \frac{\mathrm{d}}{\mathrm{d} x}(f(x) \cdot g(x)) \\ =\lim _{h \longrightarrow 0} \frac{f(x+h) \cdot g(x+h)-f(x) \cdot g(x)}{h} \end{array}$$ The last two lines of our proof should be: $$\begin{array}{c} =\lim _{h \longrightarrow 0} \frac{f(x+h)-f(x)}{h} \cdot g(x)+f(x) \cdot \lim _{h \longrightarrow 0} \frac{g(x+h)-g(x)}{h} \\ =\frac{\mathrm{d}}{\mathrm{d} x}(f(x)) \cdot g(x)+f(x) \cdot \frac{\mathrm{d}}{\mathrm{d} x}(g(x)) \end{array}$$ Fill in the rest of the proof.

A Pythagorean triple is a set of three natural numbers, \(a, b\) and \(c,\) such that \(a^{2}+b^{2}=c^{2}\). Prove that, in a Pythagorean triple, at least one of \(a\) and \(b\) is even. Use either a proof by contradiction or a proof by contraposition.

The trichotomy property of the real numbers simply states that every real number is either positive or negative or zero. Trichotomy can be used to prove many statements by looking at the three cases that it guarantees. Develop a proof (by cases) that the square of any real number is non-negative.

True or false: Whenever an integer \(n\) is a divisor of the square of an integer, \(m^{2},\) it follows that \(n\) is a divisor of \(m\) as well. (In symbols, \(\left.\forall n \in \mathbb{Z}, \forall m \in \mathbb{Z}, n\left|m^{2} \Longrightarrow n\right| m .\right)\) Prove your answer.

Prove that \(\forall x \in \mathbb{R}, x \notin \mathbb{Z} \Longrightarrow\lfloor x\rfloor+\lfloor-x\rfloor=-1\).

In an exercise in Section 3.2 we proved that the quadratic equation \(a x^{2}+b x+c=0\) has two solutions if \(a c<0 .\) Find a counterexample which shows that this implication cannot be replaced with a biconditional.

Suppose that \(a, b\) and \(c\) are integers such that \(a \mid b\) and \(b \mid c .\) Prove that \(a \mid c\)

Suppose that \(a, b, c\) and \(d\) are integers with \(a \neq c .\) Further, suppose that \(x\) is a real number satisfying the equation $$ \frac{a x+b}{c x+d}=1 $$ Show that \(x\) is rational. Where is the hypothesis \(a \neq c\) used?

Show that if two positive integers \(a\) and \(b\) satisfy \(a \mid b\) and \(b \mid a\) then they are equal.