Hints, Solutions and Help -- a companion to GIAM

Chapter 3 -- Proof techniques I --- Standard methods

Section 3.1 -- Direct proofs of universal statements

  1. Every prime number greater than 3 is of one of the two forms 6k+1 or 6k+5. What statement(s) could be used as hypotheses in proving this theorem?
    Fill in the blanks:
    • p is a _________ number, and
    • p is greater than _______.
  2. Prove that the sum of two rational numbers is a rational number.
    You want to argue about the sum of two generic rational numbers. Maybe call them a/b and c/d. The definition of "rational number" then tells you that a, b, c and d are integers and that neither b nor d are zero. You add these generic rational numbers in the usual way -- put them over a common denominator and then add the numerators. A common denominator is bd, so we can express the sum as (ad+bc)/(bd). You can finish off the argument from here: you need to show that this expression for the sum satisfies the definition of a rational number (quotient of integers w/ non-zero denominator). Also, write it all up a bit more formally...
  3. Prove that if the sum of two integers is even, then so is their difference.
    Hint: If we write x+y for the sum of two integers that is even (so x+y = 2k for some integer k), then we could subtract ____________ from it in order to obtain x-y. Once you fill in that blank properly the flow of the argument should become apparent to you.
  4. Prove that if x is an odd integer, then x2 is of the form 4k+1.
    You may be tempted to write "Since x is odd, it can be expressed as x = 2k+1 where k is an integer." This is slightly wrong since the variable k is already being used in the statement of the theorem. But, except for replacing k with some other variable (maybe m?) that is a good way to get started. From there it's really just algebra until, eventually, you'll find out what k really is...
  5. Define the evenness of an integer n by:

    evenness (n) = k    ⇔    2k | n   ∧   2k+1 | n

    State and prove a theorem concerning the evenness of products.

    Well, the statement is that the evenness of a product is the sum of the evennesses of the factors...

  6. Suppose that a, b and c are integers such that a | b and b | c. Prove that a | c.
    This one is pretty straightforward. Be sure to not reuse any variables. Particularly, the fact that a | b tells us (because of the definition of divisibility) that there is an integer k such that b = ak. It is not okay to also use k when converting the statement "b | c."

  7. Suppose that a, b, c and d are integers with a ≠ c. Further, suppose that x is a real number satisfying the equation

    (ax+b)/(cx+d) = 1.

    Show that x is rational. Where is the hypothesis a ≠ c used?

    Cross multiply and solve for x. If you need to divide by an expression, it had better be non-zero!

  8. Show that if two positive integers a and b satisfy a | b and b | a then they are equal.

    From the definition of divisibility, you get two integers j and k, such that a = jb and b = ka. Substitute one of those into the other and ask yourself what the resulting equation says about j and k. Can they be any old integers? Or, are there restrictions on their values?



Section 3.2 -- More direct proofs

  1. Suppose you have a savings account which bears interest compounded monthly. The July statement shows a balance of $2104.87 and the September statement shows a balance $2125.97. What would be the balance on the (missing) August statement?

    A savings account where we are not depositing or withdrawing funds has a balance that is growing geometrically.
  2. Recall that a quadratic equation ax2+bx+c=0 has two real solutions if and only if the discriminant b2-4ac is positive. Prove that if a and b have the same sign and c has a different sign (from a and b), then the quadratic equation has (two) real solutions.

    You don't need all the hypotheses. If a and c have different signs, then ac is a negative quantity.
  3. Prove that if x3-x2 is negative then 3x+4 < 7.

    This follows very easily by the method of working backwards from the conclusion. Remember that when multiplying or dividing both sides of an inequality by some number, the direction of the inequality may reverse (unless we know the number involved is positive). Also, remember that we can't divide by zero, so if we are (just for example, don't know why I'm mentioning it really...) dividing both sides of an inequality by x2 then we must treat the case where x=0 separately.
  4. Show that if x is a positive real number, then x+1/x ≥ 2.

    If you work backwards from the conclusion on this one, you should eventually come to the inequality (x-1)2 ≥ 0 . Notice that this inequality is always true -- all squares are non-negative. When you go to write-up your proof (writing things in the forward direction), you'll want to acknowledge this truth. Start with something like "Regardless of the value of x, the quantity (x-1)2 is greater than or equal to zero as it is a perfect square."



Section 3.3 -- Indirect proofs: contradiction and contraposition

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

    The best hint for this problem is simply to write down the contrapositive statement. It is trivial to prove!
  2. Prove that whenever a prime p does not divide the square of an integer, it also doesn't divide the original integer. (p doesn't divide x2    ⇒    p doesn't divide x)

    The contrapositive is (p|x) ⇒ (p|x2).
  3. Prove (by contradiction) that there is no largest integer.

    Well, if there was a largest integer -- let's call it L (for largest) -- then isn't L+1 an integer, and isn't it bigger?
  4. Prove (by contradiction) that there is no smallest positive real number.

    Assume there was a smallest positive real number -- might as well call it s (for smallest) -- what can we do to produce an even smaller number? (But be careful that it needs to remain positive -- for instance s-1 won't work.)
  5. Prove (by contradiction) that the sum of a rational and an irrational number is irrational.

    Suppose that x is rational and y is irrational and there sum (let's call it z) is also rational. Do some algebra to solve for y, and you will see that y (which is, by presumption, irrational) is also the difference of two rational numbers (and hence, rational -- a contradiction.)
  6. A Pythagorean triple is a set of three natural numbers, a, b and c, such that a2 + b2 = c2. 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.

    Hint: this result depends on knowing how squares behave mod 4. Odd squares are 1 mod 4. The sum of two odd squares is 2 mod 4 -- but even squares are 0 mod 4.



Section 3.4 -- Disproofs of universal statements

  1. Find a polynomial that assumes only prime values for a reasonably large range of inputs.

    It sort of depends on what is meant by "a reasonably large range of inputs." For example the polynomial p(x) = 2x+1 gives primes three times in a row (at x=1,2 and 3).
  2. Find a counterexample to Conjecture 3 using only powers of 2.

    The intent of the problem is that you find three numbers, a, b and c, that are all powers of 2 and such that a divides the product bc, but neither of the factors separately. For instance, if you pick a=16, then you would need to choose b and c so that 16 doesn't divide evenly into them (they would need to be less than 16...) but so that their product is divisible by 16.
  3. The alternating sum of factorials provides an interesting example of a sequence of integers.

    1! = 1

    2! - 1! = 1

    3! - 2! + 1! = 5

    4! - 3! + 2! - 1! = 19

    et cetera

    Are they all prime? (After the first two 1's.)

    Here's some Maple code that would test this conjecture:

    for i from 2 to 8 do
        n := i! - n;
    end do;

    Of course it turns out that going out to 8 isn't quite far enough...

  4. It has been conjectured that whenever p is prime, 2p - 1 is also prime. Find a minimal counterexample.

    I would definitely seek help at your friendly neighborhood CAS.

  5. True or false: The sum of any two irrational numbers is irrational. Prove your answer.

    Hint: Both √(2) and -√(2) are irrational numbers

  6. True of false: There are two irrational numbers whose sum is rational. Prove your answer.

    See previous.

  7. True or false: The product of any two irrational numbers is irrational. Prove your answer.

    Is the inverse, 1/x, of an irrational number x rational?

  8. True or false: There are two irrational numbers whose product is rational. Prove your answer.

    See previous.

  9. True or false: Whenever an integer n is a divisor of the square of an integer, m2, it follows that n is a divisor of m as well. (In symbols, ∀ n ∈ Z, ∀ m ∈ Z, n | m2    ⇒    n | m.) Prove your answer.

    Hint: List all of the divisors of 36 = (2⋅3)2. See if any of them are bigger than 6.



Section 3.5 -- Even more direct proofs: By cases and By exhaustion

  1. Prove that if n is an odd number then n4 (mod 16) = 1.

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

    It is probably obvious that the "cases" will be the possible remainders mod 6. Numbers of the form 6q+0 will be multiples of 6, so clearly not prime. The other forms that need to be eliminated are 6q+2, 6q+3, and 6q+4.

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

    The sum is n + (n+1) + (n+2).

  4. A vampire number is a 2n digit number v that factors as v=xy where x and y are n digit numbers and the digits of v are the union of 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, pairs of trailing zeros are disallowed.

    Show that there are no 2-digit vampire numbers.

    Show that there are seven 4-digit vampire numbers.

  5. 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 = 72 + 52 + 22 + 12. Show (exhaustively) that 15 can not be represented using fewer than 4 squares.
    Note that 15 = 32 + 22 + 12 + 12. Also, if 15 were expressible as a sum of fewer than 4 squares, the squares involved would be 1, 4 and 9. It's really not that hard to try all the possibilities.

  6. Show that there are exactly 17 numbers x in the range 1 ≤ x ≤ 100 that can't be represented using fewer than 4 squares.

    You should really enlist a CAS (unless you're feeling masochistic...)

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

    By trichotomy, x is either zero, negative, or positive. If x is zero, its square is zero. If x is negative, its square is positive. If x is positive, its square is also positive.



Section 3.6 -- Proofs and disproofs of existential statements

  1. Show that there is a perfect square that is the sum of two perfect squares.

    Can you say "Pythagorean triple"? I thought you could.
  2. Show that there is a perfect cube that is the sum of three perfect cubes.

    Hint: 63 can be expressed as such a sum.
  3. Show that the WOP doesn't hold in the integers. (This is an existence proof, you show that there is a subset of Z that doesn't have a smallest element.)

    How about even integers? Is there a smallest one?
  4. Show that the WOP doesn't hold in Q+.

    Consider the set {1, 1/2, 1/4, 1/8, ...}. Does it have a smallest element?
  5. In the proof of Theorem 3.6.4 we weaseled out of showing that d | b. Fill in that part of the proof.

    Still weaseling...
  6. Give a proof of the unique existence of q and r in the division algorithm.

    Unique existence proofs consist of two parts. First, just show existence. Then, show that if there were two of the things under consideration they must be equal.
  7. A digraph is a drawing containing a collection of points that are connected by arrows. The game known as scissors-paper-rock can be represented by a digraph that is balanced (each point has the same number of arrows going out as going in). Show that there is a balanced digraph having 5 points.

    If at first you don't succeed...
    try googling "scissor paper rock lizard spock."