Introduction to Proofs, an Inquiry-Based approach

Chapter 1 – Numbers

We begin with results about the integers Z= { . . . −2,−1,0,1,2, . . . }. In this chapter, “number” means integer. Some statements refer to the natural numbers N= {0,1,2, . . . } or the positive integers Z+ = {1,2, . . . }.

Divisibility

1.1 Definition. For two integers d ,n we say that d divides n if there is an integer k such that d ·k = n. Here, d is the divisor, n is the dividend, and k is the quotient. (Alternative wordings are: d is a factor of n, d goes evenly into n, n is divisible by d , or n is a multiple of d .) We write d ∣∣ n if d is a divisor of n, or d ∣∣- n if it is not.

1.2 Definition. A number is even if it is divisible by 2, otherwise it is odd. (We may instead say that the parity is even or odd.)
The notation d ∣∣ n signifies a relationship between two integers. It is different than the fraction d/n, which is a rational number: we can sensibly ask “Does 2 divide 5?” but “Does 2/5?” is not sensible.

1.3 Exercise. (Interaction with sigh) Each of these is a statement about integers. Prove each.
A. If a number is even then its negative is even. If a number is odd then its negative is odd.
B. If d ∣∣ a then both −d ∣∣ a and d ∣∣−a. In addition, d divides |a| (recall that the absolute value of a number, |a|, is a if a ≥ 0 and is −a if a < 0).

1.4 Exercise. (Interaction of party and addition) Prove or disprove. That is, for each decide if it is true or false and if it is true then prove it, while if it is false then give a counterexample.
A. The sum of two evens is even. The difference of two evens is even.
B. The sum of two odds is odd. The difference of two odds is odd.
C. For a,b ∈Z, the number a +b is even if and only if a −b is even.

1.5 Exercise. Generalize the first item of the prior exercise to be a statement about sums of multiples of d ∈Z, and then prove your statement.

1.6 Exercise. (Interaction of party and multiplication) Prove or disprove. (i) The product of two evens is even. (ii) The quotient of two evens, if it is an integer, is even.

1.7 Exercise. For the prior exercise’s first item, formulate and prove a generalization that applies to any integer.

1.8 Exercise. (Divisibility properties) Prove each. Assume that all the numbers are integers.
A. (Reflexivity) Every number divides itself.
B. Every number divides 0 while the only number that 0 divides is itself.
C. (Transitivity) If d ∣∣ n and n ∣∣ m then d ∣∣ m. That is, if n divides m then so do n’s divisors.
D. (Cancellation) Where d ,n ∈Z, if there is a nonzero integer a such that ad ∣∣ an then d ∣∣ n. And, if d ∣∣ n then ad ∣∣ an for all a ∈Z.
E. (Comparison) For d ,n ∈Z+, if n is a multiple of d then n ≥ d .
F. Every number is divisible by 1 and −1. The only numbers that divide 1 are 1 and −1.
G. The largest divisor of any nonzero a ∈Z is |a|.
H. Every nonzero integer has only finitely many divisors.

1.9 Exercise. What conclusion can you make if both a ∣∣ b and b ∣∣ a?

1.10 Exercise. Suppose that a,b,c ∈Z.
A. Prove that if a ∣∣ b then a ∣∣ bc for all integers c.
B. Prove that if a ∣∣ b and a ∣∣ c then a divides the sum b + c and difference b − c.
C. (Linearity) This generalizes the prior item: if a ∣∣ b and a ∣∣ c then a divides m ·b+n ·c for any m,n ∈Z.