For the proofs requested below, use facts and theorem given in this lesson, including results given

in the exercises, as justifications. Assume all letters represent integers.

(1) Mimic the proof given in the sample solutions for the proposition if a > 0 and b > 0, then ab > 0 to prove:

(a) If a < 0 and b < 0, then ab > 0.

(b) If a < 0 and b > 0, then ab < 0.

(2) Prove that is m2 = n2, then m = n or m = −n. (Hints: (1) From algebra: a2 − b2 = (a + b)(a− b), and (2) From exercises: If ab = 0, then either a = 0 or b = 0.)

(3) Determine all the integers that 0 divides. Hint: Think carefully about the definition of the divides relation! This question is

about the divides relation, not about the arithmetic operation of division (a maybe subtle distinction). The correct answer is probably not what you might first think it is.

(4) Prove: For integers r, s, t,and u, if r|t and s|u, then rs|tu.

(5) Determine the quotient and remainder when 117653 is divided by 27869. (Finally, an easy problem.)

(6) (bonus) Prove or give a counterexample: If p is a prime, then 6p + 1 is a prime.

12. Lesson 12

(1) Use the Euclidean Algorithm to compute the following gcd’s:

10

(a) gcd(216, 111).

(b) gcd(1001, 11).

(c) gcd(663, 5168).

(d) gcd(1357, 2468).

(e) gcd(733103, 91637).

(2) If p is a prime, and n is any integer, what are the possible values of gcd(p, n)? Hint: Try a few experiments with specific numbers to spot the correct answer. Alternatively, think about the positive integers that can divide a prime. Warning: In the notation gcd(a, b), do not assume that a ≥ b. The two parameters a and b can be written in either order: gcd(15, 12) = gcd(12, 15) = 3.

(3) Determine gcd(6123, 2913) and write it as a linear combination of 6123 and 2913.

(4) What can you conclude about gcd(a, b) if there are integers s, t such that as + bt = 8?

(5) What is the smallest positive integer that can be written as a linear combination of 2191 and 1351?

(6) (bonus) If n is a positive integer, what is gcd(n, n + 1)? Explain your answer.

13. Lesson 13

(1) Determine the prime factorization of 212100.

(2) How many positive divisors does 212100 have? You don’t have to list them all, just deter- mine how many there are. This isn’t difficult using the result of problem 1. See a similar example in the notes.

(3) Find all integer solutions to 14x + 77y = 69.

(4) Find all integer solutions to 14x + 77y = 70.

(5) Beth stocked her video store with a number of video game machines at $79 each, and a number of video games at $41 each. If she spent a total of $6358, how many of each item did she purchase?

(6) (bonus) Determine all integer solutions to 5x− 7y = 99. Watch that minus sign!

11

14. Lesson 14: Test #2

15. Lesson 15

(1) (a) Suppose we have a 52 card deck with the cards in order ace , 2, 3, . . . , queen, king top to bottom, for clubs, then diamonds, then hearts, then spades. A step consists to taking the top card and moving it to the bottom of the deck. We start with the ace of clubs as the top card. After two steps, the top card is the 3 of clubs. What is the top card after 735 steps?

(b) The marks on a combination lock are numbered 0 to 39. If the lock is at mark 19, and the dial is turned one mark clockwise, it will be at mark 18. If the lock is at mark 19 and turned 137 marks clockwise, at what mark will it be?

(2) (a) Arrange the numbers −39,−27,−8, 11, 37, 68, 91 so they are in the order 0, 1, 2, 3, 4, 5, 6 modulo 7.

(b) Determine n between 0 and 16 such that 311 + 891 ≡ n (mod 17).

(c) Determine n between 0 and 16 such that (405)(777) ≡ n (mod 17).

(d) Determine n between 0 and 16 such that 710447 ≡ n (mod 17).

(3) Find all solutions: 33x ≡ 183 (mod 753).

(4) A multiple choice test contains 10 questions. There are four possible answers for each ques- tion.

(a) How many ways can a student complete the test if every question must be answered?

(b) How many ways can a student complete the test if questions can be left unanswered?

(5) Here are two questions most easily done using the Good = Total − Bad method.

(a) How many seven-letter words contain at least one X?

(b) How many seven-letter words contain at least two X’s? Hint: The Bad ones are those with no X’s and those with exactly one X. Think carefully about counting the number of words with exactly one X.

(6) (bonus) A code word is either a sequence of three letters followed by two digits or two letters followed by three digits. (Unless otherwise indicated, letters will means letters chosen from

12

the usual 26-letter alphabet and digits are selected from {0, 1, 2, 3, . . . , 8, 9}. Also, unless it is stated that letters have to be different, you should assume repeats are allowed. Likewise for digits.) How many different code words are possible?

16. Lesson 16

(1) (a) (a permutation problem, order matters) An ID code consists of 4 different letters and 3 different digits. How many codes are possible if the letters must be kept together? For example, 34ABCD9 and WAXT604 are good, but TR67Y Z3 is bad.

(b) (a combination problem, order does not matter) A lottery ticket consists of four differ- ent integers between 1 and 99 (inclusive). How many different lottery tickets are there?

(2) Determine the coefficient of x4y5 in the expansion of (3x− 2y)9. Be sure to take the 3 and the −2 coefficients into account.

(3) Give an algebraic proof that

( 2n

2

) = 2

( n

2

) + n2.

Hint: The idea is to expand and simplify each side of the equation, then compare the two results and make sure they are the same. This problem seems to cause a lot of anguish. It might help if the two sides are computed for a few specific values of n to see how the arithmetic works out. Try n = 3 and n = 4 for example.

(4) A poker hand consists of five cards selected from a 52 card deck. The order of the cards in a poker hand does not matter. A poker hand is called a full house if it has two cards of one rank and three cards of a second rank. For example, a hand consisting of two 7’s and three queens is a full house. How many different full house hands are there?

(5) How many permutations of the letters a,b,c,d,e,f,g either begin with an a or end with an a?

(6) (bonus) A committee of size five is selected from a group of ten clowns and twelve lion tamers.

(a) How many different committees are possible?

(b) How many committees are possible if there must be exactly two clowns on the com- mittee?

(c) How many committees are possible if lion tamers must outnumber clowns on the com- mittee?