Title: Part II / Number Theory
Tags: Distribution::of::Prime::Numbers Quadratic::Forms Prime::numbers::and::Congruences Quadratic::Reciprocity Primality::Testing Continued::Fractions

Q: Lemma. If \(I = \{\lambda_1 a_1 + \dots + \lambda_n a_n | \lambda_1 , \dots , \lambda_n \in \mathbb{Z}\}\) and \(a_1, \dots, a_n \in \mathbb{Z}\) not all 0. Then \(\exists ! d > 0, d\in \mathbb{Z}\) such that \(I = d\mathbb{Z}\)
A: Let d be the least positive element of I. \(d \in I \implies d = \lambda_1 a_1 + \dots + \lambda_n a_n \implies d \mathbb{Z} \subseteq I\). If \(a \in I\), we can write \(a = qd +r, 0 \leq r < d\). Then \(r = a - qd \in I\). Since d is minimal, we must have \(r = 0\)

Q: Theorem. Fundamental Theorem of Arithmetic. Any \(n \in \mathbb{Z}, n>1\), admits an expression as a product of primes, unique up to re-ordering.
A: Existence: use induction on n. If n is prime we are done. Otherwise \( n = ab, a,b > 1\) and both are less than n so by induction they can be written as a product of primes.
Uniqueness: again by induction. Suppose \(n = \prod_{i=1}^k p_i^{r_i} = \prod_{j=1}^l q_j^{s_j}, p_i, q_j \text{ prime }\) and \(r_i, s_j \geq 1\). Then \(p_1 | n\), so we have \(p_1 | q_j\) for some j, but then \(q_j\) is prime so \(p_1 = q_j\) therefore \[\frac{n}{p_1} = p_1^{r_1 -1}\prod_{i=2}^k p_i^{r_i}= q_j^{s_j - 1} \prod_{m=1, m\neq j}^l q_m^{s_m}\] By induction these expressions are the same up to relabelling, therefore the two expressions for n are the same.

Q: Definition. Suppose given an algorithm with input an integer N>1. We say the algorithm is polynomial-time if [...]
A: \(\exists b,c > 0\) s.t. the algorithm terminates always after at most \(b(\log N)^c\) elementary operations.

Q: Lemma. Let \(a \in \mathbb{Z}\). Then TFAE:
1) (a, N) = 1
2)\(\exists b \in \mathbb{Z}\) s.t. \(ab \equiv 1 \mod N\)
3) \(a + N \mathbb{Z}\) generates the additive group
A: 1 -> 2: If \((a,N) = 1, \exists b,y \in \mathbb{Z}\) s.t. \(ab + yN = 1 \implies ab \equiv 1 \mod N\)
2 -> 1: If \(ab \equiv 1 \mod N, \exists y \in \mathbb{Z}\) s.t. \(ab + yN = 1 \implies (a,N) = 1\)
2 -> 3: Note \(1 + N \mathbb{Z}\) generates \(\mathbb{Z} / N \mathbb{Z}\), as if \(b \in \mathbb{Z}, b > 0\), then \(b + N \mathbb{Z} = (1 + N \mathbb{Z}) + \dots + (1 + N \mathbb{Z})\). Suppose \(\exists b \in \mathbb{Z}\) s.t. \(ab \equiv 1 \mod N\). WLOG \(b > 0\). Then \(1 + N\mathbb{Z} = (a + N \mathbb{Z}) + \dots + (a + N\mathbb{Z})\) b times so \(a + N \mathbb{Z}\) is a generator.
3 -> 2: If \(a + N \mathbb{Z}\) is a generator, \(\exists b \in \mathbb{Z}, b > 0\) s.t. \(ab + N \mathbb{Z} = (a + N\mathbb{Z}) + \dots + (a + N \mathbb{Z}) = 1 + N\mathbb{Z} \implies ab \equiv 1 \mod N\)

Q: Corollary. Let G be a cyclic group of order N. Then G contains exactly \(\phi(N)\) elements of exactly order N.
A: G is isomorphic to \(\mathbb{Z} /N \mathbb{Z}\). The elements of exact order N are the generators. This equals \(\phi(N)\) by definition.

Q: Theorem. Euler-Fermat. Suppose \(a,N \in \mathbb{Z}, N > 1, (a,N) = 1\). Then \[a^{\phi(N)} \equiv 1 \mod N\]
A: Lagrange's theorem: If H is a group of order m, and \(h \in H\), then \(h^m = e\). \(H = (\mathbb{Z} / N \mathbb{Z})^{\times}, m = \phi(N), (a+N\mathbb{Z})^{\phi(N)} = a^{\phi(N)} + N \mathbb{Z} = 1 + N \mathbb{Z} \implies a^{\phi(N)} \equiv 1 \mod N\)

Q: Corollary. Fermat's Little Theorem. Let p be a prime, \(a \in \mathbb{Z}\). Then \[a^p \equiv a \mod p\]
A: If \(p | a\), then \(a^ p \equiv a \equiv 0 \mod p\). If \(p \not{|} a\) then \((a,p) = 1 \implies a^{\phi(p)} = a^{p-1} \equiv 1 \mod p \implies a^p \equiv a \mod p\)

Q: Theorem. Chinese Remainder Theorem. Suppose given integers \(m_1 , \dots, m_k\) satisfying \(\forall i, m_i > 1\) and \(\forall i \neq j, (m_i , m_j) = 1\). Suppose given integers \(a_1 , \dots , a_k\) then the system of congruences \[\begin{cases} x \equiv a_1 \mod m_1 \\ \vdots \\ x\equiv a_k \mod m_k\end{cases}\]has a solution \(x \in \mathbb{Z}\) which is uniquely determined modulo \(M = \prod_{i=1}^k m_i\)
A: Uniqueness: If x,y are two sollutions then \(x \equiv y \mod m_i \forall i \implies \forall i, m_i | (x-y) \implies M | (x-y) \implies x\equiv y \mod M\) because the \(m_i\) are pairwise coprime
Existence: Define \(M_i = \prod_{j \neq i} m_j\) then \((m_i, M_i) = 1 \implies \exists x_i, y_i \in \mathbb{Z}\) such that \(x_i m_i + y_i M_i = 1\). In particular \(y_i M_i \equiv 1 \mod m_i\) and \(y_i M_i \equiv 0 \mod m_j \; \;j\neq i\) \[\implies x = \sum_{i=1}^k a_i y_i M_i\] is a solution

Q: Theorem. Suppose given integers \(m_1 , \dots , m_k\) satisfying \(\forall i, m_i > 1\) and \(\forall i \neq j (m_i , m_j) = 1\). Then the function \[\theta : \frac{\mathbb{Z}}{M \mathbb{Z}} \to \frac{\mathbb{Z}}{m_1 \mathbb{Z}} \times \dots \times \frac{\mathbb{Z}}{m_k \mathbb{Z}} \]\[a + M \mathbb{Z} \mapsto (a+m_1\mathbb{Z}, \dots, a+m_k \mathbb{Z})\]is a ring isomorphism (i.e. it is bijective and respects addition and multiplication)
A: \(\theta\) is bijective by Chinese Remainder Theorem.
The addition and multiplication in the RHS group is defined component wise, so we only need that the map \[\frac{\mathbb{Z}}{M \mathbb{Z}} \to \frac{\mathbb{Z}}{m_i \mathbb{Z}}\]\[a + M\mathbb{Z} \mapsto a+ m_i \mathbb{Z}\]
respects addition and multiplication

Q: Corollary. In the same case as Chinese Remainder Theorem, the \(\theta\) restricts to a group isomorphism \[\left ( \frac{\mathbb{Z}}{M \mathbb{Z}}\right )^{\times} \to \left ( \frac{\mathbb{Z}}{m_1 \mathbb{Z}}\right )^{\times} \times \dots \times \left ( \frac{\mathbb{Z}}{m_k \mathbb{Z}}\right )^{\times}\]
A: \(\theta\) will restrict to an isomorphism between the multiplicative groups \[\{a+M\mathbb{Z} \in \frac{\mathbb{Z}}{M \mathbb{Z}} | a + M \mathbb{Z} \text{ has a multiplicative inverse}\} \to \{(a_1 + m_1 \mathbb{Z}, \dots , a_k + m_k \mathbb{Z}) \in \prod_i \left(\frac{\mathbb{Z}}{m_i \mathbb{Z}}\right) | (a_1 +m_1 \mathbb{Z}, \dots, a_k + m_k \mathbb{Z}) \text{ has a multiplicative inverse}\}\]where the source and target match up by definition.

Q: Definition. Let \(\mathbb{N} = \{1, 2 , \dots\}, f : \mathbb{N} \to \mathbb{C}\) a function. We say that
- f is multiplicative if [...]
- totally multiplicative if [...]
A: \(\forall m,n \in \mathbb{N}\) such that \((m,n) = 1, f(mn) = f(m)f(n)\); \(\forall m,n \in \mathbb{N} \; f(mn) = f(m) f(n)\)

Q: Corollary. \(\phi\) is multiplicative
A: \(\phi(m) = \# (\mathbb{Z} / m \mathbb{Z})^{\times}\). We know that \[\# (\mathbb{Z} / mn \mathbb{Z})^{\times} = \# (\mathbb{Z} / m \mathbb{Z})^{\times} \cdot \# (\mathbb{Z} / n \mathbb{Z})^{\times}\]as the groups are isomorphic so we are done.

Q: Proposition. Let \(f : \mathbb{N} \to \mathbb{C}\) be a multiplicative function, and define \(g : \mathbb{N} \to \mathbb{C}\) by \(g(n) = \sum_{d | n} f(d)\). Then g is also multiplicative
A: Let \(m,n \in \mathbb{N}, (m,n) = 1\). Must show \(g(mn) = g(m)g(n)\) \[g(mn) = \sum_{d|mn} f(d) = \sum_{d_1 | m, d|2 |n} f(d_1 d_2) = \sum_{d_1 | m, d_2 | n} f(d_1)f(d_2) = (\sum_{d_1 | m} f(d_1)) \times (\sum_{d+2 | m} f(d_2))\]We can split the sum as m,n are coprime.

Q: Proposition. (1) If p is a prime, \(k \in \mathbb{N}\), \(\phi(p^k) = p^k - p^{k-1}\)
(2) \(\phi(N) = N \prod_{p | N, \text{ prime}} (1 - 1/p)\)
(3) \(\forall n \in \mathbb{N}, \sum_{d|N} = \phi(d) = N\)
A: (1) If \(1 \leq a \leq p^k\), then \((a, p^k) = 1 \iff \text{ a is not a multiple of p}\) so the result follows.
(2) Write \(N = \prod_{i=1}^r p_i^{k_i}\), where the \(p_i\) are distinct primes and \(r_i \geq 1\). \[\phi(N) = \phi(\prod_{i=1}^k p_i^{k_i}) = \prod_{i=1}^r \phi(p_i^{k_i}) = \prod(p_i^{k_i} - p_i^{k_i - 1})\](3) Define \(g(n) = \sum_{d | n} \phi(d)\), multiplicative function \(\mathbb{N} \to \mathbb{C}\)
WTS: \(g(n) = n \forall n \in \mathbb{N}\)We just need to show this for prime powers as it is multiplicative. \[g(p^k) = \sum_{d|p^k} \phi(d) = \phi(1) + \phi(p) + \dots + \phi(p^k) = 1 + (p-1) + (p^2 - p) + \dots + (p^k - p^{k-1}) = p^k\]

Q: Theorem. Lagrange's Theorem. Let p be a prime, \(f(X) = a_n X^n + \dots + a_0 \in \mathbb{Z}/ p\mathbb{Z} [X]\) a polynomial with \(a_n \not \equiv 0 \mod p\). Then \(f(X) \equiv 0\) has at most n solutions in \(\mathbb{Z} / p \mathbb{Z}\)
A: Induction on n. If \(n = 0, f(X) = a_0\) is never 0 by definition of the polynomial
Now suppose \(n > 0\). If there are no solutions to \(f(X) = 0\), we're done. Suppose instead \(\exists a \in \mathbb{Z} / p \mathbb{Z}\) s.t. \(f(a) \equiv 0 \mod p\).
Note \(\forall j \geq 1, X^j - a^j = (X-a)(X^{j-1} + aX^{j-2} + \dots + a^{j-1})\) so \(f(X) = f(X) - f(a) = \sum_{j=0}^n [a_j X^j - a_j a^j] = \sum_{j=1}^n a_j(X^j - a^j) = (X-a)g(X)\) where g is a polynomial in the same group with leading term \(a_n X^{n-1}\) with \(a_n \not \equiv 0 \mod p\). Suppose \(b \in \mathbb{Z} / p \mathbb{Z}\) is a solution of \(f(X) = 0\). Then \(0 \equiv f(b) \equiv (b-a) g(b) \mod p\). Then either \(b \equiv a \mod p\) or \(b - a \not \equiv 0 \mod p \implies b - a \text{ has a multiplicative inverse} \implies g(b) \equiv 0 \mod p\)
By induction, \(\exists \leq n-1, b \in \mathbb{Z} / p \mathbb{Z}\) s.t. \(g(b) \equiv 0 \mod p \implies \exists \leq n , b \in \mathbb{Z}/p\mathbb{Z}\) s.t. \(f(b) \equiv 0 \mod p\)

Q: Theorem. Let p be a prime. Then \((\mathbb{Z} / p \mathbb{Z})^{\times}\) is cyclic
A: Let \(G = (\mathbb{Z} / p \mathbb{Z})^{\times}\). \(\# G = p-1\)
We know \(\sum_{d | p - 1} \phi(d) = p-1\). We also know that if \(g \in G\), then the order of g divides \( p -1\). Therefore \( p -1 = \sum_{d | p-1} N_d\) where \(N_d = \# \{g \in G | \text{ order of g is d} \}\)
\(G \text{ cyclic} \iff N_{p-1} > 0\)
Suppose for contradiction that G is not cyclic, so \(N_{p-1} = 0\). Since \(p - 1 = \sum_{d | p -1} \phi(d) = \sum_{d | p-1 , d \neq p-1} = N_d\) we must have \(N_d > \phi(d)\) for some \(d|p-1\). Choose \(a \in G\) of order d.
Consider the subgroup \( \langle a \rangle \leq G\). Then \(\langle a \rangle = \{1, a , \dots , a^{d-1}\}\) is cyclic with d elements.
We saw that any cyclic group of d elements has \(\phi(d)\) elements of order d. Since \(N_d > \phi(d)\), there must exists some elements \(b \in G\) of order d such that \( b \not \in \langle a \rangle \)
The elements of \(\langle a \rangle\) have order dividing d \(\implies \)they are all solutions to \(X^d - 1 = 0\) in \(\mathbb{Z} / p \mathbb{Z}\)
b is also a solution to this polynomial congruence so \(1, a ,\dots, a^{d-1}, b\) give d+1 distinct solution, contradicting Lagrange's theorem.

Q: Definition. If p is a prime, and \(a \in \mathbb{Z}\),  we say that a is a primitive root modulo p if  [...]
A: \((a,p) = 1\) and \(a \mod p \in (\mathbb{Z} / p \mathbb{Z})^{\times }\) generates this group

Q: Lemma. Let p be an odd prime, \(k \in \mathbb{N}, x,y \in \mathbb{Z}\). Then:
(1) If \(x \equiv 1 + p^k y \mod p^{k+1}\), then \(x^p \equiv 1 + p^{k+1}y \mod p^{k+2}\)
(2) \((1+py)^{p^k} \equiv 1 + p^{k+1}y \mod p^{k+2}\)
A: (1) Write \(x = 1 + p^k y + p^{k+1}z\) for some z. Then \(x^p = (1+p^ky)^p + \sum_{j=1}^p {p \choose j} (1+p^k y)^{p-j}(p^{k+1}z)^j\)
Claim: Each summand is divisible by \(p^{k+2}\). Clear for \(j < p, j=p\) we have \(p^{p(k+1)}\) which divides it.
So we can assume that \(x = 1+p^k y\). Then \(x^p = (1+p^ky)^p = 1+p^{k+1}y + \sum_{j=2}^p {p \choose j} (p^ky)^j\)
Claim: Each summand is divisible by \(p^{k+2}\)
If \(2 \leq j < p\), then \(p^{1+2k}|\text{summand}\). We have \(2k+1 \geq k+2 \iff k\geq 1\)
If \(j = p\), then \(p^{pk} | \text{summand}\) . We have \(pk \geq k+2 \iff (p-1)k \geq 2\). This holds because we assume that \(p \geq 3\).
(2) Apply the first part k times.

Q: Lemma. Let p be an odd prime, and let \(a \in \mathbb{Z}\) be a primitive root mod p. If \(a^{p-1} \not \equiv 1 \mod p^2\), then \(a \mod p^k\) generates \((\mathbb{Z}/ p^k \mathbb{Z})^{\times}\) for all \(k \geq 1\).
A: We can assume that \(k \geq 2\). Then \(\# (\mathbb{Z}/ p^k \mathbb{Z})^{\times} = (p-1)p^{k-1}\).
Let \(d = \text{ order of a} \mod p^k\). Then \(d | (p-1)p^{k-1}\) and we must show \(d = (p-1)p^{k-1}\).
There's a surjective homomorphism \((\mathbb{Z}/ p^k \mathbb{Z})^{\times} \to (\mathbb{Z}/ p \mathbb{Z})^{\times}\) with \(b + p^k\mathbb{Z} \mapsto b + p \mathbb{Z}\). \(a + p^k \mathbb{Z}\) under this homomorphism is \(p - 1\). Therefore \(p-1 | d\), so \(d = (p-1)p^j\) for some \(0 \leq j \leq k-1\).
Let \(x = a^{p-1}= 1+py\), for some \(y \in \mathbb{Z}\) with \((y,p) = 1\).
By assumption \(x \not \equiv 1 \mod p^2\). If \(k = 2\), this already means that we must have \(d \neq p-1\), hence \(d = p(p-1)\).
Now assume that \(k \geq 3\). Then by lemma 1.24, \(x^{p^{k-2}} \equiv 1 + p^{k-1}y \mod p^k\). In particular, \(a^{(p-1)p^{k-2}}\not \equiv 1 \mod p^k\).
This shows that \(d \not{|} p^{k-2}(p-1)\) and so we must have \(d = p^{k-1}(p-1)\) as required.

Q: Theorem. Let p be an odd prime number. Then \((\mathbb{Z}/ p^k \mathbb{Z})^{\times}\) is cyclic for all \(k \geq 1\)
A: Let a be a primitive root modulo p. If \(a^{p-1} \not \equiv 1 \mod p^2\) we are done, so assume it is congruent to 1. Let \(b = (1+p)a\). We compute \[b^{p-1} = (1+p)^{p-1}a^{p-1} \equiv 1 + (p-1)p \equiv 1-p \mod p^2\]In particular, b is a primitive root module p and \(b^{p-1} \not \equiv 1 \mod p^2\) so b generates the group for all k.

Q: Definition. Let p be a prime, \(a \in \mathbb{Z}\). Then if \((a,p) = 1\) we say that a is a quadratic residue modulo p if [...] and a quadratic non-residue otherwise.
A: the polynomial congruence \(X^2 - a= 0\) has a solution in \(\mathbb{Z} / p \mathbb{Z}\)

Q: Lemma. If p is an odd prime, then there are \(\frac{p-1}{2}\) quadratic residues mod p, and \(\frac{p-1}{2}\) non residues.
A: Consider the map \(\sigma\), \((\mathbb{Z} / p \mathbb{Z})^{\times} \to (\mathbb{Z} / p \mathbb{Z})^{\times}\) with \(x \mapsto x^2\). We need to show the size of the image is \((p-1)/2\). Enough to show that each set \(\sigma^{-1}(x^2)\) has exactly two elements. If \(x,y \in (\mathbb{Z} / p\mathbb{Z})^{\times}\) and \(x^2 \equiv y^2 \mod p\) then \((x-y)(x+y) \equiv 0 \mod p\) so either \(x \equiv y \) or \(x \equiv -y\). So \[\sigma^{-1}(x^2) = \{\pm x\}\]

Q: Definition. Legendre Symbol. For p an odd prime, a an integer, we write \[[...]\]
A: \left ( \frac{a}{b} \right ) = \begin{cases} 0 & p | a \\ 1 & p \not{|} a \text{ and a is a quadratic residue} \\ -1 & p \not{|} a \text{ and a is a quadratic non-residue} \end{cases}

Q: Proposisition. Euler's Criterion. If p is an odd prime, \(a \in \mathbb{Z}\), then \[\left ( \frac{a}{p} \right ) \equiv a^{(p-1)/2} \mod p\]
A: If \(p | a\) then both sides are 0 mod p. So assume \( p \not{|} a\). If \(a \equiv x^2 \mod p\) then the Legendre symbol is 1, and \(a^{(p-1)/2} \equiv x^{p-1} \equiv 1 \mod p\) by Euler-Fermat.
If a is a quadratic non-residue then the Legendre symbol is -1. We have \((a^{(p-1)/2})^2 \equiv 1 \mod p\) so \(a^{(p-1)/2} \equiv \pm 1 \mod p\) and we need to show it is not 1.
We know \(x^{(p-1)/2} - 1\equiv 0\) has at most \((p-1)/2\) solutions in \((\mathbb{Z} / p \mathbb{Z})\) by Lagrange's theorem.
We know that there are \(\geq (p-1)/2\) solutions given by the quadratic residues. So if a is a quadratic non-residue, then \(a^{(p-1)/2} \equiv - 1 \mod p\)

Q: Corollary. If \(a,b \in \mathbb{Z}\) then \[\left( \frac{ab}{p} \right ) = \left( \frac{a}{p} \right )\left( \frac{b}{p} \right )\]
A: We have \[(ab)^{(p-1)/2} = a^{(p-1)/2} b^{(p-1)/2}\]

Q: Corollary. We have \(\left ( \frac{-1}{p} \right ) = (-1)^{(p-1)/2} = \begin{cases} 1 & p\equiv 1 \mod 4 \\ -1 & p \equiv -1 \mod 4\end{cases}\)
A: First equality is Euler's criterion, second equality is trivial.

Q: Theorem. Gauss' Lemma. Let p be an odd prime, \(a \in \mathbb{Z}, p \not{|}a \). Then \(\left ( \frac{a}{p}\right) = (-1)^{\mu}\) where \(\mu = \# \{j \in \mathbb{Z} | 0 < j < p/2 , \langle ja \rangle < 0\}\).
We have for p an odd prime and a an integer, there is a unique integer \(b \in a + p\mathbb{Z}\) such that \(-p/2 < b < p/2\). We write \(\langle a \rangle = b\)
A: Consider \(((p-1)/2)! = \prod_{j=1}^{(p-1)/2} j\). How is this related to \(\prod_{j=1}^{(p-1)/2} aj\)? If \(0 < j < p/2, 0 < k < p/2\) then \(-p/2 < \langle aj \rangle < p/2\) so there's a unique sign \(\epsilon_j \in \{\pm 1\}\) such that \(0 < \epsilon_j \langle aj \rangle < p/2\). Moreover if \(j \neq k\), then \(\epsilon_j \langle aj \rangle \neq \epsilon_k \langle ak \rangle\). Why? If \(\epsilon_j \langle aj \rangle = \epsilon_k \langle ak \rangle\) then \(\langle aj \rangle = \pm ak \mod p \implies j \equiv \pm k \mod p\). This can only happen if j = k because we are assuming they are both positive. Contradiction.
So the integers \(\epsilon_j \langle aj \rangle, j = 1,\dots, (p-1)/2\) are distinct and live in \(\{1, \dots , (p-1)/2\}\). Therefore \[\prod_{j=1}^{(p-1)/2} aj = a^{(p-1)/2} (\frac{p-1}{2}) !\]\[\prod_{j=1}^{(p-1)/2} aj \equiv \prod_{j=1}^{(p-1)/2} \langle aj \rangle \equiv \prod_{j=1}^{(p-1)/2} (\epsilon_j \cdot j) \mod p \equiv \left [ \prod_{j=1}^{(p-1)/2} \epsilon_j\right ] (\frac{p-1}{2})!\]\[\implies a^{(p-1)/2} = \prod_{j=1}^{(p-1)/2} \epsilon_j \mod p\]By Euler's criterion, LHS \(\equiv \left ( \frac{a}{p} \right ) \mod p\)
RHS \( = (-1)^{\mu'}\) where \(\mu' = \# \{ j | \epsilon_j = -1\}\) so \(\mu' = \mu\) by definition.

Q: Theorem. Law of Quadratic Reciprocity. Suppose p.q are distinct odd primes. Then \[\left (\frac{p}{q} \right )\left (\frac{q}{p} \right ) = (-1)^{((p-1)/2)((q-1)/2)}\]
A: By Gauss' Lemma, \(\left (\frac{p}{q} \right ) = (-1)^{\# A}\) where \(A = \{(b,c) \in \mathbb{Z}^2 | 0 < b < p/2 , -p/2 < qb - pc < 0\}\). Similarly, \(\left ( \frac{q}{p} \right ) = (-1)^{\# B} = (-1)^{\# C}\), \(B = \{(b,c) \in \mathbb{Z}^2 | 0 < b < q/2, -q/2 < pb - qc < 0\}\), \(C = \{(b,c) \in \mathbb{Z}^2 | 0 < c < q/2, 0 < qb - pc < q/2\}\). Let \(S = \{(b,c) \in \mathbb{Z}^2 | 0 < b < p/2, 0 < c < q/2\}\). Then \(\# S = (\frac{p-1}{2}) (\frac{q-1}{2})\). Claim: A,C are disjoint subsets of S. If \((b,c) \in A\), then \(0 < b < p/2\) and \(pc < qb \implies c > \frac{q}{p}b > 0\) and also \(pc < qb + p/2 \implies c < \frac{q}{p}b + \frac{1}{2} < \frac{q+1}{2} \implies c < q/2\) as \(c \in \mathbb{Z}\) so \((b,c) \in S\).
The proof that \(C \subset S\) is the same.
A,C are disjoint as \(qb - pc < 0\) in A and \(qb - pc > 0\) in C.
We need to show that \((-1)^{\#A + \# C} = (-1)^{\# S}\) we will show that \(\# (S \setminus (A \cup C))\) is even. Let \(X = \{(b,c) \in S | qb - pc < -p/2\}\) and \(Y = \{(b,c) \in S | qb - pc > q/2\}\). So \(X,Y \subset S\) and disjoint and \(S \setminus (A \cup C) = X \cup Y\).
Claim \(\# X = \# Y\). This will show that \(\# S \setminus (A \cup C)\) is even. Let's write \(f:S \to S\) be the function \[f(b,c) = (\frac{p+1}{2} - b , \frac{q+1}{2} - c)\] This is bijective. We have that \(f(X) \subset Y\), \(f(Y) \subset X\).

Q: Definition. Let \(N \in \mathbb{N}\) be odd, and let \(a \in \mathbb{Z}\). Then we define the Jacobi symbol [...]
A: \((\frac{a}{N}) = \prod_{i=1}^k (\frac{a}{p_i})\), where \(p_1 , \dots, p_k\) are primes with \(N = p_1p_2 \dots p_k\) and the symbols on the RHS are Legendre symbols.

Q: Lemma. Let \(N,M \in \mathbb{N}\) be odd, \(a,b \in \mathbb{Z}\). Then:
(1) If \(a \equiv b \mod N\), then \(\left ( \frac{a}{N}\right) = \left ( \frac{b}{N}\right)\)
(2) \(\left ( \frac{ab}{N}\right) = \left ( \frac{a}{N}\right)\left ( \frac{b}{N}\right)\)
(3) \(\left ( \frac{a}{MN}\right) = \left ( \frac{a}{M}\right)\left ( \frac{a}{N}\right)\)
A: Write \(M = p_1 \dots p_k, N = q_1 \dots q_k\) with \(p_i, q_j\) primes
(1) \(\left ( \frac{a}{N}\right) = \prod_j \left ( \frac{a}{q_j}\right) = \prod_j \left ( \frac{b}{q_j}\right) = \left ( \frac{b}{N}\right)\) as if \(a \equiv b \mod N\) then \(a \equiv b \mod q_j \forall j\)
(2) \(\left ( \frac{ab}{N}\right) = \prod_j \left ( \frac{ab}{q_j}\right) = \prod_j \left ( \frac{a}{q_j}\right) \left ( \frac{b}{q_j}\right) = \left ( \frac{a}{N}\right)\left ( \frac{b}{N}\right)\)
(3) \(\left ( \frac{a}{MN}\right) = \prod_i \left ( \frac{a}{p_i}\right) \prod_j \left ( \frac{a}{q_j}\right) = \left ( \frac{a}{M}\right)\left ( \frac{a}{N}\right)\)

Q: Proposition. If \(N \in \mathbb{N}\) is odd, then \[\left ( \frac{-1}{N}\right) = (-1)^{\frac{N-1}{2}}\]\[\left ( \frac{2}{N}\right) = (-1)^{\frac{N^2 - 1}{8}}\]
A: The identities hold when N is prime: true for \(\left ( \frac{-1}{N}\right)\). If \(N = 8k+r\), then \(\frac{N^2 - 1}{8} = 8k^2 + 2kr + \frac{r^2-1}{8}\) so only the remainder matters and we can check and see that it matches with \(\left ( \frac{2}{N}\right)\)
To get the general case we need to show that if \(M \in \mathbb{N} \) is odd then
(a) \((-1)^{\frac{M-1}{2} + \frac{N-1}{2}} = (-1)^{\frac{MN-1}{2}}\) and (b)\((-1)^{\frac{M^2-1}{2} + \frac{N^2-1}{2}} = (-1)^{\frac{(MN)^2-1}{2}}\) which can be done by considering \((M-1)(N-1) \mod 4\) and \((M^2 - 1)(N^2 - 1) \mod 64\)

Q: Theorem. Law of Quadratic Reciprocity for Jacobi Symbols. Let \(M,N \in \mathbb{N}\) be odd. Then \[\left ( \frac{M}{N} \right ) = (-1)^{\frac{M-1}{2} \frac{N-1}{2}} \left ( \frac{N}{M} \right )\]so if \((M,N) = 1\) the regular law holds.
A: Let \(M = p_1 \dots p_k, N = q_1 \dots q_l\) for \(p_i, q_j\) primes. Then \[\left ( \frac{M}{N} \right ) = \prod_i \prod_j\left ( \frac{p_i}{q_j} \right ) = \prod_i \prod_j (-1)^{\frac{p_i - 1}{2} \frac{q_j - 1}{2}} \left ( \frac{q_j}{p_i} \right ) = (-1)^{\sum_i \frac{p_i - 1}{2} \sum_j\frac{q_j - 1}{2}} \left ( \frac{N}{M} \right )\]We need to show that \((\sum_i \frac{p_i - 1}{2})(\sum_j \frac{q_j- 1}{2}) \equiv \frac{M-1}{2} \frac{N-1}{2} \mod 2\)
We showed in the proof for the -1 and 2 Jacobi symbols that \(\sum_i \frac{p_i - 1}{2} \equiv \frac{M-1}{2} \mod 2\) and similarly for N so we are done by multiplying these together.

Q: Definition. A binary quadratic form is [...] If f is a binary quadratic form and \(N \in \mathbb{Z}\) we say f represents N if[...]
A: a polynomial \(f(x,y) = ax^2 + bxy + cy^2\) where \(a,b,c \in \mathbb{Z}\).; \(\exists m,n \in \mathbb{Z}\) s.t.  \(f(m,n) = N\)

Q: Definition. (1) A unimodular change of variables is one of the form[...](2) If \(f(x,y), g(x,y)\) are binary quadratic forms, we say they are equivalent if [...]
A: \(X = \alpha x + \gamma y, Y = \beta x + \delta y\), where \(\alpha, \beta, \gamma, \delta \in \mathbb{Z}\) and \(\alpha \delta - \beta \gamma = 1\). Equivalently, one of the form \((X,Y) = (x,y)A\) where \(A \in SL_2 (\mathbb{Z})\); there exists a unimodular change of variables such that \(g(x,y) = f(X,Y)\)

Q: Definition. The discriminant of a binary quadratic form \(f(x,y) = ax^2 + bxy + xy^2\) is [...]
A: \(\text{disc }f = b^2 - 4ac\)

Q: Lemma. Let f,g be equivalent binary quadratic forms. Then:
(1) f,g represent the same integers
(2) \(\text{disc} f = \text{disc} g\)
A: (1)We can write \(g(X,Y) = f(\alpha x + \gamma y , \beta x + \delta y)\). If g represents N, then f represents N.
We're done by symmetry.
(2) Let \(M_f\) be the matrix associated to f, so \(f(x,y) = (x,y)M_f (x,y)^T\) and \(\det M_f = ac - b^2 /4 = -1/4\text{disc} f\)
We have \[g(x,y) = f((x,y)A) = (x,y) A M_f A^T(x,y)T\]\[\implies M_g = AM_f A^T \implies \det M_g= \det M_f \implies \text{ discriminants are equal}\]

Q: Lemma. Let \(d \in \mathbb{Z}\). Then there exists a binary quadratic form f with \(\text{disc} f = d \iff d \equiv 0,1 \mod 4\)
A: (\(\implies\)) If \(f \leftrightarrow (a,b,c)\) then \(\text{disc}f = b^2 - 4ac \equiv b^2 \mod 4\) so we are done
(\(\impliedby\)) If \(d \equiv 0 \mod 4\) take \(f = x^2 - \frac{d}{4}y^2\)
If \(d \equiv 1 \mod 4\), take \(f = x^2 +xy + \frac{1-d}{4}y^2\)

Q: Definition. Let f be a binary qudratic form. Then we say f is positive/negative definite if [...]. It is indefinite if [...]
A: \(\forall (u,v) \in \mathbb{R}^2 - \{0\}, f(u,v) >0 / f(u,v) < 0\); there are pairs where it can be either positive or negative.

Q: Proposition. Let \(f(x,y) = ax^2 + bxy + cy^2\) be a binary quadratic form. Then:
(1) If \(d<0\), then \(a \neq 0\). If \(a > 0\) f is positive definite, if \(a < 0\) it is negative definite
(2) If \(d>0\), then f is indefinite
(3)If \(d = 0\) then \(\exists l,m,n \in \mathbb{Z}\) s.t. \(f = l(mx + ny)^2\)
A: \(4af(x,y) = (2ax +by)^2 - dy^2\)
(1) \(d = b^2 - 4ac < 0 \implies a\neq 0\). Then RHS is positive definitve.
(2) If \(a \neq 0\) and \(d > 0\) then RHS is indefinite so f is indefinite
If \(c \neq 0\) and \(d > 0\) then the same argument shows that f is indefinite
If \(a = c = 0\) then \(f(x,y) = bxy\) is indefinite as \(b \neq 0\)
(3) If \(d = 0\) then \(b^2 = 4ac\). Write \(a = a_1 (a_2)^2\) where \(a_1, a_2 \in \mathbb{Z}\) and \(a_1\) is squarefree.
Then \(b^2 = 4a_1 a_2^2c \implies (2a_2)^2 | b^2 \implies 2a_2 | b\)
Then \((b/2a_2)^2 = a_1 c \implies a_1 | (b/2a_2)^2 \implies a_1 |(b/2a_2) \implies 2 a_2 a_1 | b\)
Then \(f(x,y) = a_1 a_2 x^2 + bxy + cy^2 = a_1 (a_2 x + \frac{b}{2a_1 a_2} y)^2 + (c - a_1 \frac{b^2}{4a_1^2 a_2^2})y^2 = a_1 (a_2 x + \frac{b}{2a_1 a_2y})^2 + (c - \frac{b^2}{4a})y^2\)
If \(a = 0\) then \(b = 0\) so \(f(x,y) = cy^2\).

Q: What can the actions of \(SL_2(\mathbb{Z})\) on quadratic forms be broken up into?
A: Translation: \[T_{\lambda} =\left ( \begin{matrix}1 & 0 \\ \lambda & 1 \end{matrix}\right ): (a,b,c) \mapsto (a, 2\lambda a + b, c + \lambda b + \lambda^2a)\]Reflection: \[S =\left ( \begin{matrix}0 & 1 \\ -1 & 0 \end{matrix}\right ): (a,b,c) \mapsto (c,-b, a)\]

Q: Definition. Let \(f = (a,b,c)\) be a PDBQF. We say that f is reduced if [...]
A: \(-a < b \leq a \leq c\) and if \(a=c\) then \(b \ge 0\)
Back Extra: Equivalently if \(|b| \leq a \leq c\) and if either inequality is an equality, then \(b \ge 0\)

Q: Proposition. Every PDBQF is equivalent to a reduced one.
A: Start with \(f = (a,b,c)\) and consider the following algorithm:
If \(a<c\), then replace f by \(S \cdot f\)
If \(|b| > a\) replace f by \(T_{\pm 1} \cdot f\) depending on the sign of b.
Repeat until \(a \leq c \) and \(|b| \leq a\)
This terminates, considering \(a + |b|\), if \(a > c\) then \(a \) is replaced by c and \(|b|\) is unchanged so the quantity decreases
If \(|b| > a\) then a doesn't change but \(|b| \) decreases.
After running this we have replaced f with an equivalent form \((a,b,c)\) satisfying \(|b| \leq a \leq c\)
We're done except if \(|b| = a\) or \(a = c\)
If \(a = c\), then \(f = (a,b,a)\)If \(b \geq 0\) f is reduced. Otherwise \(S \cdot f\) is reduced
If \(a<c\) but \(|b| = a\) then either \(f = (a,a,c)\) is redcued or \(f= (a,-a,c) \) which is not reduced, in which case \(T_1 \cdot f = (a,a,c)\) is reduced.

Q: Lemma. If \(f = (a,b,c)\) is reduced PDBQF then \(|b| \leq a \leq \sqrt{\frac{|\text{disc} f|}{3}}\) and \(b \equiv \text{disc }f \mod 2\)
A: Have \(|b| \leq a \leq c\) as f reduced.
\(|\text{disc}f| = 4ac - b^2 \geq 4a^2 - a^2 = 3a^2 \implies a \leq \sqrt{\frac{|\text{disc} f|}{3}}\)
We have \(\text{disc}f \equiv b^2 \equiv b \mod 2\)

Q: Corollary. If p is prime and \(p \equiv 1 \mod 4\) then p is represented by \(x^2 + y^2\)
A: Since \(p \equiv 1 \mod 4\), \(\left (\frac{-1}{p} \right ) = 1\) and we can find \(k,l \in \mathbb{Z}\) such that \(k^2 = -1 + lp \implies (2k)^2 = -4 + 4lp \implies -4 = (2k)^2 - 4lp\)
The binary quadratic form \(f = (p,2k,l)\) has discriminant -4 and is PD.
We know that f is equivalent to a reduced form of discriminant -4.
\(x^2 + y^2\) is the unique such form, so f is equivalent to \(x^2 + y^2\)
We have \(f(1,0) = p \implies f \) represents p.
Equivalent forms represent the same integers, so \(x^2 + y^2\) must also represent p.

Q: Corollary. If \(d \in \mathbb{Z}, d < 0, d\equiv 0 \text{ or } 1 \mod 4\) then there are only finitely many reduced \(PDBQF\)s of discriminant d.
A: If f is reduced then there are only finitely many possibilies for a,b. Since \(d = b^2 - 4ac\), c is determined by a and b

Q: Definition. Let \(d \in \mathbb{Z}, d<0, d \equiv 0 \text{ or }1 \mod 4\). Then we write \(h(d)\) for [...] We call \(h(d)\) [...]
A: the number of equivalence classes of PDBQFs of discriminant d.; the class number of d.

Q: Definition. Let \(f(x,y)\) be a binary quadratic form, \(N \in \mathbb{Z}\). Then we say f properly represents N if[...]
A: \(\exists(n,m)\in \mathbb{Z}^2\) s.t. \(f(m,n) = N\) and \(gcd(m,n) = 1\)

Q: Lemma. If f,g are equivalent binary quadratic forms, then they properly represent the same integers.
A: Suppose \(g = A \cdot f, A = (\alpha, \beta; \gamma,\delta)\in SL_2(\mathbb{Z})\), and \(g(m,n) = N\), with \(\gcd (m,n)= 1\). We'll show f properly represents N. This is enough, by symmetry. We have \(N = g(m,n) = (A \cdot f)(m,n) = f((m,n)A) = f(\alpha m + \gamma n, \beta m + \delta n)\). We need to check that \(\gcd(\alpha m + \gamma n, \beta m + \delta n) = 1\).
We have  \((\alpha m + \gamma n, \beta m + \delta n) = (m,n) A \implies (m,n) = (\alpha m + \gamma n, \beta m + \delta n)A^{-1}, A^{-1} \in SL_2 (\mathbb{Z})\)
Therefore \(\gcd(\alpha m + \gamma n, \beta m + \delta n) | \gcd (m,n) = 1\)

Q: Lemma. Let \(f = (a,b,c)\) be a reduced PDBQF. Then:
(1) \(a \le c \le a +c - |b|\)
(2) \(f(1,0) = a, f(0,1) = c\) and \(\exists \epsilon \in \{\pm 1\}\) s.t. \(f(1, \epsilon) = a + c - |b|\)
(3) If m,n are non-zero integers with \(\gcd (m,n) = 1\), then \(f(m,n) \geq a + c - |b|\)
A: (1) f reduced \(\implies c \geq a \geq |b| \implies a - |b| \geq 0 \implies c+a-|b| \geq c\)
(2) \(f(x,y) = ax^2 + bxy + cy^2 \implies f(1,0) = a, f(0,1 = c), f(1,\epsilon) = a +c + b\epsilon\) choose \(\epsilon\) s.t. \(\epsilon \beta < 0\)
(3)m,n non-zero integers. If \(|m| \geq |n| \), then \(f(m,n) = am^2 + bmn + cn^2 \geq am^2 - |b|m^2 + cn^2 = (a - |b|)m^2 + cn^2 \geq a - |b| + c\) as \(m^2 , n^2 \geq 1\)
If \(|m| \le |n|, f(m,n) = am^2 + bmn + cn^2 \ge am^2 + (c - |b|)n^2 \geq a+c - |b|\)

Q: Theorem. Every PDBQF is equivalent to a unique reduced form.
A: We knew every PDBQF is equivalent to a reduced form. We need to show that if \(f = (a,b,c), g = (a', b', c')\) are equivalent forms, then they are equal.
f,g properly represent the same integers \(\implies\)the lists of properly represented integers in increasing order for f,g are the same.
So \(a,a,c,c,a+c-|b|, a+c - |b|, \dots = a', a', c',c', a' + c' - |b'|, a'+c'- |b'|\) \(\implies a=a', c=c', |b| = |b'|\)
If \(b = 0\), then \(f=g\) and we're done.
Suppose \(b \neq 0\), after possibly swapping f,g we can further suppose \(b > 0\) and \(b' -b < 0\)
then \(f = (a,b,c), g =(a, -b,c) = A \cdot f\) for some \(A \in SL_2(\mathbb{Z})\) and f,g are reduced. In particular \(c > a > b\)
We have  \(g(1,0) = a = (A \cdot f)(1,0) = f((1,0)A)\)
If \((m,n)\in \mathbb{Z}^2, \gcd (m,n) = 1,\) and \(f(m,n) = a\) then \((m,n) = (\pm 1,0)\)
Hence \((1,0)A = (\pm1,0)\)
Similarly \(g(0,1) = c =f((0,1)A)\)
Then also \((m,n) = (0, \pm1)\) hence \((0,1)A= (0,\pm1)\)
Therefore \(A = (\pm 1 , 0 ; 0, \pm1)\) but \(\det A = 1\) so \(A = \pm I\)
\(A \cdot f = f\) therefore \(g = A \cdot f = f\)

Q: Lemma. Let f be a binary quadratic form, \(N \in \mathbb{Z}\). Then f properly represents N \(\iff\)f is equivalent to a form \((N,b,c) \) for some \(b,c \in \mathbb{Z}\)
A: (\(\impliedby\))we know proper representation is preserved under equivalence. \(Nx^2 + bxy + cy^2\) properly represents N take \((x,y) = (1,0)\)
(\(\implies\)) Suppose \(f(m,n) = N, \gcd(m,n) =1 \). We can fine \(u,v \in \mathbb{Z}\) s.t. \(um + vn = 1\) \[\implies A = (m,n; -v,u) \in SL_2(\mathbb{Z})\]Let \(g = A \cdot f\). Then \(g(1,0) = f((1,0)A) = f(m,n) = N\)

Q: Theorem. Let \(d\in \mathbb{Z}, d<0, d\equiv 0,1 \mod 4, N \in \mathbb{N}\). Then TFAE
(1) N is properly represented by a PDBQF of discriminant d
(2)The equation \(x^2 = d\) has a solution in \(\mathbb{Z} / 4N \mathbb{Z}\)
A: (1) \(\implies\)(2): By the lemma, there exists a form \((N,b,c)\) of discriminant d. Therefore \(b^2 - 4Nc = d\) and \(b^2 \equiv d \mod 4N\)
(2) \(\implies\)(1): We can find \(b,c \in \mathbb{Z}\) such that \(b^2 = d + 4Nc\). Then the form \((N,b,c)\) has discriminant d. This is positive definite as \(d < 0\) and \(N > 0\)

Q: Lemma. (1) Let p be an odd prime, \(a \in \mathbb{Z}\). Then if \(\left ( \frac{a}{p} \right ) = 1\), then \(x^2 = a\) has a solution in \(\mathbb{Z}/ p^k \mathbb{Z} \; \; \forall k \geq 1\)
A: We use induction on \(k \geq 1\). Holds when k=1 by assumption. Suppose \(\exists b \in \mathbb{Z}\) such that \(b^2 \equiv a \mod p^k\), so \(\exists c \in \mathbb{Z}\) such that \(b^2 = a + p^k c\)
Then \((b+p^kx)^2 = a + p^k(c + 2bx) + p^{2k}x^2\)
We'll be done if we can choose x so that \(2bx \equiv -c \mod p\)
This is possible provided \((p,2b) = 1\)
Since  \(\left ( \frac{a}{p} \right ) = 1, a \not \equiv 1 \mod p \implies b \not \equiv 0 \mod p\)
\(p \text{ odd }\implies 2b \not \equiv 0 \mod p\)

Q: Lemma. Let \(a \in \mathbb{Z}\), and suppose \(a \equiv 1 \mod 8\). Then the equation \(x^2 = a\) has a solution in \(\mathbb{Z}/ 2^k \mathbb{Z} \; \; \forall k \geq 1\)
A: Use induction on \(k \geq 1\). Holds when \(k \leq 3\) by assumption. So suppose \(\exists b \in \mathbb{Z}\) s.t. \(b^2 \equiv a \mod 2^k\), where \(k \geq 3\)
\(\exists c \in \mathbb{Z}\) s.t. \(b^2 = a + 2^k c\)
If c even, then \(b^2 \equiv a \mod 2^{k+1}\) so assume c is odd.
Note that b is odd, as \(b^2 \equiv a \equiv1 \mod 2\)
Then \((b+2^{k-1})^2 = a + 2^k(b+c) + 2^{2(k-1)}\)
b + c is even and since \(2k-2 \ge k+1\) for \( k \ge 3\) we're done

Q: Lemma. If \(x \in \mathbb{Z}, x \ge 2\) then \(\pi(x) \ge \frac{\log x}{2 \log 2}\)
A: We have \(x =\#\{1,2,\dots, x\}\)
Let \(p_1 , \dots , p_r\) be the primes \(\le x\)(so \(\pi (x) = r\))
Any \(1 \leq N \leq x\) can be written uniquely in the form \(N = p_1^{a_1}\dots p_r^{a_r} M^2\), where \(a_i \in \{0,1\}, M \leq \sqrt{x}\)
So we get \(x \le 2^r \sqrt{x} \implies 2^{\pi(x)} \ge \sqrt{x}\)

Q: Proposition. (1)\(\sum_{p \text{ primes}} \frac{1}{p}\) diverges
(2)\(\prod_{p \text{ primes}}(1- \frac{1}{p})^{-1}\) diverges
A: (1) \(\iff \)(2): We use Taylor series expanion \[-\log(1-x) = \sum_{k \ge 1} \frac{x^k}{k}\]valid \(x \in (-1,1)\)
We have \(\log \prod_{p \le x} (1-1/p)^{-1} = \sum_{p \le x} - \log(1-1/p) = \sum_{p\leq x, k \ge 1} \frac{p^{-k}}{k} = \sum_{p\le x} \frac{1}{p} + \sum_{p \le x, k \ge 2} \frac{p^{-k}}{k}\)
Claim: the sums \(\sum_{p \le x, k \ge 2} p^{-k}/k\) are bounded as \(x \to \infty\)
We have \(\sum_{p\le x, k \ge2} \frac{p^{-k}}{k} \le \sum_{p \le x, k \ge 2} p^{-k} = \sum_{p \le x} \frac{1}{p^2} \frac{1}{1-1/p} = \sum_{p \le x} \frac{1}{p(p-1)}\)
\[\implies \prod_{p \le x} (1-1/p)^{-1} \le \sum_{n \in \mathbb{N}} \frac{1}{n^2} < \infty\]
(2) \(\prod_{p \le x} (1-1/p)^{-1} = \prod_{p \le x} \sum_{k \ge 0} p^{-k} = \sum_{k_1, \dots ,k_r \ge 0} p_1^{-k_1} \dots p_r^{-k_r}\) where \(p_1, \dots ,p_r\) are the primes \(\le x\)
Note: any \(1 \le N \le x\) has the form \(p_1^{k_1} \dots p_r^{k_r}\) for some \(k_i \ge 0\). So \(\prod_{p\le x} (1-1/p)^{-1} \ge \sum_{1 \leq N \leq x} \frac{1}{N}\)
This diverges as \(x \to \infty\)(its the harmonic series)

Q: Definition. The Riemann zeta function is \[[...]\]
A: \zeta(s) = \sum_{n=1}^{\infty} n^{-s}

Q: Proposition. Let \(s \in \mathbb{C}\), and suppose \(\Re(s) > 1\). Then \(\zeta(s)\) converges absolutely.
A: \(\sum_{n=1}^{\infty}|n^{-s}| = \sum_{n=1}^{\infty} |\exp(-\sigma \log n) \exp(-it\log n)| = \sum_{n=1}^{\infty} n^{-\sigma}\)
This converges \(\iff \sigma >1\)

Q: Proposition. let \(s \in \mathbb{C}, \sigma > 1\). Then \[\zeta(s) = \prod_{\text{p prime}} (1-1/p^s)^{-1}\]More precisely, \(\zeta(s) = \lim_{x \to \infty} \prod_{\text{p prime}, p \leq x} (1-1/p^s)^{-1}\). Moreover \(\zeta(s) \neq 0\)
A: Formally we can expand \[\prod_p (1-1/p^s)^{-1} = \prod_p (1+ p^{-s} + p^{-2s} + \dots) = \sum_{r \geq} \sum_{p_1 < \dots < p_r} \sum_{k_1 , \dots , k_r \geq 1}(p_1^{k_1} \dots p_r^{k_r})^{-s} = \sum_{n=1}^{\infty}n^{-s}\]with the last equality from FTA.
Now arguing rigorously. Suppose \(X > 2\), \(p_1 , \dots ,p_r\) are the primes \(\le X\)
Then \[\prod_{p \le X} (1-1/p^s)^{-1} = \prod_{p \le X}(1+p^{-s} + p^{-2s} + \dots) = \sum_{n \in S_X}n^{-s}\]where \(S_X = \{n \in \mathbb{N} | \text{ if } p|n, \text{ p prime, then } p \le X\}\)
Therefore \[|\zeta(s) - \prod_{p \leq X}(1-1/p^s)^{-1}| \le \sum_{n \in \mathbb{N} - S_X} n^{-\sigma} \le \sum_{n > X} n^{-\sigma} \to 0 \text{ as }X \to \infty\]since \(\sum_{n=1}^{\infty}n^{-\sigma}\) is convergent.
We next show that \(\zeta(s) \neq 0\)
Consider \(|\zeta(s)\prod_{p \le X} (1-1/p^s)| = |\prod_{p > X}(1-1/p^{-s})^{-1}| = |1+ \sum_{n \in T_X} n^{-s}|,\)  where \(T_X = \{n > 1 | \text{ if p prime, } p|n, \text{ then } p > x\} \subset \{n > X\}\)
So \(|\zeta(s) \prod_{p \le X}(1-1/p^s)| \ge 1 - \sum_{n > X} n^{-\sigma}\)
When X is large enough, this sum is \(> 0\), so \(\zeta(s) \neq 0\)

Q: Definition. A Dirichlet series is a formal series \[[...]\]where \(a_n \in \mathbb{C}\)
A: \sum_{n=1}^{\infty}a_n n^{-s}

Q: Definition. Define \(f *g: \mathbb{N} \to \mathbb{C}\) to be [...] and call it the Dirchlet convolution.
A: \((f * g)(n) = \sum_{d|n} f(d)g(n/d)\)

Q: Lemma. Let \(f,g,h: \mathbb{N} \to \mathbb{C}\) be functions.
(1) Dirichlet convolution is commutative
(2) It is associative
(3) If f,g are multiplicative so is \(f*g\)
A: (1) \[(f * g)(n) = \sum_{d|n} f(d)g(n/d) = \sum_{a,b \in \mathbb{N}, ab = n} f(a)g(b)\]and can write it the same the other way round
(2)\(((f * g)*h) = \sum_{d|n}(f * g)(d)h(n/d) = \sum_{d|n}\sum_{e|d} f(e)g(d/e)h(n/d)\)
This equals \(\sum_{a,b,c \in \mathbb{N}, abc = n} f(a)g(b)h(c)\) as we can form a bijection between the sets
(3)Suppose f,g are multiplicative, \((m,n) = 1\)
Then \((f * g)(mn) = \sum_{d|mn}f(d)g(mn/d) = \sum_{d|m} \sum_{e|n}f(de)g(mn/de)=\sum_{d|m}\sum_{e|n} f(n)g(m/d)f(e)g(n/e) = (f*g)(m)(f*g)(n)\)

Q: Definition. The Möbius function \(\mu : \mathbb{N \to C}\) is defined by \[[...]\]
A: \mu(n) = \begin{cases}(-1)^k &n=p_1 \dots p_k, \text{ distinct primes} \\ 0 & \exists p \text{ prime s.t. }p^2 | n \end{cases}
Back Extra: \(\mu(1) = 1\)

Q: Proposition. Let \(f: \mathbb{N} \to \mathbb{C}\), let \(\mathbb{1: N \to C}\) be \(\mathbb{1} = 1\) and let \(\delta: \mathbb{N \to C}\) be defined by \(\delta(n) = 0\) if n >1 and \(\delta(1) = 1\)
(1) \(f * \delta = f\)
(2) \(\mu * \mathbb{1} = \delta\)
A: (1)trivial
(2)show that \(\mu \) is multiplicative on sheet. So only need to check for prime powers. True for k = 0
 \[(\mu * \mathbb{1})(p^k) = \sum_{i=1}^k \mu(p^i) = \mu(1) + \dots + \mu(p^k) = 1 - 1 = 0 = \delta(p^k)\]

Q: Proposition. Möbius inversion formula. Suppose \(f,g: \mathbb{N \to C}\) are such that \(\forall n \in \mathbb{N}, f(n) = \sum_{d|n}g(d)\).
Then \(\forall n\in \mathbb{N}, g(n) = \sum_{d|n}\mu(d)f(n/d)\)
A: We have \(f = g * \mathbb{1}\). We need to show that \( g = \mu * f\).
We compute \(\mu * f = \mu * g * \mathbb{1} = g * \mu * \mathbb{1} = g * \delta = g\)

Q: Definition. The von Mangodlt function \(\Lambda : \mathbb{N \to C}\) is defined by \[[...]\]The Chebyshev \(\psi\)-function is defined by \([...]\)
A: \Lambda(n) = \begin{cases} \log p & \text{ if } n =p^k, \text{ p prime}, k \geq 1 \\0 & \text{otherwise}\end{cases}; \psi(x) = \sum_{1 \leq n \leq x}\Lambda(n)

Q: Theorem. If \(s \in \mathbb{C}, \sigma > 1\) then \(- \zeta'(s) / \zeta(s) = \sum_{n=1}^{\infty}\Lambda(n)n^{-s}\)
A: It suffices to prove the identity in the case that \(s > 1\) is real (the case of a general complex \(s\) then follows by analytic continuation). Using the Euler product for \(\zeta(s)\), we compute
\[- \frac{\zeta'(s)}{\zeta(s)} = - \frac{d}{ds} \log \zeta(s) = - \frac{d}{ds} \sum_p -\log(1 - p^{-s})^{-1}\]
\[= - \frac{d}{ds} \sum_p \sum_{k \geq 1} \frac{p^{-ks}}{k} = - \sum_p \sum_{k \geq 1} -k (\log p) p^{-ks} \frac{1}{k} = \sum_{n \geq 1} \Lambda(n) n^{-s},\]
where the interchange of summation and differentiation may be justified using uniform convergence.

Q: Proposition. Legendre's Formula. Suppose \(X > 2\), and let \[P = \prod_{p \le \sqrt{x} \text{ prime}} p\]Then \[\pi(X) - \pi(\sqrt{X}) + 1 = \#\{1 \le n \le X | (n,P) = 1\} = \sum_{d | P} \mu(d) \lfloor X / d \rfloor\]
A: If \(n \in \mathbb{N}\), \(1 \le n \le X\), then either n is prime, or n = 1, or there's a non-trivial factorisation \( n =ab\), where \(a,b > 1\) and one of a,b satisfies \(a \le \sqrt{x} \) or \(b \le \sqrt{x}\)
So if \(n \neq 1\) and n is not prime, then \(\exists\) a prime p s.t. \(p | n\) and \(p \le \sqrt{X}\)
So \(\{1 \le n \le X | (n,P) = 1\} = \{1 \le n \le X | \text{if } p \le \sqrt{X} \text{ is prime, then } p \not{|} n\} = \{1\} \cup \{ \sqrt{X} < p \le X | p \text{ is prime}\}\)
So \(\# \{1 \le n \le X | (n,P) = 1\} = \pi(X ) - \pi(\sqrt{X}) + 1\)
Let's define for \(d | P\), \[A_d = \#\{ 1 \le n \le X | d |n\}\]Let's write \(p_1 , \dots , p_r\) denote the primes \(\le \sqrt{x}\)
Then \(\{1 \le n \le x | (n,P) = 1\} = A_1 \setminus (\bigcup_{i =1}^r A_{p_i})\)
By Inclusion-Exclusion, we have \[\# \{1 \le n \le X | (n,P) = 1\} = \lfloor X \rfloor + \sum_{i=1}^r \sum_{j_1 < \dots < j_i}(-1)^{i} \# (A_{p_{j_1}} \cap \dots \cap A_{p_{j_i}}) = \lfloor X \rfloor + \sum_{d | P, d > 1} \mu(d) \# A_d = \sum_{d|P} \mu(d) \lfloor X / d \rfloor\]

Q: Definition. Let \(N \in \mathbb{N}\), p a prime. Then the p-adic valuation \(v_p(N)\) of \(N\) is [...]
A: the exponent of the largest power of p dividing N.
Back Extra: Equivalently \(v_p(N)\) is the unique integer s.t. \(N = p^{v_p(N)}N_0\) where \(N_0 \in \mathbb{N}\) is prime to p

Q: Lemma. Let \(n \in \mathbb{N}\), \(N = {2n \choose n}\). Then:
1. \(2^{2n}/2n \le N < 2^{2n}\)
2. If p is a prime s.t. \(n < p \le 2n\), then \(v_p(N) = 1\)
3. If p is an odd prime and \(2n/3 < p \le n\) then \(v_p (N) = 0\)
4. If p is any prime, then \(p^{v_p(N)} \le 2n\)
A: (1) \(2^{2n} = (1+1)^{2n} = \sum_{i=1}^{2n} {2n \choose i} \implies N = {2n \choose n} < 2^{2n}\)
\(2^{2n} = 2+ \sum_{i=1}^{2n-1} {2n \choose i} \le 2 + (2n-1)N = 2nN + (2-N) \le 2nN\) as \(N \ge 2\)
(2) \(N = {2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{2n \times (2n-1) \times \dots \times (n+1)}{n \times (n-1) \times \dots \times 1}\)
We have \(n < p \le 2n\). So the denominator is prime to p. We have \(2p > 2n\). There is exactly one multiple of p appearing in the numerator, namely p.
So \(v_p(N) = 1\).
(3) \(N = \frac{(2n) \times \dots \times (n+1)}{n \times \dots \times 1}\) . We have \(2n/3 < p \le n\). We have \(4n/3 < 2p \le 2n\) and \(2n < 3p \le 3n\)
The only multiples of p that appear are p(in denominator) and 2p (in numerator). So \(v_p(N) = 0\)
(4) We show that if \(k \ge 1\), and \(p^k > 2n\), then \(v_p(N) < k\)
We have \(v_p(N) = v_p((2n)!) - 2v_p(n!)\)
We now use the formula \((m \in \mathbb{N}) \) \(v_p(m!) = \sum_{i=1}^{\infty} \lfloor m / p^i \rfloor\)
Therefore \(v_p(N) = \sum_{i=1}^{\infty} (\lfloor 2n /p^i \rfloor - 2 \lfloor n/p^i \rfloor)\)
If \(p^k > 2n\), then the terms with \(i \ge k\) are zero.
If \(x \in (0, \infty)\) then \(\lfloor 2x \rfloor - 2 \lfloor x \rfloor \in \{0,1\}\)
So \(v_p(N) = \sum_{i=1}^{k-1} (\lfloor 2n / p^i \rfloor - 2\lfloor n/p^i \rfloor) \le k-1\)

Q: Theorem. Chebyshev's. \(\exists c_1 , c_2 > 0\) \(\forall x > 4\) \[c_1 \frac{x}{\log x} \le \pi(x) \le c_2 \frac{x}{\log x}\]
A: We start with the upper bound. Strategy: first prove a statement for certain integer values of x.
Claim: If \(k \ge 1\), then \(\pi(2^k) \le \frac{3 \times 2^k}{k} = \frac{2^k}{\log(2^k)} \times 3 \log 2\)
Proof by induction on \(k \ge 1\).
If \(n \in \mathbb{N} \) is even, \(\pi (n) \le n/2\)(as primes are in \(2,3,5,7, \dots\))
Note \(2^k /2 \le 3\times 2^k /k \iff k \le 6\). So done for \(k \le 6\)
For the induction step , note that if \(n \in \mathbb{N}, N = {2n \choose n}\) then \(2^{2n} \ge N \ge \prod_{p \text{ prime}, 2n \ge p > n} p \ge n^{\pi(2n) - \pi(n)}\)
\(\implies (\pi(2n) - \pi(n)) \log n \le 2n \log 2 \implies \pi(2n) - \pi(n) \le \frac{n}{\log n} \cdot 2 \log 2\)
Suppose we know that \(\pi(2^k) \le \frac{3 \times 2^k}{k}\)
We take \( n = 2^k\) to get \(\pi(2^{k+1})\le\frac{2^k}{\log(2^k)} 2\log 2 + \frac{3 \times 2^k}{k} = \frac{2 \times2^k}{k} + \frac{3 \times 2^k}{k} = \frac{5 \times 2^k}{k}\)
The induction step is complete if \(\frac{5 \times 2^k}{k} \le \frac{3 \times 2^{k+1}}{k+1}\), i.e. \(5k+5 \le 6k \implies k \ge 5\)
Suppose \(X > 4\), \(2^k \le X \le 2^{k+1}\)
Then \(\pi(X) \le \pi(2^{k+1}) \le \frac{3 \times2^{k+1}}{k+1}\le \frac{6 \times 2^k}{k} = \frac{6 \times 2^k}{\log(2^k)}\log(2)\)
\(\frac{d}{dx}(\frac{X}{\log X}) = \frac{\log (X-1)}{(\log X)^2} > 0\) when \(x > e \implies \frac{x}{\log x}\) is strictly increasing when \(X > 4\)
So \(\pi(x) \le 6 \log 2 \frac{2^k}{\log 2^k} \le (6 \log 2) \frac{X}{\log X}\)
To prove the general upper bound, we note that \( X / \log X \) is strictly increasing when \( X > e \) (compute derivatives). If \( 4 \leq 2^k < X \leq 2^{k+1} \), then we have \[ \pi(X) \leq \pi(2^{k+1}) \leq 6 \cdot \frac{2^k}{k+1} < 6 \cdot \frac{2^k}{k} = 6 \log 2 \cdot \frac{2^k}{\log 2^k} \leq 6 \log 2 \cdot \frac{X}{\log X}. \] We next establish the lower bound. Let \( n \in \mathbb{N}, N = \binom{2n}{n} \). Lemma 4.18(4) implies that for any prime \( p \), we have \( p^{v_p(N)} \leq 2n \), i.e., \( v_p(N) \leq \frac{\log 2n}{\log p} \). Moreover, this valuation is 0 if \( p > 2n \). Since \( 2^{2n}/2n \leq N \), we have \[ 2n \log 2 - \log 2n \leq \log N = \sum_{p \leq 2n} v_p(N) \log p \leq \sum_{p \leq 2n} \log 2n = \pi(2n) \log 2n. \] If \( 2n \leq X < 2n + 2 \), then we get \[ \pi(X) \geq \pi(2n) \geq \frac{2n}{\log 2n} \log 2 - 1 \geq \frac{X - 2}{\log X} \log 2 - 1. \] We claim that when \( X \geq 16 \), we have \[ \frac{X - 2}{\log X} \log 2 - 1 \geq \frac{\log 2}{2} \cdot \frac{X}{\log X}. \] Combining this with the previous line shows that \( \pi(X) \geq \frac{\log 2}{2} \cdot \frac{X}{\log X} \) when \( X \geq 16 \). To prove the claim, we note that re-arranging gives the inequality \[ \frac{\log 2}{2} \cdot \frac{X}{\log X} - 2 \log 2 \cdot \frac{1}{\log X} - 1 \geq 0. \] This is indeed satisfied when \( X = 16 \): if we plug in \( X \geq 16 \), then we get \( \frac{1}{2} \geq 0 \), and the left-hand side is increasing when \( X \geq 16 \) (compute derivatives). To complete the proof of the theorem, it remains to show that \( \pi(X) \geq \frac{\log 2}{2} \cdot \frac{X}{\log X} \) when \( 4 < X \leq 16 \). This is true: we have \( \pi(X) \geq 2 \) when \( X > 4 \), while the largest value of \( \frac{\log 2}{2} \cdot \frac{X}{\log X} \) in this range is achieved when \( X = 16 \), in which case it equals 2.

Q: Lemma. Let \( P(X) = \prod_{p \leq X \text{ prime}} p \). Then \( P(X) \leq 4^X \) for all \( X \geq 1 \).
A: It suffices to show this when \( X = m \in \mathbb{N} \). We will use induction on \( m \geq 1 \). The cases \( m = 1, 2 \) are immediate. In general, suppose that \( n \geq 2 \) and the statement is known for \( m \leq n \). We show that \( P(n+1) \leq 4^{n+1} \). If \( n \) is odd, then \( n+1 \) is even and \( P(n) = P(n+1) \), so \[ P(n+1) = P(n) \leq 4^n < 4^{n+1}. \] If \( n = 2k \) is even, then we have \[ P(n) = P(k+1) \prod_{k+2 \leq p \leq 2k+1} p \leq 4^{k+1} \binom{2k+1}{k+1}, \] because if \( k+2 \leq p \leq 2k+1 \), then \( v_p \left( \binom{2k+1}{k+1} \right) = 1 \). However, we have \[ 2^{2k+1} = (1+1)^{2k+1} \geq 2 \binom{2k+1}{k+1}, \] hence \[ \binom{2k+1}{k+1} \leq 4^k, \] hence \[ P(n) \leq 4^{2k+1} = 4^n, \] as required.

Q: Theorem. Bertrand's Postulate. For every integer \(n>1\), there exists a prime number p such that \(n < p < 2n\)
A useful equivalent formulation is: for any prime q, there exists a prime p such that q < p < 2p.
A: Suppose for contradiction that there is no prime \( p \) with \( n < p < 2n \). We can assume that \( n > 3 \), as the statement is easily checked for small values of \( n \). Let \[ N = \binom{2n}{n}. \] For any prime \( p \mid N \), we must have \( p \leq n \) (by our assumption). Lemma 4.18(3) shows that if \( p \mid N \) and \( p < n \), then in fact \( p \leq 2n/3 \). Let us write \( N = N_1 N_2 \) with \[ N_1 = \prod_{p \mid N, v_p(N) = 1} p \quad \text{and} \quad N_2 = \prod_{p \mid N, v_p(N) \geq 2} p^{v_p(N)}. \] Then \( N = N_1 N_2 \) and \( (N_1, N_2) = 1 \). \( N_1 \) is the product of its distinct prime factors, each of which is at most \( 2n/3 \), so we find \[ N_1 \leq \prod_{p \leq 2n/3 \text{ prime}} p = P(2n/3) \leq 4^{2n/3}. \] If \( p^{v_p(N)} \) appears in \( N_2 \), then \( p^2 \leq p^{v_p(N)} \leq 2n \) (by Lemma 4.18(4)), so \( p \leq \sqrt{2n} \), so we find \[ N_2 \leq \prod_{p \leq \sqrt{2n}} p^{v_p(N)} \leq \prod_{p \leq \sqrt{2n}} 2n \leq (2n)^{\sqrt{2n}}. \] We get \[ \frac{2^{2n}}{2n} = N = N_1 N_2 \leq 4^{2n/3} (2n)^{\sqrt{2n}}, \] hence \[ \frac{\log 2}{3} 2n \leq (1 + \sqrt{2n}) \log 2n. \] The left-hand side grows much faster than the right-hand side as \( n \to \infty \), so this will certainly be a contradiction for large values of \( n \); in fact, it is a contradiction whenever \( n \geq 500 \). It remains to show that the Theorem holds when \( 1 < n < 500 \). Suppose given a list \( 2 = p_1 < p_2 < \cdots < p_r \) of primes such that \( p_r > 500 \) and \( p_{i+1} < 2p_i \) for each \( i = 1, \ldots, r-1 \). We claim that this would complete the proof of the Theorem. Indeed, let \( 1 < n < 500 \); then there exists \( p_i \) such that \( p_i \leq n < p_{i+1} \), hence \( p_{i+1} < 2p_i \leq 2n \) (and so \( p_{i+1} \) works for \( n \)). One possible sequence of primes with this property is \[ 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631. \]

Q: Proposition. Let \(\theta\in \mathbb{R}\). Then the continued fraction expansion of \(\theta\) is finite \(\iff \theta \in \mathbb{Q}\)
A: (\(\implies\))follows as if \(\theta = [a_0, \dots , a_n], a_i \in \mathbb{Z}\) then \(\theta \in \mathbb{Q}\)
(\(\impliedby\))If \(\theta \in \mathbb{Z}\), then \(\theta = [a_0]\). So suppose \(\theta \not \in \mathbb{Z}\), \(\theta_1 = r_1/r_2\), where \(r_1 > r_2 > 0\) are integers, \((r_1, r_2) = 1\)
Apply the Euclidean algorithm to \(r_1 / r_2\): \(r_1 = q_1 r_2 + r_3\), \(r_2 = q_2 r_3 + r_4\), \(\dots\), \(r_{n+1} = q_{n+1}r_{n+2} \) where \(r_{n+2} = 1 \)
Claim: \(\forall i = 1, \dots , n+1, \theta_i = r_i / r_{i+1}\) .
True when \(i=1\) by definition
If \(\theta_i = r_i / r_{i+1}\) for some \(i \le 1 < n+1\), then \[r_i= q_i r_{i+1} + r_{i+2} \implies \theta_i = r_{i}/r_{i+1} = q_i + r_{i+2} / r_{i+1}\]with \(r_{i+2}/ r_{i+1} < 1\) so \(a_i = \lfloor \theta _i \rfloor = q_i\), \(\theta_{i+1} = (\theta_i - a_i)^{-1} = r_{i+1}/ r_{i+2}\) , in particular this in an integer at i = n so the continued fraction algorithm stops at step n+1.

Q: Definition. Suppose \(a_0 , a_1 , \dots \in \mathbb{Z}, a_i \geq 1 \) if \(i \geq 1\). Then define two sequences \((p_n)_{n \geq 0}, (q_n)_{n \ge 0}\) recursively as follows\[[...]\]
\[[...]\]
A: p_0 = a_0 \; \; p_1 = a_0 a_1 + 1 \; \; p_{n+1} = a_{n+1}p_n + p_{n-1}; q_0 = 1 \; \; q_1 = a_1 \;\;q_{n+1} = a_{n+1}q_n + q_{n-1}
Back Extra: We could define \(p_{-1} = 1, q_{-1} = 0\) then recursive formula also holds for \(n=0\)
We have \(q_0 \le q_1 < q_2 < q_3< \dots\) as \(a_n \ge 1\) if \(n \ge 1\)
We can express the recursion using matrices as \[\left ( \begin{matrix} p_{n+1} & p_n \\ q_{n+1} & q_n\end{matrix} \right ) = \left ( \begin{matrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{matrix} \right ) \left ( \begin{matrix} a_{n+1} & 1 \\ 1 & 0\end{matrix} \right ) = \left ( \begin{matrix} a_0 & 1 \\ 1 & 0\end{matrix} \right ) \dots \left ( \begin{matrix} a_{n} & 1 \\ 1 & 0\end{matrix} \right ) \left ( \begin{matrix} a_{n+1} & 1 \\ 1 & 0\end{matrix} \right )\]If \(\theta \in \mathbb{R}\) and \(\theta = [a_0, a_1 , a_2 , \dots]\) then \((p_n / q_n)_{n \ge 0}\) is called the sequence of convergents of \(\theta\)

Q: Lemma. Suppose \(a_0 , a_1 , a_2 , \dots \in \mathbb{Z}, a_i \ge 1\) if \(i \ge 1\). Then:
(1) \(p_n / q_n = [a_0 , \dots , a_n]\)
(2) \(\forall n \ge 1\), \(p_n q_{n-1} - q_n p _{n-1} = (-1)^{n-1}\), \((p_n , q_n) = 1\) and \(p_n / q_n - p_{n-1}/q_{n-1} = (-1)^{n-1}/q_n q_{n-1}\)
(3)Suppose \(\beta \in \mathbb{R}, \beta > 0\). Then \(\forall n \ge 1\), \(\frac{\beta p_n + p_{n-1}}{\beta q_n + q_{n-1}} = [a_0, a_1 , \dots , a_n, \beta]\) and \(\frac{\beta p_n + p_{n-1}}{\beta q_n + q_{n-1}}\) lies strictly between \(p_n / q_n \) and \(p_{n-1} / q_{n-1}\)
A: (1) Take \(\beta = a_{n+1}\) in (3): \(p_{n+1} / q_{n+1} = [a_1 , \dots , a_{n+1}]\)
(2)Take determinants in matrix equation to get \(p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}\)
This shows they are coprime. Divide by \(q_{n-1}q_n\) to get the other identity.
(3) is proved using induction on \( n \geq 0\). If \( n =0 \), the LHS equals \[\frac{\beta a_0 + 1}{\beta} = [a_0, \beta]. \] If \( n >0\), let \( \gamma = a_n + \frac{1}{\beta} >0\). Then \[[a_0, \dots, a_n, \beta]=[a_0, \dots, a_{n-1}, [a_n, \beta]] = [a_0, \dots, a_{n-1}, \gamma] = \frac{\gamma p_{n-1} + p_{n-2}}{\gamma q_{n-1} + q_{n-2}}, \] which equals \[\frac{\beta p_n + p_{n-1}}{\beta q_n + q_{n-1}},\] by induction. This in turn equals \[\frac{a_n p_{n-1} + p_{n-2} + p_{n-1}/\beta}{a_n q_{n-1} + q_{n-2} + q_{n-1}/\beta} = \frac{\beta p_n + p_{n-1}}{\beta q_n + q_{n-1}}.\]After multiplying through and applying the recursive formula for \( p_n, q_n \), we now have \[[a_0, \dots, a_n, \beta]= \frac{\beta p_n + p_{n-1}}{\beta q_n + q_{n-1}}, \] which shows that \( [a_0, \dots, a_n, \beta] \) lies strictly between \( \frac{\beta p_n}{\beta q_n} = \frac{p_n}{q_n} \) and \( \frac{p_{n-1}}{q_{n-1}} \) (noting that \( \frac{p_n}{q_n} \neq \frac{p_{n-1}}{q_{n-1}} \) by (2)).

Q: Theorem. Let \(\theta \in \mathbb{R}\) be irrational, with continued fraction expansion \([a_0, a_1, a_2, \ldots]\), and let \((p_n / q_n)_{n \geq 1}\) be the associated sequence of convergents. Then:
(1)\(\theta\) lies strictly between \(p_n / q_n\) and \(p_{n+1} / q_{n+1}\), and \(|\theta - p_n / q_n| < 1 / (q_n q_{n+1})\).
(2)\(p_n / q_n \to \theta\) as \(n \to \infty\).
A: According to the continued fraction algorithm, we have \(\theta = [a_0, a_1, \ldots, a_{n+1}, \theta_{n+2}]\), where \(\theta_{n+2}\) is a positive real number. By Lemma 5.3, \(\theta\) lies between \(p_n / q_n\) and \(p_{n+1} / q_{n+1}\), in an interval of length \(1 / (q_n q_{n+1})\). Therefore,
\[|\theta - p_n / q_n| \leq 1 / (q_n q_{n+1}).\]
We have already observed that \(q_n \to \infty\) as \(n \to \infty\), so this implies that \(p_n / q_n \to \theta\) as \(n \to \infty\).

Q: Theorem. Let \(\theta \in \mathbb{R}\) be irrational, and let \(p \in \mathbb{Z}, q \in \mathbb{N}\). Then:
If \(q < q_{n+1}\), then \(|q\theta - p| \geq |q_n\theta - p_n|\).
If \(q \leq q_n\), then \(|\theta - p/q| \geq |\theta - p_n/q_n|\).
A: First statement implies the second. Assume \(q \leq q_n < q_{n+1}\). Then:
\[|\theta - p/q| = \frac{1}{q} |q\theta - p| \geq \frac{1}{q_n} |q_n\theta - p_n| = |\theta - p_n/q_n|.\]
For the first part of the theorem, there is a unique pair \((u, v) \in \mathbb{Z}^2\) such that
\[\begin{pmatrix} p_n & p_{n+1} \\ q_n & q_{n+1} \end{pmatrix} \begin{pmatrix} u \\ v \end{pmatrix} = \begin{pmatrix} p \\ q \end{pmatrix}.\]
Indeed, the determinant of the matrix on the left is \(p_nq_{n+1} - q_np_{n+1} = (-1)^{n-1}\), so its inverse still has integer entries. With this choice of \((u, v)\), we have:
\[q\theta - p = u(q_n\theta - p_n) + v(q_{n+1}\theta - p_{n+1}).\]
If \(v = 0\), then \(|u| \geq 1\) and the result follows immediately. Assume instead that \(v \neq 0\). As \(0 < q < q_{n+1}\) and \(q = uq_n + vq_{n+1}\), we see that \(u, v\) must have opposite signs (and in particular, \(u \neq 0\)). We also know that \(q_n\theta - p_n\) and \(q_{n+1}\theta - p_{n+1}\) have opposite signs, as \(\theta\) lies between the two distinct rational numbers \(p_n/q_n\) and \(p_{n+1}/q_{n+1}\).
Therefore, \(u(q_n\theta - p_n)\) and \(v(q_{n+1}\theta - p_{n+1})\) have the same sign, and:
\[|q\theta - p| = |u(q_n\theta - p_n)| + |v(q_{n+1}\theta - p_{n+1})| \geq |(q_n\theta - p_n)|,\]
as \(u\) is a non-zero integer

Q: Theorem. Let \(\theta \in \mathbb{R}\) be irrational, and let \(\{p_n / q_n\}\) denote the sequence of convergents to \(\theta\). Then \(\theta\) is badly approximable if and only if there exists \(c > 0\) such that \[ |q \theta - p| > \frac{c}{q} \] for all \(p \in \mathbb{Z}\), \(q \in \mathbb{N}\).
A: \((\Rightarrow)\) Suppose \(\theta\) is badly approximable. Then by definition there exists \(c > 0\) such that\[ \left| \theta - \frac{p}{q} \right| > \frac{c}{q^2} \]for all \(p \in \mathbb{Z}\), \(q \in \mathbb{N}\). Multiplying through by \(q\), we obtain\[ |q \theta - p| > \frac{c}{q}. \]\((\Leftarrow)\) Conversely, suppose there exists \(c > 0\) such that\[ |q \theta - p| > \frac{c}{q} \]for all \(p \in \mathbb{Z}\), \(q \in \mathbb{N}\). Then dividing through by \(q\), we obtain\[ \left| \theta - \frac{p}{q} \right| > \frac{c}{q^2}. \]Hence \(\theta\) is badly approximable by definition

Q: Definition. Let \((a_n)_{n \ge 0}\) be a sequence of integers with \(a_n \ge 1\) if \(n \ge 1\). We say that the continued fraction \([a_0, a_1 , \dots]\) is essentially periodic(of period \(k \ge 1\)) if it has the form \[[...]\]
A: [a_0, \dots , a_{m-1}, \overline{a_m, \dots , a_{m+k-1} }]
Back Extra: We say that it is purely periodic if \(m = 0 \)

Q: Theorem. Lagrange. Let \(\theta \in \mathbb{R}\) be irrational. Then the continued fraction expansion of \(\theta\) is essentially periodic if and only if \(\theta\) is a quadratic irrational.
A: Suppose that \( \theta \) is a quadratic irrational, satisfying an equation \[ a\theta^2 + b\theta + c = 0 \] with \( a, b, c \in \mathbb{Z} \). Let \( f(x, y) = ax^2 + bxy + cy^2 \) (a binary quadratic form), so that \( f(\theta, 1) = 0 \). For each \( n \geq 0 \), we have \[ \theta = [a_0, a_1, \ldots, a_n, \theta_{n+1}]. \] We define further binary quadratic forms \( f_n(x, y) \) (\( n \geq 1 \)) by the formula \[ f_n(x, y) = f((x, y) \begin{pmatrix} p_n & q_n \\ p_{n-1} & q_{n-1} \end{pmatrix}) = f(p_n x + p_{n-1}y, q_n x + q_{n-1}y). \] Then \[ f_n(\theta_{n+1}, 1) = f(p_n\theta_{n+1} + p_{n-1}, q_n\theta_{n+1} + q_{n-1}) = (q_n\theta_{n+1} + q_{n-1})^2 f(\theta, 1) = 0. \] We claim that as \( n \geq 1 \) varies, the sequence \( f_n(x, y) \) features only finitely many distinct binary quadratic forms. We first explain why this implies the theorem. Since \( f_n \) is obtained from \( f \) by a change of variable with non-zero determinant, \( f_n \) is non-zero, so the equation \( f_n(x, 1) = 0 \) has at most two distinct solutions. The claim implies that the sequence \( \theta_{n+1} \) can itself take on only finitely many distinct values. Therefore, there exist \( n, k \geq 1 \) such that \( \theta_n = \theta_{n+k} \). This implies that the continued fraction expansion of \( \theta \) is indeed essentially periodic. We now establish the claim. Write \( f_n(x, y) = A_nx^2 + B_nxy + C_ny^2 \). Then \( A_n = f_n(1, 0) = f(p_n, q_n) \), while \( C_n = f_n(0, 1) = f(p_{n-1}, q_{n-1}) = A_{n-1} \). Moreover, we have \[ \operatorname{disc} f_n = B_n^2 - 4A_nC_n = \det \begin{pmatrix} p_n & q_n \\ p_{n-1} & q_{n-1} \end{pmatrix}^2 \operatorname{disc} f = \operatorname{disc} f, \] since \( p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1} \). Therefore, it suffices to show that the sequence \( A_n \) takes on only finitely many possible values, or equivalently that \( |A_n| \) is bounded as \( n \) varies. To this end, let us factor \( f(x, 1) = a(x - \theta)(x - \theta') \) for \( \theta' \in \mathbb{R} \): \[ |A_n| = |f(p_n, q_n)| = q_n^2|p_n/q_n - \theta||p_n/q_n - \theta'| \leq q_n^2|p_n/q_n - \theta'|, \] using that \( |p_n/q_n - \theta| \leq 1/(q_n q_{n+1}) \) (Theorem 5.4). We have \( |p_n/q_n - \theta'| \to |\theta - \theta'| > 0 \) as \( n \to \infty \), so the sequence \( |a||p_n/q_n - \theta'| \) (\( n \geq 1 \)) is bounded. This shows that \( |A_n| \) is also bounded and completes the proof.

Q: Theorem. Let \( d \in \mathbb{N} \) be a non-square. Then the equation \( x^2 - dy^2 = 1 \) has a solution with \( x, y \in \mathbb{N} \).
A: Consider\[ \theta = \sqrt{d} = [a_0, a_1, \ldots, a_n] = [a_0, \ldots, a_n, \theta_1], \]where \( \theta_1 = (\sqrt{d} - a_0)^{-1} = [a_1, \ldots, a_n] \). Then we find\[ \sqrt{d} = \frac{\theta_1 p_n + p_{n-1}}{\theta_1 q_n + q_{n-1}} = \frac{p_n + p_{n-1}(\sqrt{d} - a_0)}{q_n + q_{n-1}(\sqrt{d} - a_0)}. \]Therefore,\[ q_n d + (q_n - q_{n-1}a_0)\sqrt{d} = (p_n - p_{n-1}a_0) + p_{n-1}\sqrt{d}. \]Equating coefficients of \( 1 \) and \( \sqrt{d} \), we find\[ q_{n-1} d = p_n - p_{n-1}a_0 \quad \text{and} \quad p_{n-1} = q_n - q_{n-1}a_0, \]hence\[ p_{n-1}^2 - dq_{n-1}^2 = p_{n-1}q_n - q_{n-1}p_n = (-1)^n. \]If \( n \) is even, then \( (p_{n-1}, q_{n-1}) \) is a solution to Pell's equation. Otherwise, we can repeat the same argument using\[ \theta = [a_0, a_1, \ldots, a_{2n}], \]so that \( (p_{2n-1}, q_{2n-1}) \) is a solution

Q: Definition. Let \(N>1\) be an odd composite integer, and let \(b \in \mathbb{Z}\) be an integer with \((b,N) = 1\). We say that N is a Fermat pseudoprime to the base b if [...]
A: \(b^{N-1} \equiv 1 \mod N\)

Q: Proposition. Let \( N \in \mathbb{N} \) be an odd composite integer. Then:
1. If \( b \in \mathbb{Z} \) and \( \gcd(b, N) = 1 \), then whether \( N \) is a Fermat pseudoprime to the base \( b \) depends only on the image of \( b \) in \( (\mathbb{Z}/N\mathbb{Z})^\times \).
2. The set \( B \) of \( b \in (\mathbb{Z}/N\mathbb{Z})^\times \) such that \( N \) is a Fermat pseudoprime to the base \( b \) is a subgroup of \( (\mathbb{Z}/N\mathbb{Z})^\times \).
3. If there is some \( b_0 \in (\mathbb{Z}/N\mathbb{Z})^\times \) such that \( N \) is not a Fermat pseudoprime to the base \( b_0 \), then \( N \) is not a Fermat pseudoprime to the base \( b \) for at least half of the \( b \in (\mathbb{Z}/N\mathbb{Z})^\times \).
A: (1) is clear since the condition \( b^{N-1} \equiv 1 \mod N \) only depends on \( b \mod N \)
(2) \( N \) is certainly a Fermat pseudoprime to the base \( 1 \). We need to show that if \( N \) is a Fermat pseudoprime to the bases \( b_1, b_2 \), then it is also a Fermat pseudoprime to the base \( b_1 b_2 \). We compute \[ (b_1 b_2)^{N-1} = b_1^{N-1} b_2^{N-1} \equiv 1 \mod N, \] so this is true
(3) Let \( G = (\mathbb{Z}/N\mathbb{Z})^\times \). We need to show that \( \#G \setminus B \geq \frac{1}{2} \#G \), or equivalently that \( \#B \leq \frac{1}{2} \#G \). Since \( B \leq G \) is a subgroup, we have \( \#B = \#G / [G : B] \). The existence of \( b_0 \) implies that \( B \) is a proper subgroup of \( G \), hence \( [G : B] \geq 2 \), hence \( \#B \leq \frac{1}{2} \#G \), as required.

Q: Defintion. Let \(N>1\) be an odd composite integer. N is said to be a Carmichael number if [...]
A: N is a Fermat pseudoprime to every base \(b \in (\mathbb{Z} / N \mathbb{Z})^{\times}\)

Q: Definition. Let \(N>1\) be an odd composite integer, and let \(b \in \mathbb{Z}, (b,N)=1\). We say that N is an Euler pseudoprime to the base b if [...]
A: we have \(b^{(N-1)/2} \equiv (\frac{b}{N}) \mod N\) where the RHS is a Jacobi symbol.

Q: Theorem. Let \( N > 1 \) be an odd composite integer. Then there exists a base \( b \in (\mathbb{Z}/N\mathbb{Z})^\times \) such that \( N \) is not an Euler pseudoprime to the base \( b \).
A: Suppose first that \( N \) is square-free, and write \( N = p m \) with \( p \) prime, \( m \geq 3 \), \( p \nmid m \). Choose \( u \in \mathbb{Z} \) such that \( \left( \frac{u}{p} \right) = -1 \). By the Chinese Remainder Theorem, we can find \( b \in \mathbb{Z} \) such that \( b \equiv u \mod p \), \( b \equiv 1 \mod m \), hence \( \left( \frac{b}{N} \right) = -1 \). On the other hand, we have
\[b^{(N-1)/2} \equiv 1 \mod m, \quad \text{hence } b^{(N-1)/2} \not\equiv -1 = \left( \frac{b}{N} \right) \mod N,\]
so \( N \) is not an Euler pseudoprime to the base \( b \).
Now suppose that \( N \) is divisible by \( p^2 \) for an odd prime \( p \). Then we have
\[(1 + p)^{N-1} \equiv 1 + (N-1)p \mod p^2.\]
By the Chinese Remainder Theorem, we can find some \( b \in \mathbb{Z} \) with \( (b, N) = 1 \) such that \( b \equiv 1 + p \mod p^2 \). Then \( b^{N-1} \not\equiv 1 \mod p^2 \), so
\[b^{(N-1)/2} \not\equiv \pm 1 \mod p^2,\]
and \( N \) is again not an Euler pseudoprime to the base \( b \)

Q: Definition. Let \(N>1\) be an odd integer, and let \(b \in \mathbb{Z}, (b,N) = 1\). Factor \(N-1 = s^2 t\) where t is odd and \(s \ge 1\). We say that N passes the strong test to the base b if [...] If N is composite and passes the strong test to the base b, then we say that N is [...]
A: either \(b^t \equiv 1 \mod N\) or \(b^{2^rt} \equiv -1 \mod N\) for some \(0 \le r < s\).; a strong pseudoprime to the base b.

Q: Proposition. Let \( N > 1 \) be an odd integer, and suppose that \( x, y \in \mathbb{Z} \) satisfy \( x^2 \equiv y^2 \mod N \) but \( x \not\equiv \pm y \mod N \). Then \( (N, x-y) \) and \( (N, x+y) \) are non-trivial factors of \( N \).
A: \( (N, x-y) \) and \( (N, x+y) \) are certainly factors of \( N \). We need to show they are non-trivial. If \( (N, x-y) = N \), then \( x-y \equiv 0 \mod N \), which implies \( x \equiv y \mod N \), a contradiction since \( x \not\equiv \pm y \mod N \). If \( (N, x-y) = 1 \), then we can cancel \( x-y \) in the identity \( (x+y)(x-y) \equiv 0 \mod N \), leading to \( x+y \equiv 0 \mod N \). This implies \( x \equiv -y \mod N \), again a contradiction. The argument for \( (N, x+y) \) is similar

Q: Lemma. Let \( p_1, \ldots, p_r \) be distinct primes, and let \( c_1, \ldots, c_k \) be non-zero integers divisible only by primes in \( \{p_1, \ldots, p_r\} \). If \( k > r+1 \), then there is a non-empty set \( I \subset \{1, \ldots, k\} \) such that \[ \prod_{i \in I} c_i \] is a square.
A: If \( J \subset \{1, \ldots, k\} \) is a subset, write\[ c_J = \prod_{i \in J} c_i = (-1)^{\alpha_J,0} p_1^{\alpha_J,1} \cdots p_r^{\alpha_J,r} m_J^2, \]where \( m_J \geq 1 \) and \( \alpha_{J,j} \in \{0, 1\} \) for each \( j = 0, \ldots, r \). We consider the \( (r+1) \)-tuples \( \alpha_J \in \{0, 1\}^{r+1} \). There are \( 2^k \) possible choices for \( J \). By the pigeonhole principle, we can find \( J \neq J' \) such that \( \alpha_J = \alpha_{J'} \), hence \( c_J = c_{J'} \). Then the set \( J \Delta J' = (J \cup J') \setminus (J \cap J') \) (symmetric difference) is non-empty and\[ c_J c_{J'} = c_{J \Delta J'} c_{J \cap J'}^2 \]is a square, hence \( c_{J \Delta J'} \) is a square.

Q: Definition. A factor base is [...] If B is a factor base and \(N \in \mathbb{N}\) is an odd composite integer, then a B-number is [...]
A: a set \(B = \{-1, p_1 , \dots , p_r\}\) where \(p_1 , \dots , p_r\) are prime numbers.; a positive integer x such that \(\langle x^2 \rangle\) is divisible only by primes in B (where \(\langle x^2 \rangle\) is the unique integer such that \(\langle x^2 \rangle = x^2 \mod N\) and \(-N/2 < \langle x^2 \rangle < N/2\))

Q: Lemma. Let \( N \in \mathbb{N} \) be an odd composite integer that is not a perfect square. Let \( p_n/q_n \) be a convergent to \( \sqrt{N} \). Then \[ |p_n^2 - Nq_n^2| \leq 2\sqrt{N}. \]
A: We compute\[ |p_n^2 - Nq_n^2| = q_n^2 \left| \frac{p_n}{q_n} - \sqrt{N} \right|\left| \frac{p_n}{q_n} + \sqrt{N} \right| \leq q_n^2 \cdot \frac{1}{q_nq_{n+1}} \left( 2\sqrt{N} + \frac{1}{q_nq_{n+1}} \right) = \frac{1}{q_{n+1}} \left( 2q_n\sqrt{N} + \frac{1}{q_nq_{n+1}} \right) \leq \frac{1}{q_{n+1}} \left( (2q_n + 1) \sqrt{N} \right) \leq 2\sqrt{N}, \]as \( q_n < q_{n+1} \) \(\square\)

Q: What is Lagrange's Theorem?
A: Let p be a prime, \(f(X) = a_n X^n + \dots + a_0 \in \mathbb{Z}/ p\mathbb{Z} [X]\) a polynomial with \(a_n \not \equiv 0 \mod p\). Then \(f(X) \equiv 0\) has at most n solutions in \(\mathbb{Z}/p \mathbb{Z}\).

Q: What is Gauss' Lemma?
A: Let p be an odd prime, a an integer not divisible by p. Then \(\left ( \frac{a}{p}\right) = (-1)^{\mu}\) where \[\mu = \# \{j \in \mathbb{Z} | 0 < j < p/2 , \langle ja \rangle < 0\}\]

Q: What is Legendre's formula?
A: Suppose \(X > 2\) and let \[P = \prod_{p \le \sqrt{x} \text{ prime}} p\]then \[\pi(X) - \pi(\sqrt{X}) + 1 = \#\{1 \le n \le X | (n,P) = 1\} = \sum_{d | P} \mu(d) \lfloor X / d \rfloor\]

Q: What is the Prime Number Theorem?
A: \[\pi(X) \sim X/\log X\]as \(X \to \infty\)

Q: What is Dirichlet's Theorem?
A: Let \[\pi(X,a,N) = \# \{p \in (a + N\mathbb{Z}) \cap [1,X] | p \text{ prime}\}\]denote the counting function of primes congruent to a mod N. Then \[\pi(X) \sim \frac{1}{\phi(N)} \cdot X / \log (X)\]as \(X \to \infty\)

Q: What is Pollard's method?
A: Let N be an odd composite integer of the form \(N = pN_0\) where \((p, N_0) = 1\). We consider an integer a with \((a,N) = 1\). Then \(a^{p-1} \equiv 1 \mod p\) but it is likely that \(a^{p-1} \not \equiv 1 \mod N_0\) so \((N, a^{p-1} - 1)\) will usually be a non-trivial factor of N. We don't know p at the start so the method proceeds as follows.
1. Fix \(m \ge 2\). We aim to find prime factors p of N such that all prime powers dividing p-1 are at most m.
2. Let \(k = \text{lcm}(1, \dots , m)\)
3. Choose \(a \ge 2\) at random. Test whether \((a,N) = 1\). If not, we have found a non-trivial factor of N.
4. Otherwise, compute \(a^k \mod N\) by repeated squaring
5. Compute \((N, a^k - 1)\); we hope that this is a non-trivial factor of N.