HW 4 Answer Key

Section 2.3

6. Under the hypotheses, we have c = as and d = bt for some s and t. Multiplying we obtain cd = ab(st), which means that ab | cd, as desired.

8. a. prime b. not prime c. not prime

10 a. 3 * 13 b. 3^{4} c. 101 (prime) d. 11 * 13 e. 17 * 17 f. 29 * 31

18. Assume that a ≡ b(modm) . This means that m | a − b , so a − b = mc , or a = b + mc. We know that b = qm + r for some nonnegative r less than m (namely r = b mod m). Therefore a = qm + r + mc = (q + c)m + r . By definition this means that r must also equal a mod m. This is what we wanted to prove.

24. a. 2^{2} ∗ 3^{3} ∗ 5^{2} b. 2 ∗ 3 ∗ 11 c. 17 d. 1 e. 5 f. 2 ∗ 3 ∗ 5 ∗ 5

36.From a ≡ b(modm) we know that b = a + sm for some integer s . Now, if d is common divisor for a and m, then it divides the right hand side of this equation, so it also divides b. Similarly, any common divisor of b and m is also a divisor of a. Hence the set of common divisors of a and m is the same as the set of common divisors of b and m, and therefore gcd(a,m)=gcd(b,m).

40. x_{0} = 3 x_{1} = (4 · 3 + 1) mod 7 = 13 mod 7 = 6 x_{2} = (4 · 6 + 1) mod 7 = 25 mod 7 = 4 x_{3} = (4 · 4 + 1) mod 7 = 17 mod 7 = 3 At this point we know the sequence is 3,6,4,3,6,4,... forever

43. a. GR QRW SDVV JR b. QB ABG CNFF TB c. QX UXM AHJJ ZX

44. a. BLUE JEANS b. TEST TODAY c. EAT DIM SUM

Section 3.1

3 a. Fallacy of affirming the conclusion b. Fallacy of begging the question c. Valid argument using modus tollens d. Valid argument using disjunctive syllogism e. Fallacy of denying the hypothesis.

10 A rational number is a number that can be written in the form x/y where x and y are integers and y ≠ 0. Suppose that we have two rational numbers, say a/b and c/d. Then their sum is, by the usual rules for addition of fractions, (ad + bc)/(bd) . Note that both the numerator and the denominator are integers, and that bd ≠ 0 since b and d were both nonzero. Therefore the sum is, by definition, a rational number.

12 A rational number is a number that can be written in the form x/y where x and y are integers and y ≠ 0. Suppose that we have two rational numbers, say a/b and c/d. Then their product is, by the usual rules for product of fractions, (ac)/(bd) . Note that both the numerator and the denominator are integers, and that bd ≠ 0since b and d were both nonzero. Therefore the product is, by definition, a rational number.

17 Suppose 3^{1}/3 = a/b, a, b are integers,b ≠ 0, and gcd(a,b)=1. Then 3b^{3} = a^{3} . Hence 3 | a^{3} , which can only happen if 3 | a. Let a = 3m. Then 9b^{3} = 27m^{3}, or b^{3} = 9m^{3} .Thus 3 | b . This is a contradiction of the assumptuion gcd(a,b)=1.

18 A proof by contradiction:

Suppose that n is not a perfect square but that \sqrt{n} is a rational number, say a/b, with a and b integers. Then nb^{2} = a^{2}. Consider the prime factorizations of the two sides of this equation, which must be identical by the Fundamental Theorem of Arithmetic (Section2.3). On the right-hand side, every prime factor appears to an even power, because of the square. On the left-hand side, since n is not a perfect square, not every prime factor of n appears to an even power, but every prime factor of b does; therefore at least one prime factor of the left-hand side appears to an odd power. This is impossible. Therefore \sqrt{n} is not rational.

20 A proof by cases:

There are four possible remainders when an integer n which is not divisible by 5 is divided by 5. These remainders are 1, 2, 3, and 4. Therefore we can write n = 5k + 1, n = 5k + 2, n = 5k + 3,or n = 5k + 4. We show that in each case the remainder when n^{2} is divided by 5 is either 1 or 4.

Case 1: Suppose n = 5k + 1. n^{2} = (5k + 1)^{2} = 25k^{2} + 10k + 1 = 5(5k^{2} + 2k) + 1. Therefore we see that the remainder when n^{2} is divided by 5 is 1.

Case 2: Suppose n = 5k + 2. n^{2} = (5k + 2)^{2} = 25k^{2} + 20k + 4 = 5(5k^{2} + 4k) + 4. Therefore we see that the remainder when n^{2} is divided by 5 is 4.

Case 3: Suppose n = 5k + 3. n^{2} = (5k + 3)^{2} = 25k^{2} + 30k + 9 = 5(5k^{2} + 6k + 1) + 4. Therefore we see that the remainder when n^{2} is divided by 5 is 4.

Case 4: Suppose n = 5k + 4. n^{2} = (5k + 4)^{2} = 25k^{2} + 40k + 16 = 5(5k^{2} + 8k + 3) + 1. Therefore we see that the remainder when n^{2} is divided by 5 is 1.

22.Let us prove directly that if n is even 7n + 4 is even. Let cn = 2k for some integer k.Then 7n + 4 = 14k + 4 = 2(7k + 2) . This is 2 times an integer and is hence even. Consider an indirect proof for n is even if 7n + 4 is even. Suppose that n is odd. Then let n be c = 2k + 1 for some integer k. Thus 7n + 4 = 14k + 11 = 2(7k + 5) + 1 . This is twice an integer plus 1, so it is odd. this completes the indirect proof.

40. We need only find a prime number n such that n + 2 is not prime. The smallest examples are n = 2and n = 7.

44. One counter-example is sufficient. Let a = 2 and b = 1/2. Then a^{b} = 2^{1}/2 = \sqrt{2} which we know is not rational.