\section{Orders Modulo a Prime and Related Stuffs}

	\faka 
	\begin{myitemize}{}
		\item \href{http://web.evanchen.cc/handouts/ORPR/ORPR.pdf}{Order Modulo a Prime - Evan Chen}
		\item \href{https://proofwiki.org/wiki/Zsigmondy's_Theorem}{Another source of the proof of Zsigmondy's Theorem}
	\end{myitemize}
	\faka
	
	
\subsection{Cyclotomic Polynomials}

	\begin{myitemize}
		\item \href{https://pdfs.semanticscholar.org/1445/5f5fbff56e403f72a6f4efad7e1e82b17f49.pdf}{Elementary Properties of Cyclotomic Polynomials - Yimin Ge}
	\end{myitemize}


	\den{Cyclotomic Formulas}{
		For any integer $n$, we have
		\[ X^n - 1 = \prod_{d \mid n} \Phi_d(X)\]
		In particular, if $p$ is a prime then
		\[ \Phi_p(X) = \frac{X^p-1}{X-1} = X^{p-1} + X^{p-2} + \dots + 1\]
	}
	\faka
	
	\den{Mobius Function}{The Mobius function $ \mu $ maps the natural numbers to the set $ \{-1, 0, 1\} $. $ \mu $ can be defined in multiple ways:
		\begin{itemize}
			\item Let $ \zeta_i $ be the primitive roots of $ n^{th} $ cyclotomic polynomial, then $ \displaystyle\mu (n) = \sum{\zeta_i} $ 
			\item \[\mu(n)=
			\begin{cases}
			1	&  \text{ if }	n \text{ is square free and has an even number of prime divisors}\\
			-1	&  \text{ if }	n \text{ is square free and has an odd number of prime divisors}\\
			0	&  \text{ if }	n \text{ has a prime square divisor}
			\end{cases}\]
	\end{itemize}}

	\lem{Sum of Mobius functions of divisors}{Let $ n $ be a positive integer. Then 
		\[\sum_{d|n} \mu(d) =
			\begin{cases}
			1 & \text{ if }n=1\\
			0 & \text{ if }n\ge 2
			\end{cases}
		\]
	}
	
		\proof{The divisors of $ n $ with a prime square divisor will contribute $ 0 $. If $ n=1 $ it's trivial. So let $ n=p_1^{\a_1}p_2^{\a_2}\dots p_k^{\a_k} $. Then, 
			\begin{align*}
				\sum_{d|n} \mu(d) &= \sum_{\{b_{1}\dots b_{t}\} \subseteq \{1, 2 \dots k\}} p_{b_1}\dots p_{b_t}\\[1em]
				&= \binom{k}{0} - \binom{k}{1} + \dots + (-1)^k\binom{k}{k}\\[.5em]
				&=0 
			\end{align*}
		}
	
	\thmbox{https://en.wikipedia.org/wiki/Mobius_inverison_formula}{Mobius Inverison Formula}{Suppose $ F, f:\Z^+ \rightarrow \Z^+ $ are functions such that
		\[F(n)=\sum_{d|n} f(d)\ \implies \ f(n)=\sum_{d|n} \mu(d)\ F\left(\tfrac{n}{d}\right)\]
		\[F(n)=\prod_{d|n} f(d) \ \implies \ f(n)=\prod_{d|n}F\left(\tfrac{n}{d}\right)^{\mu(d)}\]
	}
	
		\proof{
			\begin{align*}
				\sum_{d|n} \mu(d)\ \sum_{t|\tfrac{n}{d}} f(t) &= \sum_{t|n} f(t) \sum_{d|n,\  t|\tfrac{n}{d}} \mu(d)\\[.5em]
				&=\sum_{t|n} f(t) \sum_{d|\tfrac{n}{t}} \mu(d)\\[.5em]
				&=f(n)\quad [\because \autoref{lemma:Sum of Mobius functions of divisors}]
			\end{align*}
		}
	
	
	
	\lem{Prime Divisors of Cyclotomic Polynomials}{If $ a\in \Z $ such that $ \Phi_n(a)\neq 0 $ and for some prime $ p $, \[\Phi_n(a)\equiv 0\ (\text{mod} \ p)\]
		Then either
		\begin{itemize}
			\item $ p\equiv 1\ (\text{mod} \ n) $, or
			\item $ p|n $
	\end{itemize}}

	
	\lem{}{If $ p $ does not divide $ m $, then\[\Phi_{pm}(x)\Phi_m(x)=\Phi_m(x^p)\]}
	
	
\subsection{Quadratic Residue}
	
	\theo{https://en.wikipedia.org/wiki/Quadratic_reciprocity}{Quadratic Reciprocity}{Let $ p $ and $ q $ be two prime numbers. Then using \href{https://en.wikipedia.org/wiki/Legendre_symbol}{Legendre symbol}, we have \[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}}\]}
	
	\lem{2 is a quadratic residue}{\[\left(\frac{2}{p}\right)=\left(-1\right)^{\tfrac{p^2-1}{8}}\]}
		
		\proof{Take $ a\not\equiv 0 \pmod p $. Let $ t_i \equiv ia \pmod p $ the least positive residues for $ 1\le i\le \dfrac{p-1}{2} $. Let $ r_1, r_2\dots r_m $ be the $ t_i $'s that are smaller than $ \dfrac{p-1}{2} $, and let $ s_1, s_2 \dots s_n $ be the $ t_i $'s that are larger than $ \dfrac{p-1}{2} $. Then we have, 
				\[\{r_1, r_2,\dots r_m, p-s_1, p-s_2, \dots p-s_n\} = \{1, 2, \dots \dfrac{p-1}{2}\}\]
			So, multiplying gives us, 
				\[a^{\tfrac{p-1}{2}}\equiv (-1)^n =\left(\frac{a}{p}\right) \pmod p\]
			Plugging in $ a=2 $, we get \autoref{lemma:2 is a quadratic residue}.
		}
	
		
%		\proof{Let $ s=\frac{p-1}{2} $. Consider the equations:
%			\begin{align*}
%			1& = (-1) (-1)\\
%			2& = 2 (-1)^2\\
%			3& = (-3) (-1)^3\\
%			\vdots\\
%			s&=(\pm s)(-1)^s
%			\end{align*}
%			
%			Multiplying all of them gives us:
%			\begin{align*}
%			s!=(-1)2(-3)\dots (\pm s) \times (-1)^{\tfrac{s(s+1)}{2}}
%			\end{align*}
%			From the fact that $ -1 \equiv 2s $ and $ -3 \equiv 2(s-1)\ (mod\ p)$, the right side becomes,
%			\begin{align*}
%			(-1)2(-3)\dots (\pm s) \times (-1)^{\tfrac{s(s+1)}{2}}\equiv 2^s s! (-1)^{\tfrac{s(s+1)}{2}}\ (mod\ p)
%			\end{align*}
%			Which implies after dividing both sides by $ s! $,
%			\begin{align*}
%			1&\equiv 2^s (-1)^{\tfrac{s(s+1)}{2}}\ (mod\ p)\\
%			2^s&\equiv (-1)^{\tfrac{s(s+1)}{2}}\ (mod\ p)
%			\end{align*}
%			And since $ \dfrac{s(s+1)}{2} = \dfrac{p^2-1}{8} $, the lemma is proved.
%		} 
	
		
	\lem{Quadratic non-residue mod infitely many primes}{There are infinitely many primes $p$ for every non-square integers $a$ such that $a$ is a non-quadratic residue $\left(\bmod\ p\right)$}
	
		\proof{We can assume that $ a $ is square free. So $ a=2^sp_1p_2\dots p_r $ for some $ s\in \{0, 1\} \text{ and } r\ge 0 $. Assume the contrary, that there are only finitely many primes, namely $ q_1, q_2 \dots q_m $ for which $ a $ is a quadratic non residue. We have three cases:\\
		
		\textbf{\textit{Case 1:}} $ s=1, r=0 $. In that case, we have infinitely many prime number, $ q $ such that $ q\equiv 3 \pmod 8 $, and $ x^2\not\equiv a \pmod q $ using \autoref{lemma:2 is a quadratic residue}.\\
		
		\textbf{\textit{Case 2:}} $ s=1, r>0 $. Take $ t $, a quadratic non-residue $ \pmod p_r $. Consider the following congruences:
			\begin{align*}
				x&\equiv 1 \pmod {q_i}	\text{ for all } q_i\\
				x&\equiv 1 \pmod 8\\
				x&\equiv 1 \pmod {p_i}	\text{ for } i=1, 2\dots r-1\\
				x&\equiv t \pmod {p_r}
			\end{align*}
		By Chinese Remainder Theorem and Dirichlet theorem, it follows that there exists infinitely many prime numbers $ N $ that satisfies all of the congruences. Now using Jacobi symbol and Law of Reciprocity, it follows that,
			\begin{align*}
				\left(\frac{2}{N}\right)&=1\\
				\left(\frac{p_i}{N}\right)&=1 \text{ for } i=1, 2\dots r-1\\
				\left(\frac{q_i}{N}\right)&=1 \text{ for all } q_i\\
				\left(\frac{p_r}{N}\right)&=-1
			\end{align*}
		Therefore, $ \displaystyle \left(\frac{a}{N}\right)=-1 $
		Which is a contradiction, since $ q_i \not| N $.\\
	
		\textbf{Case 3:} $ s=0, r>0 $, this is similar to the above case.}
	
	
	
	\newpage\subsubsection{Quadratic Residue}
	
	
	\theo{}{}{Let $ p $ be an odd prime. Then, 
		
		\begin{enumerate}
			\item The product of two quadratic residue is a quadratic residue.
			\item The product of two quadratic non-residue is a quadratic residue.
			\item The product of a qudratic residue and a quadratic non-residue is a quadratic non-residue
	\end{enumerate}}              
	
	
	\theo{}{}{For an odd prime $ p $ and any two integers $ a, b $, we have $  \left( \frac{ab}{p} \right) =  \left( \frac{a}{p} \right)  \left( \frac{b}{p} \right) $}
	
	
	\theo{}{Euler's Criterion}{Let $ p $ be an odd prime. Then, \[a^\frac{p-1}{2} \equiv  \left( \frac{a}{p} \right) (mod\ p)\]}
	
	\theo{}{}{Let $ (a, b)=1 $. Then every prime divisors of $ a^2+b^2 $ is either $ 2 $ or a prime of the form $ 4k+1 $.}
	
	\theo{}{Gauss's Criterion}{Let $ p $ be a prime number and $ a $ be an integer coprime to $ p $. Let $ \mu(a) $ be the number of integers $ x \in \{a, a*2, \dots a*\frac{p-1}{2}\} $ such that $ x (mod\ p) > \frac{p}{2} $. Then \[ \left( \frac{a}{p} \right) = -1^{\mu(a)} \]}
	
	
	\theo{}{}{The smallest quadratic non-residue of an odd prime $ p $ is a prime which is less than $ \sqrt{p} + 1 $}
	
	\theo{}{Quadratic Residue Law}{Using the usual Legendre Symbol, for two prime numbers $p,q$ we have: \[\left( \frac{p}{q}\right)\left( \frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]}
	
	
	
	\den{Jacobi Symbol}{Let $ a, n=p_1^{\a_1}\dots p_k^{\a_k} $. We define Jacobi symbol as 
		\[\left( \frac{a}{n} \right) = \prod_{i=1}^{k} \left( \frac{a}{p_i} \right)^{\a_i}\]}
	
	\begin{note}
		Jacobi symbol is not as accurate as Legendre symbol. $ \left( \frac{a}{n} \right) = -1 $ means that $ a $ is a quadratic non-residue of $ n $, but $ = 1 $ doesnt necessarily mean that $ a $ is a quadratic residue of $ n $.
	\end{note}
	
	\theo{}{}{Let $ a, n=p_1^{\a_1}\dots p_k^{\a_k} $, then $ a $ is a quadratic residue of $ n $ iff it is a quaadratic residue of every $ p_i^{\a_i} $.}
	
	
	\theo{}{}{\hl{If an integer is a quadratic residue of every prime, then it is a square.}}
	
	
	
	
	\subsection{Zsigmondy's Theorem}
	
		\begin{myitemize}
			\item \href{http://pommetatin.be/files/zsigmondy_en.pdf}{Zsigmondy's Theorem's Proof, has some useful lemmas}
		\end{myitemize}
	
		\theo{}{Zsigmondy's Theorem}{Let $ a, b\in \N $ such that $ \gcd(a, b)=1 $ and $ n\in \N, n>1 $. Then there exists a prime division of $ a^n-b^n $ that does not divide $ a^k-b^k $ for all $ 1\le k< n $ \emph{except} in the following cases:
			\begin{itemize}
				\itemsep-.5em
				\item $ 2^n-1^n $
				\item $ n=2 $ and $ a+b $ is a power of $ 2 $.
			\end{itemize}}
		
		
	
	
\subsection{Problems}
	
	\prob{https://artofproblemsolving.com/community/c6h1288391}{CGMO 2016 P3}{E}{Let $m$ and $n$ are relatively prime integers and $m>1,n>1$. Show that:There are positive integers $a,b,c$ such that $m^a=1+n^bc$ , and $n$ and $c$ are relatively prime.}
	
	
	\prob{https://artofproblemsolving.com/community/c6h33810p209770}{ISL 2004 N4}{EM}{Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$.}
	
		\solu{\input{dump/isl2004n4}}
