Mathematics

Problem: Among 5 integers, there are always 3 with sum divisible by 3. (From Problem Solving Strategies, Arthur Engel) Solution: Proof by Pigeon Hole Principle. An integer is either 0, 1 or 2 \( \pmod 3 \). Imagine placing 5 integers into those 3 boxes. If we have at least one in each, then we can pick one from each, with sum divisible by 3. Otherwise, we'll have at least 3 integers in one of the boxes. Pick those 3. QED

Problem: Show that if \( p \) and \( p^2 +2 \) are prime, then so is \( p^3 + 2 \). Solution: \(p\) can't be 2. For \(p = 3 \), the statement is true. If \(p > 3\), we know that \(p^2 = 1 \pmod 3 \). Hence \(p^2 + 2 \) is always divisible by 3. QED.

Problem: If \(n\) is even, then \( 323 | 20^n + 16^n - 3^n - 1 \). Solution: Let \( n = 2k \). We have \( 17 | 400^k - 9^k \) and \( 17 | 256^k - 1 \). Hence \( 17 | 20^n + 16^n - 3^n - 1 \). Also \( 19 | 20^n -1 \) and \( 19 | 256^k - 9^k \). Hence  \(19 | 20^n + 16^n - 3^n - 1 \). Hence it is divisible by \( 17 \times 19 = 323 \). QED

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED

Problem: Prove that if \( 9 | a^2 + b^2 + c^2 \) then 9 divides at least one of \(a^2-b^2\), \(b^2-c^2\) or \( c^2 - a^2 \). Solution: Proof by contradiction. Suppose none of them is divisible by 9. Then \(a^2, b^2, c^2 \pmod 9\) are all different. A square number is \( 0, 1, -2, 4 \pmod 9 \). But \( a^2 + b^2 + c^2  \equiv 1-2+4, 0-2+4, 0+1+4, 0+1-2 \pmod 9 \not \equiv 0 \pmod 9\). QED

Problem: Prove that for \( p > 3 \) prime, \( p^2 \equiv 1 \pmod{24} \). Solution: Consider \( p^2 - 1 = (p-1) (p+1) \). Since \(p > 3\), we know that either \(p-1\) or \( p+1 \) is divisible by 3. Both are divisible by 2. Also, one of them is divisible by 4, since p is either \( -1 \) or \( 1 \pmod 4 \). Hence \( p^2-1 \) is divisible by \( 2 \times 3 \times 4 = 24 \). QED

Problem: Prove that if \( 2n+1 \) and \( 3n+1 \) are both squares, then \( 5n+3 \) is not a prime. Solution: Proof by contradiction. Suppose that there is n such that 5n+3 is prime. Note that \( 4(2n+1) - (3n+1) = 5n+3 \). Let \( 2n+1 = p^2 \) and \( 3n+1 = q^2 \), where \( p, q > 0 \). We have \( (2p-q)(2p+q) = 5n+3 \). Since RHS is a prime, we must have \(2p - q = 1 \) and \( 2p + q = 5n+3 \). Solving for \( q \) we get \( 2q = 5n + 2 \). Substituting, we get \( 2q = q^2 + 2n + 1 \), or \( -2n = (q-1)^2 \). Since RHS is \( \geq 0 \), we can only have equality when \( n= 0 \) and \( q = 1 \). In this case, we have \( 5n + 3 = 8 \) not a prime. QED.

Problem: There are 12 identical coins. There might be one that is a counterfeit, which is either heavier or lighter than the rest. Can you identify the counterfeit (if any) using a balance at most 3 times? Solution: I think this is one of the most difficult variations of the coins weighing problem. The main idea is to "mark" the coins after weighing them. Step 1. Divide the coins into groups of 4. Weigh the first two. If they have the same weight, go to step 4. Otherwise, mark the coins belonging to the heavier group 'H', lighter group 'L', and the unweighted ones 'S'. We know that the counterfeit is either in L or H. Step 2. Now we have 4 Hs, 4 Ls, and 4 Ss. We now form 3 groups: HHL, LLH, and HLS. Step 3. Weigh HHL against HLS. Case 3.1: HHL is lighter than HLS. Then either the L in HHL or the H in HLS is the counterfeit. Simply weigh one of them against S and conclude accordingly. Case 3.2: HHL is heavier than HLS. Then the counterfeit

Problem: Starting from the top-left corner of the chessboard, can we move a knight to the bottom-right corner such that every square is visited once? Solution: No. Each step, the square the knight is in switches color. There are 63 (i.e. odd) steps to make, hence the last square must be of a different color from that of the starting point. However the top-left corner and the bottom-right corner have the same color. Contradiction.

Problem: Find the n-th non-square number. (Adapted from Problem Solving Strategies, Arthur Engel ) If you have CS background, I invite you to come up with an O(log N) solution. Done? Good. Below I present the O(1) approach. Solution: The n-th non-square number is given by \( F(n) = \left \lfloor n + \sqrt{n} + 1/2  \right \rfloor \). Proof: Let G(n) be the same as F(n) except for the floor function. Investigate \( m \neq F(n) \). There is the largest \( n \) s.t. \( F(n) < m \). Hence \( m+1 \leq F(n+1) \). We conclude that \(G(n) < m \) and \(m+1 \leq G(n+1) \). Rearranging the terms and squaring the inequalities, we get: \( n < (m-n-1/2)^2 \) and \( (m-n-1/2)^2 < n+1 \), or \( n - 1/4 < (m-n)^2 - (m-n) < n + 3/4 \). Since the middle term is an integer, we see that \( (m-n)^2 - (m-n) = n \). Simplifying, we get \(m = (m-n)^2\), showing that m is a square. In other words, F(n) skips all squares. Now, we will show that F(n) is the n-th non-squ

Problem: Find prime \(p, q\) which satisfies \(p^2 - 2q^2 = 1\). Solution: We see that \(p = 3, q = 2\) is a solution. We want to show that this is the only solution. Suppose there exists a solution with \( q > 2 \). Rearranging the equation we have \( (p-1)(p+1) = 2q^2 \). Since RHS is divisible by 2, we know that \(p\) must be an odd prime. Hence, both \( p-1 \) and \( p+1 \) are divisible by 2. That means LHS is at least divisible by 4. Hence \( 2q^2 \) must be divisible by 4. This is only possible when \( 2 | q \). Contradiction. QED

\( x^2 + y^2 = z^2 \)