Solutions to Assignment 1

Solutions to Assignment 1

Question 1. [Exercises 1.1, # 6]

Use the division algorithm to prove that every odd integer is either of the form 4k + 1 or of the form 4k + 3 for some integer k.

Solution: For each positive integer n, the only possible remainders when n is divided by 4 are r = 0, 1, 2, 3, so that n has exactly one of the forms

4k, 4k + 1, 4k + 2, 4k + 3 for some integer k. Since 4k and 4k + 2 are even, then every odd integer has the form 4k + 1 or 4k + 3 for some integer k.

Question 2. [Exercises 1.1, # 8]

(a) Divide 52, 72, 112, 152, and 272 by 8 and note the remainder in each case. (b) Make a conjecture about the remainder when the square of an odd integer is divided by 8. (c) Prove your conjecture.

Solution:

(a) We have 52 = 25 = 24 + 1 = 3 ? 8 + 1 72 = 49 = 48 + 1 = 6 ? 8 + 1

112 = 121 = 120 + 1 = 15 ? 8 + 1 152 = 225 = 224 + 1 = 28 ? 8 + 1 272 = 729 = 728 + 1 = 91 ? 8 + 1, and the remainder is 1 in each case. (b) The conjecture is that for any odd integer n, we have n2 = 8k + 1 for some integer k. (c) If n is an odd integer. then n = 4m + 1 or n = 4m + 3 for some integer m, so that either n2 = (4m + 1)2 = 16m2 + 8m + 1 = 8(2m + 1) + 1 or n2 = (4m + 3)2 = 16m2 + 24m + 1 = 8(2m + 3) + 1 and in both cases n2 = 8k + 1.

Question 3. [Exercises 1.2, # 8]. If r Z and r is a nonzero solution of x2 + ax + b = 0 (where a, b Z), prove that r | b.

Solution: If r is a nonzero solution of x2 + ax + b = 0, then

r2 + ar + b = 0,

so that and r | b.

b = -r2 - ar = -r(r + a),

Question 4. [Exercises 1.2, # 10]. Prove that (n, n + 1) = 1 for every positive integer n.

Solution: Note that

1 = 1 ? (n + 1) + (-1) ? n,

so that 1 is a linear combination of n + 1 and n, and is the smallest such positive integer. Therefore (n, n + 1) = 1.

Question 5. [Exercises 1.2, # 16].

If (a, b) = d, prove that

a d

,

b d

= 1.

Solution: If (a, b) = d, then there exist integers x and y such that

d = ax + by,

and since d 1 > 0, dividing both sides of this equation by d, we have

1

=

a d

?

x

+

b d

?

y,

so

that

1

is

a

linear

combination

of

a d

and

b d

,

and

is

the

smallest

such

positive

integer.

Therefore

a d

,

b d

= 1.

Question 6. [Exercises 1.2, # 26]. Let a, b, c Z. Prove that the equation ax + by = c has integer solutions if and only if (a, b) | c.

Solution: Suppose that (a, b) | c, then c = k ? (a, b) for some integer k. Also, (a, b) = ax0 + by0 for some integers x0 and y0, so that

c = k(a, b) = akx0 + bky0 = ax + by

where x = kx0 and y = ky0 are in Z, and the equation ax + by = c has integer solutions.

Conversely, suppose that there exist integer solutions to the equation ax + by = c, say, ax0 + by0 = c,

since (a, b) | a and (a, b) | b, then (a, b) | c.

Question 7. [Exercises 1.2, # 32]. Prove that a positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3. [Hint : 103 = 999 + 1 and similarly for other powers of 10.]

Solution: Every positive integer n has a unique representation as n = a0 + a1 ? 10 + a2 ? 102 + ? ? ? + ak ? 10k

where 0 ai 9 for i = 0, 1, 2, . . . k.

Now, an easy proof by induction shows that for each 1 i k, 10i - 1 = (10 - 1) ? (10i-1 + ? ? ? + 10 + 1) = 9 ? (10i-1 + ? ? ? + 10 + 1),

which is divisible by 9, and therefore is also divisible by 3.

Thus,

n - (a0 + a1 + ? ? ? + ak) = a1 ? (101 - 1) + a2 ? (102 - 1) + ? ? ? + ak ? (10k - 1)

is also divisible by 9, and hence also by 3, and therefore the positive integer n is divisible by 3 if and only if the sum of its decimal digits is also divisible by 3.

Question 8. [Exercises 1.3, # 2].

Let p be an integer other than 0, ?1. Prove that p is prime if and only if for each a Z either (a, p) = 1 or p | a.

Solution: Suppose that p is a prime, and a Z. Let d = (a, p), since d | p, then either d = 1 or d = p, that is, either (a, p) = 1 or p | a.

Let p be an integer other than 0, ?1, and suppose that p is not a prime, then (assuming p > 1) there exist integers a and b with 1 < a, b < p such that p = a ? b. Since a | p, then (a, p) = a > 1. Also, since 1 < a < p, then p a.

Question 9. [Exercises 1.3, # 8]. Prove that (a, b) = 1 if and only if there is no prime p such that p | a and p | b.

Solution: Suppose (a, b) = 1, if p is a prime such that p | a and p | b, then p | (a, b) = 1, which is a contradiction. Therefore there is no prime such that p | a and p | b.

Conversely, if d = (a, b) > 1, then there exists a prime p such that p | d, and since d | a and d | b, then p | a and p | b.

Question 10. [Exercises 1.3, # 12].

(a) If 3 | (a2 + b2), prove that 3 | a and 3 | b. [Hint : If 3 a, then a = 3k + 1 or a = 3k + 2.]

(b) If 5 | (a2 + b2 + c2), prove that 5 | a or 5 | b or 5 | c.

Solution:

(a) Note that if 3 a, then a = 3k + 1 or a = 3k + 2 for some integer k, and a2 = (3k + 1)2 = 3(3k2 + 2k) + 1 or a2 = 3(3k2 + 4k + 1) + 1

so that a2 leaves a remainder of 1 when divided by 3. Therefore, a2 + b2 leaves a remainder of 1 + 0 = 1 or 1 + 1 = 2 depending on whether b is divisible by 3 or not. Thus, if 3 a, then 3 a2 + b2. Therefore, if 3 | a2 + b2, then 3 | a. Similarly, if 3 | a2 + b2, then 3 | b. (b) Suppose that a, b, c are integers such that 5 a, 5 b, and 5 c. Since 5 a, then a and a2 must have one of the forms

a = 5k + 1 and a2 = (5k + 1)2 = 25k2 + 10k + 1 a = 5k + 2 and a2 = (5k + 2)2 = 25k2 + 20k + 4 a = 5k + 3 and a2 = (5k + 3)2 = 25k2 + 30k + 5 + 4 a = 5k + 4 and a2 = (5k + 4)2 = 25k2 + 40k + 15 + 1 so that a2 can only leave a remainder of 1 or 4 when divided by 5, similarly for b2 and c2. Therefore, when a2 + b2 is divided by 5, the only possible remainders are 2, 0, or 3, since

1 + 1 = 2, 1 + 4 = 5, 4 + 4 = 8, and the only possible remainders when (a2 + b2) + c2 is divided by 5 are 1, 2, 3, or 4, since

2 + 1 = 3 and 2 + 4 = 6 0 + 1 = 1 and 0 + 4 = 4 3 + 1 = 4 and 3 + 4 = 7, and 5 a2 + b2 + c2.

Question 11. [Exercises 1.3, # 20].

(a) Prove that there are no nonzero integers a, b such that a2 = 2b2. [Hint : Use the Fundamental Theorem of Arithmetic or Theorem 1.8.]

(b) Prove that 2 is irrational.

[Hint : Use proof by contradiction (Appendix A). Assume that 2 = a/b (with a, b Z) and use part (a) to reach a contradiction.]

Solution:

(a) Suppose there exist positive integers a and b such that a2 = 2b2. From the Fundamental Theorem of Arithmetic, we may assume that a and b have no prime factors in common (if they do, just cancel them from both sides of the equation a2 = 2b2).

Since 2 is prime, and 2 | a2 = a ? a, then either 2 | a or 2 | a, and hence 2 | a, and a = 2k for some integer k. Therefore

a2 = (2k)2 = 4k2 = 2b2,

so that b2 = 2k2, and the same argument as above shows that 2 | b. However, this contradicts the fact that a and b have no prime factors in common.

Therefore there are no nonzero integers a and b such that a2 = 2b2.

(b) Suppose that 2 is rational, then there exist positive integers a and b such that

2

=

a b

,

so that a = 2 b. Squaring both sides, we get a2 = 2b2, which is a contradiction. Therefore 2 is

irrational.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download