Homework #5 Solutions

Homework #5
Solutions
By Stephan Garcia

Section 2.5

2(f) Express the greatest common divisor 124 and 323 as a linear combination of these integers.
Solution:
First we need to find gcd(124,323). Although this can be done in other ways, we will use the Euclidean Algorithm.

323 = 2×124 +75
124 = 1×75 + 49
75 = 1×49 + 26
49 = 1×26 + 23
26 = 1×23 + 3
23 = 7×3 + 2
3 = 1×2 + 1
2 = 2×1 + 0.

Therefore gcd(124,323) = 1 and we see that

1 = –1×2 + 3
= –1(23 – 7×3) + 3
= 8×3 – 1×23
= 8×(26 – 1×23) – 1×23
= – 9×23 + 8 ×26
= – 9×(49 – 1×26) + 8×26
= 17×26 – 9×49
= 17×(75 – 1×49) – 9×49
= – 26×49 + 17×75
= – 26×(124 – 1×75) + 17×75
= 43 ×75 – 26×124
= 43×(323 – 2×124) – 26×124
= 43×323 – 112×124.

8. Find an inverse of 144 modulo 233.
Solution:

An inverse is guaranteed to exist since gcd(144,233) = 1. We can see this because 144 = 12² = 2⁴3² and one can easily check that 2 and 3 do not divide 233. Nevertheless we need to use the Euclidean Algorithm since we wish to find integers x and y such that 144x + 233y = 1. If we find such x and y we will have 144x º 1 (mod 233).

233 = 1×144 + 89
144 = 1×89 + 55
89 = 1×55 + 34
55 = 1×34 + 21
34 = 1×21 + 13
21 = 1×13 + 8
13 = 1×8 + 5
8 = 1×5 + 3
5 = 1×3 + 2
3 = 1×2 + 1
2 = 2×1.

Back substituting we obtain

1 = 3 – 2 = 3 – (5 – 3)
= 2×3 – 5 = 2× (8 – 5) – 5
= 2×8 – 3×5 = 2×8 – 3×(13 – 8)
= 5×8 – 3×13 = 5×(21 – 13) – 3×13
= 5×21 – 8×13 = 5×21 – 8×(34 – 21)
= 13×21 – 8×34 = 13×(55 – 34) – 8×34
= 13×55 – 21×34 = 13×55 – 21(89 – 55)
= 34×55 – 21×89 = 34×(144 – 89) – 21×89
= 34×144 – 55×89 = 34×144 – 55(233 – 144)
= 89×144 – 55×233.

Therefore 89×144 º 1 (mod 233) and 144 is the inverse of 89 mod 233.

10.Show that an inverse of a modulo m does not exist if gcd(a,m) > 1.
Solution:

If ax º 1 (mod m) then there exists an integer y such that ax + my = 1. Let d = gcd(a,m) > 1 and since d|a and d|m it follows that d|1. This implies that d = 1, a contradiction.

15.Show that if p is prime, the only solutions of x2 º 1 (mod p) are integers x such that x º 1 (mod p) and x º –1 (mod p).
Solution:
If x² º 1 (mod p) then p|x² – 1. Since x² – 1 = (x + 1)(x – 1) and since p is prime it follows that either p|(x + 1) or p|(x – 1). Hence x º 1 (mod p) or x º –1 (mod p).

16a.Generalize the result in part (a) of exercise 14; that is, show that if p is prime, the positive integers less that p, except 1 and p – 1, can be split into (p – 3)/2 pairs of integers such that each pair consists of integers that are inverses of each other.
Solution:
Since p is prime, each number a satisfying 1 £ a £ p – 1 has gcd(a,p) = 1 and hence has a unique inverse mod p. Notice that 1² º 1 (mod p) and (p – 1)² º (–1)² º 1 (mod p) so that 1 and p – 1 are always self-inverse. None of the remaining p – 3 integers a in the range 1 < a < p – 1 can be self-inverse by Problem 15. Therefore the remaining p – 3 integers can be split into (p – 3)/2 pairs of integers that are inverse to each other mod p.

16b.From part (a) conclude that (p – 1)! º –1 (mod p) whenever p is prime. This result is known as Wilson’s Theorem.
Solution:
By part (a) the numbers 2, 3, …, p – 2 can be arranged as (p – 3)/2 pairs of integers that are inverse to each other mod p. Therefore (p – 1)! º 1× 2× 3× …× (p – 1) º 1× (p – 1) º –1 (mod p) can be attained by regrouping and pairing off the numbers 2, 3, …, p – 2.

16c.What can we conclude if n is a positive integer such that (n – 1)! is not congruent to –1 (mod n)?
Solution:

If (n – 1)! is not congruent to –1 (mod n), then n cannot be prime. If n were prime, then (n – 1)! º –1 (mod n) by part (b).

22.Which integers are divisible by 5 but leave a remainder of 1 when divided by 3?
Solution:
This is equivalent to the system of two congruences x º 0 (mod 5) and x º 1 (mod 3). By the Chinese Remainder Theorem there exists a unique solution mod 15. Since there are only 3 integers divisible by 5 and £ 15, we only need to check 0, 5, and 10. 10 clearly satisfies 10 º 1 (mod 3).

Section 3.1

4.Construct an argument using rules of inference to show that the hypotheses "If it does not rain or if it is not foggy, then the sailing race will be held and the life-saving demonstration will go on," "If the sailing race is held, then the trophy will be awarded," and "The trophy was not awarded" imply the conclusion "It rained."
Solution
Let R = "it rains," F = "it is foggy," S = "the sailing race will be held," L = "the life-saving demonstration will go on," and T = "the trophy will be awarded." We obtain the hypotheses

(ØR Ú ØF) ® (S Ù L)
S ® T
ØT

Since Ø T and S ® T hold, it follows that Ø S holds as well (modus tollens). Since Ø (S Ù L) holds it follows that Ø (Ø R Ú Ø F) holds. This is equivalent to R Ù F and therefore R holds.

22.Prove that the product of two rational numbers is rational.
Solution:
Let p and q be rational numbers. Then there exist integers a,b,c,d such that b,d ¹ 0 and a/b = p and c/d = q. Then pq = (a/b)(c/d) = (ac)/(bd) where bd ¹ 0 and ac and bd are integers. Hence pq is rational.

24.Prove or disprove that the product of a nonzero rational number and an irrational number is irrational.
Solution:
Let p be rational and r be irrational. Since p ¹ 0, 1/p is nonzero and rational. By problem 22, if pr were rational then (pr)(1/p) = r would be rational as well. Since this would contradict the hypothesis that r is irrational, it follows that pr must be irrational.

32.Use a proof by cases to show that ë n/2û é n/2ù = ë n²/4û for all integers n.
Solution:
If n is an even integer, then the statement is obviously true. If n is an odd integer, then there exists an integer m such that n = 2m + 1. Hence ë n/2û = ë m + 1/2û = m and é n/2ù = é m + 1/2ù = m + 1. Also ë n²/4û = ë (2m + 1)²/4û = ë (4m² + 4m + 1)/4û = ë m² + m + 1/4û = m² + m = m(m + 1). Hence ë n/2û é n/2ù = ë n²/4û holds in this case as well.

40.Prove or disprove that a mod m + b mod m = (a + b) mod m whenever m is a positive integer.
Solution:
The statement is false. Let m = 2 and let a = b = 1. Then 1 mod 2 + 1 mod 2 = 2 which is not the same as (1 + 1) mod 2 = 0.

42.Prove that if n is a positive integer such that the sum of its divisors is n + 1, then n is prime. What kind of proof did you use?
Solution:
Since 1 and n always divide n, it follows that the sum of the divisors of n, s (n), satisfies s (n) ³ n + 1. If n has other divisors besides 1 and n (n is composite), then s (n) > n + 1 (specifically s (n) ¹ n + 1). It follows then that if s (n) = n + 1, then n is not prime by contraposition.

44e.Prove or disprove ë xû + ë yû + ë x + yû £ ë 2xû + ë 2yû for all real numbers x and y.
Solution:
If both x and y are integers, then equality holds and the statement is true. Let x = n + p and y = m + q where n and m are integers and 0 £ p, q < 1. There are four remaining cases to check. If 0 < p, q < 1/2 it follows that ë xû + ë yû + ë x + yû = n + m + (n + m) = 2n + 2m = ë 2xû + ë 2yû and the statement is true. If 1/2 £ p, q < 1 then ë xû + ë yû + ë x + yû = n + m + (n + m + 1) = 2n + 2m + 1 £ (2n + 1) + (2m + 1) = ë 2xû + ë 2yû and the statement is true. If 0 < p < 1/2 and 1/2 £ q < 1 we have ë xû + ë yû + ë x + yû £ n + m + (n + m + 1) = 2n + (2m + 1) = ë 2xû + ë 2yû and the statement is true. The case 0 < q < 1/2 and 1/2 £ p < 1 is proved similarly.

52.Prove that if n is an integer, the following three statements are equivalent: (1) 5|n, (2) 5|n², (3) n² is not congruent to ± 1 (mod 5).
Solution:
If 5|n then there exists an integer d such that 5d = n and hence 5(nd) = n² and 5|n². Conversely if 5|n² it follows that 5|n. This is because if a prime number p|ab then p|a or p|b and here p = 5 and a = b = n. Thus (1) « (2). Since 5|n² if and only if n² º 0 (mod 5) it follows that (2) « (3). Hence the three statements are equivalent.

58.Find a counterexample to the proposition: "For every prime number n, n + 2 is prime."
Solution:
Take n = 2. Then n + 2 = 4 is certainly not prime! 7, 13, 19, … also work too.

66a.Given the following two assumptions: (1) "Logic is difficult or not many students like logic," (2) "If mathematics is easy, then logic is not difficult." By translating these assumptions into statements involving propositional variables and logical connectives, determine whether each of the following are valid conclusions of these assumptions: (a) That mathematics is not easy, if many students like logic, (e) That if not many students like logic, then either mathematics is not easy or logic is not difficult.
Solution:
Let D = "Logic is difficult," M = "Many students like logic," and E = "Mathematics is easy." Assumptions (1) and (2) become

D Ú Ø M
E ® Ø D

Statement (a) is M ® Ø E which is equivalent to Ø M Ú Ø E. The contrapositive of E ® Ø D is D ® Ø E. Hence D ® Ø E ® (Ø M Ú Ø E) « (M ® Ø E). The first hypothesis shows that Ø D ® Ø M ® (Ø M Ú Ø E) « (M ® Ø E). Hence M ® Ø E always holds since either D or Ø D is always true. Statement (b) is Ø M ® (Ø E Ú Ø D) which is equivalent to Ø M Ú (E ® Ø D). Since E ® Ø D is true (by hypothesis) it follows that Ø M ® (Ø E Ú Ø D) is valid.