MOE H3 Math Proofs and Reasoning Problem Set 2 Solutions

MOE H3 Math Mathematical Proofs and Reasoning Problem Set 2 1. Is each of the following statements true or false? Give a proof if it is true, and give a counter-example if it is false. (a) For each pair of real numbers x and y, if x + y is irrational, then x is irrational and y is irrational. Solution: False. A counterexample is x = √ 2 and y = 0. Then x + y = √ 2 is irrational but not both x and y are irrational. (b) For each pair of real numbers x and y, if x + y is irrational, then x is irrational or y is irrational. Solution: True. Prove by contrapositive: For every pair of real numbers x and y, if x is rational and y is rational, then x + y is rational. This statement is true by closure property of rational numbers under addition. (Note that the closure property of rational number is a ‘theorem’ rather than an ‘axiom’. It can be proven rather easily. Here you may assume it has been proven and use it without proving it again.) (c) For each pair of nonzero real numbers x and y, if x is rational and y is irrational, then xy is irrational. Solution: True. We will prove by contradiction. Write x = a b for some integers a, b∈ Z. Suppose xy is a rational number, xy = c d for some integers c, d∈ Z. Then y = c d · x = c d · a b = ac bd is a rational number since ac, bd∈ Z. This means y is rational, contradicting the assumption that y is irrational. Therefore, our assumption is false, and xy must be irrational. 2. (Y2023 Q5) (a) Let p be a prime number greater than 2. Write down the possible remainders of p when divided by 4.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 2 Solution: Possible remainders are 0, 1, 2, 3. (b) Fermat’s Little Theorem states that if p is prime and a is an integer which is not divisible by p, then ap−1 ≡ 1 (modulo p). Use Fermat’s Little Theorem to prove that if p is a prime number greater than 2, and there exists an integer z such that z2 ≡ −1 (modulo p), then p is not congruent to 3 (modulo 4). Solution: Use proof by contradiction. Suppose p ≡ 3 (mod 4). This means that p − 3 = 4k for some k ∈ Z. Now If z2 ≡ −1 (mod p), then p ∤ z. So, by Fermat’s little theorem, zp−1 ≡ 1 (mod p). By assumption, z2 ≡ −1 (mod p) tells us that z4 ≡ 1 (mod p). Now zp−3 = z4k = (z4)k ≡ 1k = 1 (mod p). Thus, by Fermat’s little theorem 1 ≡ zp−1 = Z p−3z2 ≡ (1)(−1) = −1 (mod p), which is true only if p = 2, which is a contradiction. Hence, p ̸≡ 3 (mod 4). In fact, we know that since p ̸= 2, p ̸≡ 0, 2 (mod 4). That is, it must be the case that p ≡ 1 (mod 4). (c) Write down the possible remainders of w2 when divided by 8 where w is an integer. Solution: 12 ≡ 1 (mod 8), 2 2 ≡ 4 (mod 8), 3 2 ≡ 1 (mod 8), 4 2 ≡ 0 mod 8, 52 ≡ 1 (mod 8), 6 2 ≡ 4 (mod 8), 7 2 ≡ 1 (mod 8). So, w2 ≡ 0, 1, 4 (mod 8). 3. Unique Factorization Theorem states that: Every integer n >1 has a unique standard factored form. i.e. there is exactly one way to express n = pk1 1 pk2 2 · · ·pkt t where p1 < p2 < · · ·< pt are distinct primes and k1, k2, · · ·, kt are some positive integers. Use the Unique Factorization Theorem to prove that, if a positive integer n is not a perfect square, then √n is irrational. Solution: Prove by contradiction. Suppose n is not a perfect square and √n is rational. Then √n = a b for some integers a, b. Squaring both sides and clearing denominator gives nb2 = a2 − − −(∗). Consider the standard factored forms of n, aand b: n = pk1 1 pk2 2 · · ·pkt t Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 2 a = qe1 1 qe2 2 · · ·qeu u ⇒ a2 = q2e1 1 q2e2 2 · · ·q2eu u b = rf1 1 rf2 2 · · ·rfv v ⇒ b2 = r2f1 1 r2f2 2 · · ·r2fv v i.e. the powers of primes in the standard factored form of a2 and b2 are all even integers. This means the powers ki of primes pi in the standard factored form of n are also even by Unique Factorization Theorem (UFT): Note that all pi appear in the standard factored form of a2 with even power 2ci, because of (∗). By UFT, pi must also appear in the standard factored form of nb2 with the same even power 2ci. If pi ∤ b, then ki = 2ci which is even. If pi | b, then pi will appear in b2 with even power 2di. So ki + 2di = 2ci, and hence ki = 2(ci − di), which is again even. Hence n = pk1 1 pk2 2 · · ·pkt t =

pk1/2 1 pk2/2 2 · · ·pkt/2 t 2 . Since ki/2 are all integers, pk1/2 1 pk2/2 2 · · ·pkt/2 t is an integer and n is a perfect square. This contradicts the given hypothesis that n is not a perfect square. So we conclude that when a positive integer n is not a perfect square, then √n is irrational. 4. Prove or disprove the statement If a2 | b2, then a | b for all integers a, b. Solution: Write a = nY i=1 pαi i and b = Qn i=1 pβ i be the prime factorization of a and b, where pi ̸= pj for i ̸= j (pi are distinct), and αi, βi ≥ 0 for all i = 1, ..., n. Then since a2 | b2, it means that 2 αi ≤ 2βi for all i = 1, ..., n. Hence, αi ≤ βi for all i = 1, ..., n. Hence, a | b. 5. Determine whether each of the following real numbers is rational or irrational. Justify your answers. (a) √ 3 + √ 5; Solution: √ 3 + √ 5 is irrational. Proof by contradiction. Suppose √ 3 + √ 5 is rational. Then we can write √ 3 + √ 5 = m n where m, n∈ Z. Squaring both sides gives 3 + 2 √ 3 √ 5 + 5 = m2 n2 . This gives √ 15 = m2 2n2 − 4 = 2m2 − n2 4n2 Page 3

H3 Math (Mathematical Proofs and Reasoning) Problem Set 2 which implies √ 15 is a rational number. However, since 15 is not a perfect square, √ 15 is an irrational number (by known result). This gives a contradiction. (b) √ 2 + √ 8; Solution: We can write √ 2 + √ 8 = √ 2(1 + √ 4) = 3 √ 2. Since 3 is a non-zero rational number, and √ 2 is irrational, the product 3 √ 2 is an irrational number. (Here we use the known result that product of a non-zero rational number and an irrational number is irrational. This result itself can be proven using contradiction.) (c) 1 + √ 2 1 + √ 3 . Solution: 1 + √ 2 1 + √ 3 is irrational. Proof by contradiction. Suppose 1 + √ 2 1 + √ 3 is rational. Then we can write 1 + √ 2 1 + √ 3 = m n where m, n∈ Z. This can be rewritten as n(1 + √ 2) = m(1 + √ 3) and further as n √ 2 − m √ 3 = m − n. Squaring both sides gives 2n2 − 2nm √ 2 √ 3 + 3m2 = m2 − 2mn + n2. This gives √ 6 = 2m2 + 2mn + n2 2nm which implies √ 6 is a rational number. However, since 6 is not a perfect square, √ 6 is an irrational number (by known result). This gives a contradiction. 6. Prove that there does not exists a smallest positive real number. Solution: Suppose r >0 is the smallest positive real number. Since 1 2 ≥ 0, r 2 > 0 too. Also, r = r 2 + r 2 =⇒ r 2 < r. Thus r 2 is a positive real number that is strictly smaller than r, contradicting the mini- mality of r. Therefore, no smallest positive real number exists. Page 4

H3 Math (Mathematical Proofs and Reasoning) Problem Set 2 7. Prove that each finite decimal may be written as an infinite decimal in two distinct ways: a0.a1a2 . . . an−1an = a0.a1a2 . . . an−1anb0 = a0.a1a2 . . . an−1(an − 1)b9, where an > 0 if n >0. (Here b0 means an infinite tail of 0’s, and b9 an infinite tail of 9’s.) Solution: Write x = a0.a1a2 . . . an−1an = nX k=0 ak 10−k. Appending an infinite tail of zeros does not change the value: a0.a1 . . . an−1anb0 = nX k=0 ak 10−k = x. For the b9 representation (which requires an ≥ 1 when n >0), consider a0.a1 . . . an−1(an − 1)b9 = n−1X k=0 ak 10−k + (an − 1)10−n + ∞X k=n+1 9 · 10−k. The infinite tail sums to ∞X k=n+1 9 · 10−k = 9 · 10−(n+1) ∞X j=0 10−j = 9 · 10−(n+1) · 1 1 − 1/10 = 10−n. Hence the last two terms combine to ( an − 1)10−n + 10−n = an10−n, giving the same value x. Thus both infinite decimals represent the original finite decimal. 8. Prove that each real number is represented by a unique infinite decimal unless it is representable by a finite decimal, in which case it is representable by precisely two infinite decimals as described in the previous problem. Solution: Let two infinite decimals represent the same real number: x = a0.a1a2 . . . and x = b0.b1b2 . . . (so each ak, bk ∈ {0, 1, . . . ,9}). Let Sn = Pn k=0 ak 10−k an