fuck you celena

% --- main.tex ---

%start
\documentclass{article}
\usepackage{hyperref}
\usepackage{multicol}
\usepackage{styles}
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}

\pagestyle{fancy}
\fancyhf{}
\cfoot{\thepage}
\rhead{\thepage}

%title
\lhead{Julian Zhang}
\title{\Large{Big Formula Sheet}\vspace{-3mm}}
\author{Julian Zhang\vspace{-10mm}}
\date{September 2022\vspace{-3mm}}
\begin{document}
\maketitle

\section{Introduction}
this is my attempt to not lose it all

\section{Algebra}
\subsection{Manipulations}

\begin{theorem}
\textbf{Common Algebraic Manipulations:}\vspace{2mm}
    \begin{enumerate}
        \item $(a\pm b)^2=a^2\pm2ab+b^2$ (square of sum/difference)
        \item $(a+b+c)^2=a^2+b^2+c^2+2(ab+ac+bc)$ (square of 3 sums)
        \item $a^2-b^2=(a+b)(a-b)$ (difference of squares)
        \item $(a\pm b)^3=a^3\pm3a^2b+3b^2a\pm b^3$ (cube of sum/difference)
        \item $a^3\pm b^3=(a\pm b)(a^2\pm ab+b^2)$ (sum/difference of cubes)
        \item $a^3+b^3+c^3 = (a+b+c)(a^2+b^2+c^2-ab-ac-bc)$ (cube of 3 sums)
        \item $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b{n-1})$ (generalized difference)
        \item $a^n+b^n=(a+b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b{n-1})$ (generalized sum for odd n)
    \end{enumerate}
\end{theorem}

\subsection{Functions}
\begin{definition}
    A real function defined on $(a,b)$ is said to be $convex$ if
    \[f(\frac{x}{y})\leq\frac{f(x)+f(y)}{2}, x,y\in(a,b)\]
    If the opposite inequality holds, it is called $concave$
\end{definition}\vspace{3mm}
\newpage
\begin{theorem}
\textbf{Function Properties:}\vspace{2mm}
\begin{enumerate}
    \item If $f(X)$ and $g(x)$ are convex functions on $(a,b)$, then so are $h(x)=f(x)+g(x)$ and $M(x)=\max{f(x),g(x)}$
    \item If $f(X)$ and $g(x)$ are convex functions on $(a,b)$ and if $g(x)$ is nondecreasing on $(a,b)$, then it is convex on $(a,b)$
    \item Given two functions $f(x), g(x)$ such that the domain of definition of $f$ contains the range of $g$. the $composition$ of $f$ and $g$ is defined by $(f\circ g)(x):=f(g(x))$
    \item If $f=g$ we write $f^2$ instead of $f\circ f$
\end{enumerate}
\end{theorem}

\subsection{Polynomials}
\begin{definition}
    Broadly speaking, a polynomial is the combination of more than one integer powers. The general form of a polynomial is:
    \[P(x)=a_{n}x^n+a_{n-1}x^{n-1}+\ldots a_{0}\]
\end{definition}\vspace{3mm}

\subsubsection{Root-finding Theorems}
\begin{theorem}
\textbf{Factor Theorem:}\vspace{2mm}

Given a polynomial $P(x)=a_{n}x^n+a_{n-1}+\ldots a_{0}$, $(x-k)$ is a factor of $P(x)$ if and only if $P(k)=0$, or if $k$ is a root of $P$
\end{theorem}\vspace{3mm}

\begin{theorem}
\textbf{Remainder Theorem:}\vspace{2mm}

Given a polynomial $P(x)=a_{n}x^n+a_{n-1}+\ldots a_{0}$, the remainder of $P(x)$ divided by any $x-k$ is $P(k)$
\end{theorem}\vspace{3mm}

\begin{theorem}
\textbf{Fundamental Theorem of Algebra:}\vspace{2mm}

Given a polynomial $P(x)$ of the $n$th degree, $P(x)$ has exactly $n$ complex roots, each of which can be expressed as $a+bi$. Given the $n$ roots $x_{1}, x_{2}, \ldots x_{n}$ of a polynomial $P(x)$, we have that
    \[P(x)=a(x-x_{1})(x-x_{2})\ldots(x-x_n)\]
\end{theorem}

\subsubsection{Coefficient Theorems}

\begin{theorem}
\textbf{Binomial Coefficient Theorem:}\vspace{2mm}
\[(a+b)^2=\binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\ldots+\binom{n}{k}a^{n-k}b^k+\binom{n}{n-1}ab^{n-1}+\binom{n}{n}b^n\]
\end{theorem}

\begin{theorem}
\textbf{Multinomial Coefficient Theorem:}\vspace{2mm}
\[(x_1+x_2+\ldots x_x)^n=\sum_{i_1+i_2+\ldots i_m}^{n}(\frac{n!}{i_1!i_2!\ldotsi_m!})x_1^{i_1}x_2^{i_2}\ldots x_m^{i_m}\]
\end{theorem}

\begin{theorem}
\textbf{Vieta's Theorems:}\vspace{2mm}

Given a polynomial $P(x)=a_{n}x^n+a_{n-1}+\ldots a_{0}$ with $n$ (not necessarily distinct) complex roots, we have that
\[r_1 + r_2 + \cdots + r_n = - \frac{a_{n-1}}{a_n}\]\[r_1r_2 + r_1r_3 + \cdots + r_{n-1}r_n = \frac{a_{n-2}}{a_n}\]\[\vdots\]\[ r_1r_2r_3 \cdots r_n = (-1)^n \frac{a_0}{a_n}.\]
Compactly, this equates to
\[{\displaystyle \sum _{1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n}\left(\prod _{j=1}^{k}r_{i_{j}}\right)=(-1)^{k}{\frac {a_{n-k}}{a_{n}}}}\]

\end{theorem}\vspace{3mm}
Vietas on the cubic $ax^3+bx^2+cx+d$ results in:
\begin{align*}
    r_1+r_2+r_3&=\frac{-b}{a}\\
    r_1r_2+r_1r_3+r_2r_3&=\frac{c}{a}\\
    r_1r_2r_3&=\frac{-d}{a}
\end{align*}

\subsubsection{Linear Function Optimization}
The linear function $ax+by=c$ has a maximized product $xy$ of: $\frac{x^2}{4ab}$ when $x=\frac{c}{2a}, y=\frac{c}{2b}$.
\begin{align*}
y&=\frac{c-ax}{b}\\
x(\frac{c-ax}{b})&=\frac{cx-ax^2}{b}\\
&=-\frac{1}{b}(ax^2-cx)\\
&=-\frac{1}{b}(ax^2-cx+\frac{c^2}{4a^2}-\frac{c^2}{4a^2})\\
&=-\frac{1}{b}(\sqrt{a}x-\frac{c}{2a})^2+\frac{c^2}{4a^2b}\\
\end{align*}
with a vertex at $\frac{c}{2a}$. Plugging in x gives us a y value of $\frac{c}{2b}$.

\subsubsection{Partial Fraction Decomposition}
\vspace{-3mm}
\begin{theorem}
    \textbf{Partial Fraction Decomposition:}\vspace{2mm}
    Given a rational function
    \[f(x)=\frac{1}{L_1(x)L_2(x)+\ldots L_n(x)Q_1(x)Q_2(x)\ldots Q_m(x)}\]
    Where each $L_i$ is a linear factor and each $Q_j$ is an irreducible quadratic, there exist real numbers $A_1, A_2,\ldots A_n, B_1, B_2, \ldots B_m,\ldots C_1, C_2, \ldots C_m$ such that
    \[f(x)=\frac{A_1}{L_1(x)}+\frac{A_2}{L_2(x)}+\ldots\frac{A_n}{L_n(x)}+\frac{B_1x+c_1}{Q_1(x)}+\frac{B_2x+c_2}{Q_2(x)}+\ldots\frac{B_mx+c_m}{Q_m(x)}\]
\end{theorem}

\subsection{Logs}

\begin{theorem}
\textbf{Log Properties:}
$a^b=x\Longleftrightarrow\log_a{x}=b$. Thus, we have:
    \begin{enumerate}
        \item $\log_{b}(a)+\log_{b}(c)=\log_{b}(a\cdot c)$
        \item $\log_{b}(a)-\log_{b}(c)=\log_{b}(\frac{a}{c})$
        \item $\log_{b}(a^n)=n\cdot\log_{b}(a)$
        \item $\log_{a^b}(c)=\frac{1}{b}\cdot log_a(c)$
        \item $a^{\log_a(b)}=b$
        \item $\log_{b}(a)=\frac{\log_{c}(a)}{\log_{c}(b)}$
        \item $\log_{a}(b)\log_{b}(a)=1$
    \end{enumerate}
\end{theorem}


\subsection{Trig}

\begin{definition}
    The three main trigonometric identities and their reciprocals:
    \[\sin(x)=\frac{opp}{hyp}\]
    \[\cos(x)=\frac{adj}{hyp}\]
    \[\tan(x)=\frac{opp}{adj}\]
    \[\csc(x)=\frac{1}{\sin(x)}\]
    \[\sec(x)=\frac{1}{\cos(x)}\]
    \[\cot(x)=\frac{1}{\tan(x)}\]
\end{definition}

\subsubsection{Even-odd Identities}
\[\sin(-x)=-\sin(x)\]
\[\cos(-x)=\cos(x)\]
\[\tan(-x)=-\tan(x)\]

\subsubsection{Period Identities}
\[\sin(x\pm2\pi)=\sin(x)\]
\[\cos(x\pm2\pi)=\cos(x)\]
\[\tan(x\pm\pi)=\tan(x)\]
\[\csc(x\pm2\pi)=\csc(x)\]
\[\sec(x\pm2\pi)=\sec(x)\]
\[\cot(x\pm\pi)=\cot(x)\]

\subsubsection{Conversion Identities}
\[\cos(\frac{\pi}{2}-x)=\sin(x)\]
\[\sin(\frac{\pi}{2}-x)=\cos(x)\]
\[\tan(\frac{\pi}{2}-x)=\tan(x)\]
\[\cot(\frac{\pi}{2}-x)=\tan(x)\]
\[\csc(\frac{\pi}{2}-x)=\sec(x)\]
\[\sec(\frac{\pi}{2}-x)=\csc(x)\]

\subsubsection{Pythagorean Identities}
\[\sin^2\theta+\cos^2\theta=1\]
\[\tan^2\theta+1=sec^2\theta\]
\[\cot^2\theta+1=\csc^2\theta\]

\subsubsection{Sum and Difference Formulas}
\[\sin(x\pm y)=\sin(x)\cos(y)\pm\cos(x)\sin(y)\]
\[\cos(x\pm y)=\cos(x)\cos(y)\mp\sin(x)sin(y)\]
\[tan(x\pm y)=\frac{\tan(x)\pm\tan(y)}{1\mp\tan(x)\tan(y)}\]

\subsubsection{Product to Sum formulas}
\[\sin(x)\sin(y)=\frac{1}{2}[\cos(x-y)-\cos(x+y)]\]
\[\cos(x)\cos(y)=\frac{1}{2}[\cos(x-y)+cos(x+y)]\]
\[sin(x)\cos(y)=\frac{1}{2}[\sin(x+y)+sin(x-y)]\]

\subsubsection{Sum to Product formulas}
\[\sin{x}\pm\sin{y}=2\sin{\frac{x\pm y}{2}}\cos{\frac{x\mp y}{2}}\]
\[\cos{x}+\cos{y}=2\cos{\frac{x+y}{2}}\cos{\frac{x-y}{2}}\]
\[\cos{x}-\cos{y}=-2\sin{\frac{x+y}{2}}\sin{\frac{x-y}{2}}\]

\subsubsection{Double-angle formulas}
\[\sin(2\theta)=2\sin(\theta)\cos(\theta)\]
\[cos(2\theta)=cos^2(\theta)-\sin^2(\theta)=1-2\sin^2(\theta)=2\cos^2(\theta)-1\]
\[\tan(2\theta)=\frac{2\tan(\theta)}{1-\tan^2(\theta)}\]

\subsubsection{Half-angle formulas}
\[\sin(\frac{x}{2})=\pm\sqrt{\frac{1-\cos(x)}{2}}\]
\[\cos(\frac{x}{2})=\pm\sqrt{\frac{1+\cos(x)}{2}}\]
\[\tan(\frac{x}{2})=\frac{1-\cos(x)}{\sin(x)}\]

\subsubsection{Function Laws}
Law of Sines:
\[\frac{a}{\sin(A)}=\frac{b}{\sin(B)}=\frac{c}{\sin(C)}\]
Law of Cosines:
\[a^2=b^2+c^2-2bc\cos(A)\]
Law of Tangents:

\subsubsection{Area of Triangles}
\[\frac{1}{2}ab\sin(C)\]
\[\sqrt{s(s-a)(s-b)(s-c)}\]

\subsubsection{Misc Formulas}
Amplitude Moderation: $a\sin{x}+b\cos{x}=\sqrt{a^2+b^2}\sin(x+\alpha) =\sqrt{a^2+b^2}\cos(x-\beta)$


\subsection{Sequences and Series}

\subsubsection{Mean Quantities}
\begin{definition}
\begin{itemize}
    \item The arithmetic mean of $n$ numbers $a_1,a_2,\ldots,a_n,$
    \[A(a)=\frac{a_1+a_2+\ldots a_n}{n}\]
    \item The geometric mean of $n$ nonnegative real numbers,
    \[G(a)=\sqrt[n]{\frac{1}{a_1}+\frac{1}{a_2}+\ldots\frac{1}{a_n}}\]
    \item The square mean of $n$ real numbers,
    \[S(a)=\frac{\sqrt{a_1^2+a_2^2+\ldots+a_n^2}}{n}\]
    \item The harmonic mean of $n$ real numbers,
    \[H(a)=\frac{1}{\frac{1}{a_1}+\frac{1}{a_2}+\ldots+\frac{1}{a_n}}\]
\end{itemize}
\textbf{We then have the following relationships:}
\begin{itemize}
    \item $A(a)\geq G(a)$ for non-negative real numbers (AM-GM inequality)
    \item $S(a)\geq A(a)$ for real numbers
    \item $G(a)\geq H(a)$ for positive real numbers
\end{itemize}
\end{definition}

\vspace{-5mm}
\subsubsection{Sum Quantities}
\textbf{Sum of Arithmetic Sequence:} $a, a+d, a+2d, \ldots$
\[\sum_{i=1}^{n}a_i=an+\frac{n(n-1)}{2}d\]
\noindent
\textbf{Sum of Geometric Sequences:} $a, ar, ar^2, \ldots$
\[\sum_{i=1}^{n}a_i=\frac{a(1-r^n)}{1-r}\]
\[\sum_{i=1}^{\infty}a_i=\frac{a}{1-r}\]

\subsubsection{Sequences Heuristics}
\begin{enumerate}
    \item For recursive sequences, try and look for patterns
    \item If no recursive formula is given, try writing $a_{n+1}$ in terms of $a_n$, $a_{n-1}$, etc. in inductive fashion.
    \item Try to telescope and cancel out series
\end{enumerate}

\subsection{Sigma Notation}
\subsubsection{Common Sequences}
\begin{itemize}
    \item $1+2+3+\ldots+n=\frac{n(n+1)}{2}$  (triangular numbers)
    \item $1+2+2^2+\ldots2^n=2^{n+1}-1$ (sum of powers of 2)
    \item $1+3+5+\ldots+(2n-1)=n^2$ (sum of odd numbers)
    \item $1^2+2^2+3^2+\ldots+\frac{n(n+1)(2n+1)}{6}$ (sum of squares)
    \item $1^3+2^3+3^3+\ldots+(\frac{n(n+1)}{2})^2$ (sum of cubes)
\end{itemize}

\subsubsection{Sigma Properties}
\begin{definition}
    We use the uppercase Greek letter Sigma to denote summation in the following way:
    \[\sum_{i=1}^{n}x_i=x_1+x_2+\ldots x_n\]
\end{definition}\vspace{3mm}
\begin{theorem}
\textbf{Sigma Properties:}\vspace{2mm}
\[\sum_{k=1}^{n}ca_k=c\sum{k=1}^{n}a_k\]
\[\sum_{k=1}^{n}(a_k+b_k)=\sum{k=1}^{n}a_k+\sum{k=1}^{n}b_k\]
\end{theorem}

\subsubsection{Sigma Methods}
\begin{enumerate}
    \item By grouping/pairing up (derivation of Gaussian Sum)
    \item By elimination (derivation of Geometric Series)
    \begin{align*}
        s&=a+ar+ar^2+\ldots\\
        -rs&=ar+ar^2+ar^3+\ldots\\
    \end{align*}
    \item By telescoping
    \item By recursive counting
\end{enumerate}

\subsection{Inequalities}
\subsubsection{AM-GM}
\begin{theorem}
\textbf{AM-GM:}\vspace{2mm}

NOTE: This is a special case of Jensen's Inequality
\[\frac{x_1 + x_2 + \cdots + x_n}{n} \geq \sqrt[n]{x_1 x_2 \cdots x_n}\]
\end{theorem}

\subsubsection{Cauchy-Schwartz}
\begin{theorem}
\textbf{AM-GM:}\vspace{2mm}

NOTE: This is a special case of Holder's Inequality
\[(a_1^2 + a_2^2 + \cdots + a_n^2)(b_1^2 + b_2^2 + \cdots + b_n^2) \geq (a_1b_1 + a_2b_2 + \cdots + a_nb_n)^2,\]
\end{theorem}

\newpage
\section{Number Theory}
\subsection{Bases}
\begin{definition}
    In base $n$, the largest possible value of a digit is $n-1$. A number $x$ in base $n$ is written as $x_n$, and the numerical value of $\overline{a_{k}a_{k-1}\cdots a_{0}}$ is
   \[a_k n^k+a_{k-1} n^{k-1}+\cdots a_0\]

\end{definition}\vspace{3mm}

\subsection{Divisibility}
\begin{theorem}
\textbf{Fundamental Theorem of Arithmetic:}\vspace{2mm}

Every integer greater than 1 either is a prime itself or is the product
of prime numbers. This product is unique up to the reordering of the factors. The general form is written as
\[ \prod_{i=1}^{n}p_i^{e_i}\]
where $p_i$ are distinct primes and $e_i$ are nonnegative integers.
\end{theorem}\vspace{3mm}

\begin{definition}
    Let $a=\prod_{i=1}^{n}p_i^{d_i}$, and $b=\prod_{i=1}^{n}p_i^{e_i}$, then
    \[\gcd(a,b)=\prod_{i=1}^{n}p_i^{min(d_i, e_i)}\]
    \[\lcm(a,b)=\prod_{i=1}^{n}p_i^{max(d_i, e_i)}\]
\end{definition}\vspace{3mm}

\begin{theorem}
\textbf{Divisibility over Bases}\vspace{2mm}

Given a number $x=\overline{a_{k}a_{k-1}\cdots a_{0}}=a_k n^k+a_{k-1} n^{k-1}+\cdots a_0$, in base n:
\begin{enumerate}
    \item $n-1\mid x$ if and only if $n-1|a_0+a_1+\ldots+a_k$ (sum of digits)

    \item $n\mid x$ if and only if $a_0=0$

    \item $n+1\mid x$ if and only if $n+1|a_0-a_1+\ldots+(-1)^{k}a_k$ (alternating sum)
\end{enumerate}
This can be generalized to factors of $n-1$ and $n+1$.
\end{theorem}

\subsection{Diophantine Equations}
\begin{theorem}
\textbf{Bezout's Identity}\vspace{2mm}

If $d=\gcd(a,b)$ then there always exist integers $x$ and $y$ such that
\[ax+by=d\]
Moreover, the integers of the form $az+bt$ are exactly the multiples of d. Many other number theory theorems, such as Euclid's Lemma and the Chinese Remainder Theorem are results of this identity.
\end{theorem}\vspace{3mm}

Solve $55x-169y=1$ using the Euclidean Algorithm:
\[169=3\times55+4\]
\[55=13\times4+3\]
\[4=1\times3+1\]
Since 4 and 3 are co-prime, we begin back-substitution:
\[4=1\times3+1 \implies 4-1\times3=1\]
\[4=1\times(55-3\times4)=1\implies14\times4=1\times55=1\]
\[14\times(169-3\times55)-1\times55=1\implies14\times169-43\times55=1\]
\[(x, y) = (-1806+169k, -58+55k), k\in\mathbb{Z}\]


\subsubsection{Common Factoring Motifs}
Suppose $n=2^{50}\cdot3^{27}\cdot5^{15}\cdot7^7$
\vspace{-5mm}
\begin{itemize}
    \item Number of positive divisors: $(50+1)(27+1)(15+1)(7+1)$
    \item Number of perfect square divisors: $(\lfloor\frac{50}{2}\rfloor+1)(\lfloor\frac{27}{2}\rfloor+1)(\lfloor\frac{15}{2}\rfloor+1)(\lfloor\frac{7}{2}\rfloor+1)$
    \item Product of positive divisors: $n^{\frac{d}{2}}$, paired
    \item Sum of divisors: $(1+2+2^2+\ldots2^{50})(1+3+\ldots3^{28})(1+5+\ldots5^{15})(1+7+\ldots7^7)$\\
    $=(2^{51}-1)(\frac{3^{28}-1}{2})(\frac{5^{16}-1}{4})(\frac{7^8-1}{6})$
\end{itemize}

\subsection{Mods}
\begin{theorem}
\textbf{Mod Properties:}\vspace{2mm}
Let $a \equiv b (\bmod n)$, and c be a positive integer. Then,
    \begin{enumerate}[label=(\alph*)]
        \item $a+c\equiv b+c$ (mod $n$)
        \item $a-c\equiv b-c$ (mod $n$)
        \item $ac\equiv bc$ (mod $n$)
        \item $a^c\equiv b^c$ (mod $n$)
        \item $a+b\equiv$ ($a$ mod $n$) + ($b$ mod $n$) (mod $n$)
        \item $ab\equiv$ ($a$ mod $n$)($b$ mod $n$) (mod $n$)
        \item If $\gcd(c,n)=1$ and $dc\equiv ec$ (mod $n$), then $d\equiv e$ (mod $n$)
        \item if $k|a, k|b$, and $k|n$, then $\frac{a}{k}\equiv\frac{b}{k}$ (mod $\frac{n}{k}$)
    \end{enumerate}
\end{theorem}

\subsubsection{Prime Mods}
\begin{theorem}
\textbf{Fermat's Little Theorem:}\vspace{2mm}

Let $p$ be a prime number, and $a$ be an integer such that $\gcd(a,p)=1$. We have that:
\[a^{p-1}\equiv 1 \bmod {p}\]
\end{theorem}\vspace{3mm}

\begin{theorem}
\textbf{Wilson's Theorem}\vspace{2mm}

For any prime number $p$, we have that
\[(p-1)!\equiv 1 \bmod p\]
\end{theorem}\vspace{3mm}

\begin{theorem}
\textbf{Euler's Totient Theorem}\vspace{2mm}

Define $\varphi : \mathbb{N} \to \mathbb{N}$ such that $\varphi(n)$ is the number of integers $1\leq k\leq n$ such that $\gcd(k,n)=1$.

Let $n>1$ be a positive integer and $a$ be an integer such that $\gcd(a,n)=1$, then
\[a^{\varphi(n)}\equiv1\bmod n\]
\end{theorem}

\subsubsection{Quadratic Residues}
\begin{definition}
    Given $q$ and $n$ and that the equation $x^2\equiv q(\mod n)$ has a solution, then $q$ is called the \textbf{quadratic residue} modulo n.

    If this equation does not have a solution, then $q$ is called the \textbf{quadratic non-residue } modulo n.

    \begin{itemize}
        \item For example, $x^2\equiv 9\bmod{15}$ has a solution $x=12$, hence 9 is a quadratic residue mod 15.
        \item On the other hand, the equation $x^2\equiv 11\bmod{15}$ has no solution, hence 11 is a quadratic non-residue mod 15.
        \item In simpler terms, an integer $q$ is a quadratic residue mod $n$ if a square can take the form $(nk+q)$ for some positive integer $n$.
    \end{itemize}
\end{definition}

\begin{theorem}
    \textbf{Quadratic Congruences with Prime Mods:}\vspace{2mm}
    If $p$ is a prime, then
    \[x^2\equiv a\bmod(p)\]
    has a solution if and only if
    \[a^{\frac{p-1}{2}}\equiv 1\bmod{p}\]
\end{theorem}

\subsubsection{Chinese Remainder Theorem}
\begin{theorem}
\textbf{Chinese Remainder Theorem:}\vspace{2mm}
    The system of linear congruences:
    \[x\equiv a_1\bmod n_1\]
    \[x\equiv a_2\bmod n_2\]
    \[x\equiv a_3\bmod n_3\]
    \[\ldots\]
    \[x\equiv a_k\bmod n_k\]
    Has a solution if and only if
    \[\gcd(n_i,n_j) | (a_i-a_j)\]
    for every $i!=j$. In such a case, there is a unique solution $mod n$ when $n$ is the least common multiple of $n_1, n_2, \ldots n_k$
\end{theorem}

\textbf{CRT applications:}
Solve the system of modular congruences:
\[x\equiv 1 \bmod 2\]
\[4x\equiv 3 \bmod 5\]
First simplify the second equation to $x\equiv3\times 4\equiv2\mod 5$. Now we have
\[x\equiv 1 \bmod 2\]
\[x\equiv 2 \bmod 5\]
Then let $x=2a+1=5b+2$. A clear solution for $(a,b)$ is $a=3, b=1$. Then, $x=7$ is one solution to the system, so $x\equiv7\bmod 2\times5=10$ is the set of all solutions.

If $m$ and $n$ are not relatively prime, then let $\gcd(m,n)=g$. We split the system as follows:
\[x\equiv a \bmod \frac{m}{g}\]\[x\equiv a \bmod g\]\[x\equiv b \bmod g\]\[x\equiv b \bmod \frac{n}{g}\]
Then, we must check that $a\equiv b\bmod g$. If so, simply ignore the 3rd congruence. Now, we have:
\[x\equiv a \bmod \frac{m}{g}\]\[x\equiv a \bmod g\]\[x\equiv b \bmod \frac{n}{g}\]
Now we have a system of 3 congruences, which we can solve for. If $\gcd(\frac{m}{g}, g)$ is not 1, then repeat the decomposition. Essentially, decompose until we get a system of pairwise relatively prime congruences. Then solve.
\newpage
\section{Combinatorics}
\subsection{Permutations vs Combinations}
\begin{definition}
    The total number of permutations of $k$ elements taken from a set of $n$ elements (without repetition) is commonly denoted $_nP_k$:
    $$_nP_k=n(n-1)(n-2)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$$
    where $n!=1\times 2\times \cdots \times n$ is the factorial of $n$.
\end{definition}\vspace{3mm}

\begin{definition}
The total number of combinations of $k$ elements taken from a set of $n$ elements (without repetition) is commonly denoted $_nC_k$. In fact, combinations are so likely to come up in contests that we have a special notation for them: $\binom{n}{k}$.

$$_nC_k=\binom{n}{k}=\dfrac{n(n-1)(n-2)\cdots(n-k+1)}{k!}=\dfrac{n!}{k!(n-k)!}$$
\end{definition}\vspace{3mm}

\subsection{Stars and Bars}
\begin{theorem}
\textbf{Stars and Bars:}\vspace{2mm}

The number of ways to place $n$ indistinguishable balls into $k$ labelled urns is
$$\binom{n+k-1}{n}=\binom{n+k-1}{k-1}$$

The number of solutions in nonnegative integers to the equation $x_1+x_2+\cdots +x_k = n$ is
$$\binom{n+k-1}{n}=\binom{n+k-1}{k-1}$$
\end{theorem}\vspace{3mm}

\subsection{Expected Value}
\begin{definition}
\textbf{Expected Value:}
Let X be an event, then
\[E(X)=\sum_{i}^{}P(x_i)V(X_i)\]
where $P(x_i)$ is the probability of the event and $V(X_i)$ is the value assigned to the event.

\vspace{2mm}

Properties: \vspace{-2mm}
\begin{enumerate}
    \item (Linearity) Let $a$ be a constant and $X, Y$ be two events, then $E[aX+Y]=aE[X]+E[Y]$.
    \item If $X$ and $Y$ are two independent events, then $E[XY]=E[X]E[Y]$
\end{enumerate}
\end{definition}

\subsection{Other Combo Tools}

\subsubsection{Pigeonhole Principle}
\begin{theorem}
\textbf{Pigeonhole Principle:}\vspace{2mm}

It is impossible to place $n+1$ pigeons in $n$ holes without having one hole contain 2 or more pigeons.

\vspace{2mm}

Pigeonhole Applications: \vspace{-2mm}
\begin{itemize}
    \item From any $n+1$ positive integers we can choose two so that their difference is divisible by n.
    \item If vertices of a triangle are in a rectangle (including the case they are on its sides), then the triangle’s area is at most half of the rectangle’s area.
\end{itemize}
\end{theorem}

\subsubsection{Principle of Inclusion-Exclusion}

\begin{theorem}
Principle of Inclusion-Exclusion (2 variables)
$$|A\cup B| = |A| + |B| - |A\cap B|$$
\end{theorem}

\subsubsection{Recursive Counting}
\begin{itemize}
    \item Suppose the set of objects is $f(n)$. A common trick is to relate $f(n)$ to $f(n-1)$ and possibly other previous terms.
    \item State: A description of an intermediate stage of an event.
    \item Random Walk: Processes in which a person or thing is moving around some universe.
\end{itemize}

\subsubsection{Generating Functions}
Combinatorics problems will often ask to determine a certain sequence of numbers $a_0, a_1, a_2,\ldots$ A common technique
to solve this type of problem is to encode this sequence as a (possibly infinite) polynomial,
\[f(x)=\sum_{k=0}^{\infty}a_k x^k\]
where the solution to the problem is one of the coefficients to the $n$th degree $x$ term.
\newpage

\section{Geometry}

Theorems to memorize: \vspace{-4mm}
\begin{itemize}
    \item Ptolemy's
    \item Ceva's
    \item Stewart's
\end{itemize}
Strategies for geometry: \vspace{-4
mm}
\begin{enumerate}
    \item Draw a diagram with all the information labelled
    \item Draw auxiliary lines
    \item Plug in formulas directly
    \item Use Algebra: Introduce variables, set up equations, calculate something in different ways
    \item Use Coordinates or Vectors
\end{enumerate}

\section{Methods of Proof}
All full-solution math contests will require you not only to know what things are true, but also to prove why they are true. Here are all the proof methods you will need for all high school math contests: \vspace{-3mm}
\begin{itemize}
    \item \textbf{Proof by Contradiction:} Assuming that a false hypothesis is true, and proving that it causes something impossible to be true.

    Example: Proof that $\sqrt{2}$ is irrational
    \item \textbf{Proof by Induction:}
    \begin{enumerate}
        \item Base Case: Proving that something is true for $x=1$
        \item Induction Hypothesis: Assuming that something is true for a certain $x=n$
        \item Induction Step: Using $x=n$ to prove that the same statement is true for $n+1$
    \end{enumerate}
    Example: Proof that $1+2+\ldots+n=\frac{n(n+1)}{2}$
    \item \textbf{Proof by Deduction:} The opposite of induction, deduction takes a general formula and specializes it for a certain case.

    Example: Most geometry problems
    \item \textbf{Proof by Exhaustion:} Splitting a hypothesis into all possible cases, and proving that it holds true for every case.

    Example: Casework
\end{itemize}

\end{document}


% --- styles.sty ---

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[margin=1in]{geometry} % Page Dimensions

\usepackage{cancel}
\usepackage{enumitem}
\setlength{\parskip}{\baselineskip}%
\usepackage[breakable,many]{tcolorbox}
% Math
\usepackage{amsmath, amsthm, amssymb}
\usepackage[inline]{asymptote}
\usepackage{xcolor}

% Allows for hyperlinking
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=magenta,
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% COLORS %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\definecolor{my-blue}{RGB}{93,169,233}
\definecolor{my-pink}{RGB}{238,118,116}
\definecolor{my-green}{RGB}{0,191,0}
\definecolor{my-orange}{HTML}{C78058}
\definecolor{background}{HTML}{f2f2f2}
\definecolor{my-yellow}{HTML}{F6BD60}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% Style Definitions %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% Simple Gray Boxes %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tcbset{simple/.style={
    breakable,
    enhanced,
    outer arc=0pt,
    arc = 0pt,
    colback=background, % Background color
    colframe=background, % Border Color
    coltitle=black, % Title Color
    fonttitle=\bfseries,
    attach title to upper,
    after title={:\ },
    segmentation style={dashed, gray},
    }
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%   Colored Boxes   %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tcbset{orange-labeled/.style={
  breakable,
  enhanced,
  outer arc=0pt,
  arc=0pt,
  colframe=my-orange,
  colback=my-orange!5,
  attach title to upper,
  coltitle=my-orange!200,
  after title={\medbreak},
  }
}

\tcbset{yellow-labeled/.style={
  breakable,
  enhanced,
  outer arc=0pt,
  arc=0pt,
  colframe=my-yellow,
  colback=my-yellow!5,
  attach title to upper,
  coltitle=my-yellow!200,
  after title={\medbreak},
  }
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%   1-Sided Boxes   %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\tcbset{one-sided-green/.style={
    breakable,
    enhanced,
    boxrule=0pt,
    frame hidden,
    borderline west={2pt}{0pt}{my-green},
    colback=my-green!10,
    coltitle=my-green!200,
    after title={:\ },
    sharp corners,
    attach title to upper,
    }
}

\tcbset{one-sided-blue/.style={
    breakable,
    enhanced,
    boxrule=0pt,
    frame hidden,
    borderline west={2pt}{0pt}{my-blue},
    colback=my-blue!10,
    coltitle=my-blue!200,
    after title={:\ },
    sharp corners,
    attach title to upper,
    }
}

\tcbset{one-sided-pink/.style={
    breakable,
    enhanced,
    boxrule=0pt,
    frame hidden,
    borderline west={2pt}{0pt}{my-pink},
    colback=my-pink!10,
    coltitle=my-pink!200,
    after title={:\ },
    sharp corners,
    attach title to upper,
    }
}

\tcbset{one-sided-yellow/.style={
    breakable,
    enhanced,
    boxrule=0pt,
    frame hidden,
    borderline west={2pt}{0pt}{my-yellow},
    colback=my-yellow!10,
    coltitle=my-yellow!200,
    after title={:\ },
    sharp corners,
    attach title to upper,
    }
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%   Box Definitions %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtcolorbox[auto counter]{example}[1][]{
  orange-labeled,
  title=\textbf{Example \thetcbcounter \ ({#1})},
}

\newtcolorbox[auto counter]{custom-big}[1][]{
  yellow-labeled,
  title=\textbf{{#1}},
}

\newtcolorbox{definition}{
    one-sided-green,
    title=\textbf{Definition},
}

\newtcolorbox{theorem}{
    one-sided-blue,
    title=\textbf{Theorem},
}

\newtcolorbox{idea}{
    one-sided-pink,
    title=\textbf{Idea},
}

\newtcolorbox{custom-small}[1][]{
    one-sided-yellow,
    title=\textbf{{#1}},
}

\newtcolorbox[auto counter]{custom-simple}[1][]{
    simple,
    title={#1},
    % add a `\thetcbcounter` to the end if you want to keep track of numberings.
}