Posts

Discovered New Theorem while solving Chinese Remainder Theorem

I was working through some Chinese Remainder Theorem (CRT) problems today (9/24/22), using a new technique introduced in the UKMT Introduction to Number Theory Book. And I noticed a pattern: 9a \equiv 1 \pmod 7 \rightarrow a = 4 7b \equiv 1 \pmod 9 \rightarrow b = 4 Which is cool. But it continues: 7c \equiv 1 \pmod 5 \rightarrow c = 3 5d \equiv 1 \pmod 7 \rightarrow d = 3 And: 35e \equiv 1 \pmod 33 \rightarrow e = 17 33f \equiv 1 \pmod 35 \rightarrow f = 17 Each modular inverse for these pairs were the same! I formed a conjecture, and proved it as a new theorem: Theorem : The solutions a, b to the modular equivalences (n-1)a \equiv 1 \pmod {n+1} (n+1)b \equiv 1 \pmod {n-1} for positive even integers n satisfy a = b = \frac{n}{2}. Update  (12/25/23): More intuitive understanding of Chinese Remainder Theorem (CRT) process. I was looking back at this post, and realized that I had forgotten how the Chinese Remainder Theorem process ...

Cyclic Quattrocento (Fall 2021 AMC 12B #24)

Image
Fall 2021 AMC 12B #24 Problem:  Triangle ABC has side lengths AB = 11, BC=24, and CA = 20. The bisector of \angle{BAC} intersects \overline{BC} in point D, and intersects the circumcircle of \triangle{ABC} in point E \ne A. The circumcircle of \triangle{BED} intersects the line AB in points B and F \ne B. What is CF? Solution:  We can create a diagram to try to find unique relationships in this problem. By angle chasing in the cyclic quadrilateral ABEC given that AE is the angle bisector of \angle{BAC} we can find that \angle{BAE} = \angle{CAE} = \angle{BCE} = \angle{CBE}. This means that triangle BCE is isosceles and BE = CE, which may be useful later on. Now, we can focus on CF , which is the length we want to find. We can see that ACF has a cevian CB, so we can use Stewart's Theorem (we will "derive" it with the law of cosines here) to solve for CF in terms of other side lengths. We can let \angle{ABC} = \theta which means...

Flower Petals (Fall 2021 AMC 12B #15)

Image
Fall 2021 AMC 12B #15 Problem:  Three identical square sheets of paper each with side length 6 are stacked on top of each other. The middle sheet is rotated clockwise 30^\circ about its center and the top sheet is rotated clockwise 60^\circ about its center, resulting in the 24-sided polygon shown in the figure below. The area of this polygon can be expressed in the form a-b\sqrt{c}, where a, b, and c are positive integers, and c is not divisible by the square of any prime. What is a+b+c? Solution:  We can see that the resulting shape is a "regular" 24-sided polygon with equal side lengths, and equal interior angles. So we can take a "petal" of the polygon that consists of 3 adjacent vertices, find the area, and multiply by 12. The key here is to find the area of the petal by subtracting areas from a corner of the original square paper. From this diagram of a petal inside a 3 \times 3 corner of a square, we can see that each petal has an area...

Don't Be Intimidated (Fall 2021 AMC 12B #5, 8, 13)

Image
Fall 2021 AMC 12B #5 Problem:  Call a fraction \frac{a}{b}, not necessarily in the simplest form, special if a and b are positive integers whose sum is 15. How many distinct integers can be written as the sum of two, not necessarily different, special fractions? Solution:  We can list out all the special fractions: \{\frac{1}{14},\frac{2}{13}, \frac{3}{12}, \frac{4}{11},\frac{5}{10},\frac{6}{9},\frac{7}{8},\frac{8}{7},\frac{9}{6},\frac{10}{5},\frac{11}{4},\frac{12}{3}, \frac{13}{2}, \frac{14}{1}\}. Simplifying, we have the fractions \{\frac{1}{14},\frac{2}{13}, \frac{1}{4}, \frac{4}{11},\frac{1}{2},\frac{2}{3},\frac{7}{8},\frac{8}{7},\frac{3}{2},2,\frac{11}{4},4, \frac{13}{2}, 14\}. We see that we can only add fractions with the same denominator , so we only need to focus on \{\frac{1}{4},\frac{1}{2},\frac{2}{3},\frac{3}{2},2,\frac{11}{4},4, \frac{13}{2}, 14\}. From the whole numbers \{2,4,14\}, we can achieve 4, 6, 16, 8, 18, 28. From the fractions with deno...

Complete Residue System modulo m (Fall 2021 AMC 12A #25)

Fall 2021 AMC 12A #25 Problem:  Let m\geq 5 be an odd integer, and let D(m) denote the number of quadruples (a_1, a_2, a_3, a_4) of distinct integers with 1\leq a_i \leq m for all i such that m divides a_1+a_2+a_3+a_4. There is a polynomial q(x) = c_3x^3+c_2x^2+c_1x+c_0 such that D(m) = q(m) for all odd integers m\geq 5. What is c_1? Solution:  First, we must find a way to account for the number of ordered quadruples (a_1, a_2, a_3, a_4) such that m divides a_1+a_2+a_3+a_4. We know that there are (m)(m-1)(m-2)(m-3) total ordered quadruples since all elements must be distinct. First we can list out the sums of m quadruples of the form (a_1+n, a_2+n, a_3+n, a_4+n) where n takes on the values from 0 to m-1 and all elements of the quadruple are modulo m. This means that the m quadruples have the same difference between consecutive elements modulo m. If we let the sum S = a_1+a_2+a_3+a_4, we have $(a_1, a_2, a_3, a_4) \Rightarr...