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...