diff options
Diffstat (limited to 'math/number-theory.md')
| -rw-r--r-- | math/number-theory.md | 441 |
1 files changed, 441 insertions, 0 deletions
diff --git a/math/number-theory.md b/math/number-theory.md new file mode 100644 index 0000000..47e63e7 --- /dev/null +++ b/math/number-theory.md @@ -0,0 +1,441 @@ +--- +layout: algebra +title: mathematics/number theory +--- + +# MATH 312: Number Theory + +## Chapter 1: The Integers + +## Chapter 2: Greatest Common Divisors and Prime Factorization + +## Greatest Common Divisors + +**Definition**: The **greatest common divisor** of two integers $a$ and $b$ not both zero is the largest integer which divides both $a$ and $b$. It is written as $(a,b)$. + +**Definition**: The integers $a$ and $b$ are called **relatively prime** if $a$ and $b$ have greatest common divisor $(a,b) = 1$. + +**Proposition**: Let $a,b,c$ be integers with $(a,b) = d$. Then +- $(a/d, b/d) = 1$ +- $(a+cb, b) = (a,b)$. + +**Definition**: If $a,b$ are integers, then a **linear combination** of $a$ and $b$ is a sum of the form $ma + nb$, where $m,n$ are integers. + +**Theorem**: The greatest common divisor of the integers $a,b$ not both zero is the least positive integer that is a linear combination of $a$ and $b$. + +**Definition**: Let $a_1, a_2, ... a_n$ be integers not all zero. The **greatest common divisor** of those integers is the largest integer which is a divisor of all of the integers in the set. It is written as $(a_1, a_2, ..., a_n)$. + +**Lemma**: If $a_1, a_2, ... a_n$ are integers not all zero, then $(a_1, a_2, ..., a_{n-1}, a_n)$ = $(a_1, a_2, ..., (a_{n-1}, a_n))$. + +**Definition**: We say that integers $a_1, a_2, ..., a_n$ are **mutually relatively prime** if their greatest common divisor is 1. These integers are **pairwise relatively prime** if for each pair of integers their greatest common divisor is 1. + +## The Euclidean Algorithm + +**The Euclidean Algorithm**: Let $r_0 = a$ and $r_1 = b$ be nonnegative integers with $b ≠ 0$. If the division algorithm is successively applied to obtain $r_j = r_{j+1} q_{j+1} + r_{j+2}$ with $0 < r_{j+2} < r_{j+1}$ for $j = 0,1,2,...,n-1$ and $r_n = 0$, then $(a,b) = r_{n-1}$, the last nonzero remainder. + +**Lemma**: If $c$ and $d$ are integers and $c = dq + r$, then $(c,d) = (d,r)$. + +**Definition**: The **Fibonacci numbers**... todo + +**Theorem**: Let $n$ be a positive integer and let $α = (1 + \sqrt{5})/2$. Then $u_n > α^{n-2}$ for $n ≥ 3$. + +**Theorem**: todo + +**Lame's Theorem**: The number of divisions needed to find the greatest common divisor of two positive integers using the Euclidean algorithm does not exceed five times the number of digits in the smaller of the two integers. + +**Corollary**: The number of bit operations needed to find the greatest common divisor of two positive integers $a$ and $b$ with $b > a$ is $O((log_2 a)^3)$. + +**Theorem**: Let $a$ and $b$ be positive integers. Then $(a,b) = s_n a + t_n b$ for $n = 0,1,2,...$ where $s_n$ and $t_n$ are the $n$th terms of the sequences defined by $s_0 = 1, s_1 = 0, t_0 = 0, t_1 = 1$ and $s_j = s_{j-2} - q_{j-1} q_{j-1}, t_j = t_{j-2} - q_{j-2} t_{j-t}$ for $j = 2,3,...,n$, where $q_j$ are the quotients in the divisions of the Euclidean algorithm when it is used to find $(a,b)$. + +## The Fundamental Theorem of Arithmetic + +**The Fundamental Theorem of Arithmetic**: Every positive integer can be written uniquely as a product of primes, in order of nondecreasing size. + +**Lemma**: If $a,b,c$ are positive integers such that $(a,b) = 1$ and $a | bc$, then $a | c$. + +**Corollary**: If $p$ divides $a_1 a_2 ... a_n$ where $p$ is a prime and $a_1, a_2, ..., a_n$ are positive integers, then there is an integer $i$ with $1 ≤ i ≤ n$ such that $p$ divides $a_i$. + +**Definition**: The **least common multiple** of two positive integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$. It is written as $[a,b]$. + +**Lemma**: If $x,y$ are real numbers, then $max(x,y) + min(x,y) = x+y$. + +**Theorem**: If $a,b$ are positive integers, then $[a,b] = ab/(a,b)$. + +**Lemma**: Let $m,n$ be relatively prime positive integers. Then if $d$ is a positive divisor of $mn$, there is a pair of unique positive divisors $d_1$ of $m$ and $d_2$ of $n$ such that $d = d_1 d_2$. Conversely, if $d_1$ and $d_2$ are positive divisors of $m$ and $n$ respectively, then $d = d_1 d_2$ is a positive divisor of $mn$. + +**Dirichlet's Theorem on Primes in Arithmetic Progressions**: Let $a,b$ be relatively prime positive integers. Then the arithmetic progression $an + b$, $n = 1,2,3,...$ contains infinitely many primes. + +**Proposition**: There are infinitely many primes of the form $4n + 3$, where $n$ is a positive integer. + +**Lemma**: If $a$ and $b$ are integers both of the form $4n + 1$, then the product $ab$ is also of this form. + +## Factorization of Integers and the Fermat Numbers + +**Lemma**: If $n$ is an odd positive integer, then there is a one-to-one correspondence between factorizations of $n$ into two positive integers and differences of two squares that equal $n$. + +**Proof**: The Fermat number $F_5 = 2^{2^5} + 1$ is divisible by 641. +$641 = 5⋅2^7 + 1 = 2^4 + 5^4$. So $2^{2^5} + 1 = 2^32 + 1 = 2^4 ⋅ 2^28 + 1$ = $(641 - 5^4)2^28 + 1$. Subsequently, we can rearrange this to pull out 641. + +**Proposition**: Every prime divisor of the Fermat number $F_n = 2^{2^n} + 1$ is of the form $2^{n+2}k + 1$. + +**Lemma**: Let $F_k = 2^{2^k} + 1$ denote the $k$th Fermat number, where $k$ is a nonnegative integer. Then for all positive integers $n$, we have $F_0 F_1 F_2 ... F_{n-1} = F_n - 2$. + +**Theorem**: Let $m,n$ be distinct nonnegative integers. Then the Fermat numbers $F_m$ and $F_n$ are relatively prime. + +**Theorem**: A regular polygon of $n$ sides can be constructed using a ruler and compass if and only if $n$ is of the form $n = 2^a p_1 ... p_i$ where $p_i, i = 1, 2, ..., t$ are distinct Fermat primes and $a$ is a nonnegative integer. + +## Linear Diophantine Equations + +**Theorem**: Let $a$ and $b$ be positive integers with $d = (a,b)$. The equation $ax + by = c$ has no integral solutions if $d ∤ c$. If $d | c$, then there are infinitely many integral solutions. If $x = x_0$, $y = y_0$ is a particular solution, then all solutions are given by $x = x_0 + (b/d) n$, $y = y_0 - (a/d) n$ for some integer $n$. + +## Chapter 3: Congruences <!-- done --> + +## Introduction to Congruences + +**Definition**: If $a$ and $b$ are integers, we say that $a$ is **congruent to b modulo m** if $m ∣ (a-b)$. + +**Proposition**: If $a$ and $b$ are integers, then $a ≡ b$ (mod $m$) if and only if there is an integer $k$ such that $a = b + km$. + +**Proposition**: Let $m$ be a positive integer. Congruences modulo $m$ satisfy the following properties: +- Reflexivity: $a ≡ a$ (mod $m$) +- Symmetry: $a ≡ b$ (mod $m$) ⟹ $b ≡ a$ (mod $m$) +- Transitivity: $a ≡ b$ and $b ≡ c$ (mod $m$) ⟹ $a ≡ c$ (mod $m$) + +**Definition**: A **complete system of residues modulo m** is a set of integers such that every integer is congruent modulo $m$ to exactly one integer of the set. +- ex. $\{0, 1, 2, ..., m-1\}$ is a complete set of residues modulo $m$. +- ex. $\{0, -1, -2, ... -(m-1)\}$ is a complete set of residues modulo $m$. + +**Theorem**: If $a, b, c, m$ are integers with $m > 0$ and $a ≡ b$ (mod $m$), then: +- $a + c ≡ b + c$ (mod $m$) +- $a - c ≡ b - c$ (mod $m$) +- $ac ≡ bc$ (mod $m$) + +**Theorem**: If $a,b,c,m$ are integers with $m > 0$, $d = (c,m)$, and $ac ≡ bc$ (mod $m$), then $a ≡ b$ (mod $m/d$). + +**Theorem**: If $a,b,c,d,m$ are integers with $m > 0$, $a ≡ b$ (mod $m$), and $c ≡ d$ (mod $m$), then +- $a + c ≡ b + d$ (mod $m$) +- $a - c ≡ b - d$ (mod $m$) +- $ac ≡ bd$ (mod $m$) + +**Theorem**: If $r_1 r_2 ... r_m$ is a complete system of residues modulo $m$ and $a$ is a positive integer satisfying $(a,m) = 1$, then $ar_1 + b, a_r_2 + b, ..., ar_m + b$ is a complete system of residues modulo $m$. + +**Theorem**: If $a,b,k,m$ are integers such that $k > 0$, $m > 0$, $a ≡ b$ (mod $m$), then $a^k ≡ b^k$ (mod $m$). +- Proof: $a ≡ b$ (mod $m$), so $m ∣ (a - b)$. Since we may pull $(a-b)$ out of $a^k - b^k$, $m ∣ (a^k - b^k)$. So $a^k ≡ b^k$ (mod $m$). + +**Theorem**: If $a ≡ b$ (mod $m_1$), $a ≡ b$ (mod $m_2$), ..., $a ≡ b$ (mod $m_k$) for integers and positive $m$, then $a ≡ b$ (mod $[m_1,m_2,...,m_k]$) where $[m_1,m_2,...,m_k]$ is the least common multiple of $m_1,m_2,...,m_k$. +- Proof: $a ≡ b$ (mod $m_1$), $a ≡ b$ (mod $m_2$), ..., $a ≡ b$ (mod $m_k$). So $m_1 ∣ (a-b)$, $m_2 ∣ (a-b)$, ..., $m_k ∣ (a-b)$. Therefore, $[m_1,m_2,...,m_k] ∣ (a-b)$, and so $a ≡ b$ (mod $[m_1,m_2,...,m_k]$). + +**Corollary**: If $a ≡ b$ (mod $m_1$), $a ≡ b$ (mod $m_2$), ..., $a ≡ b$ (mod $m_k$) for integers and positive relatively prime $m$, then $a ≡ b$ (mod $m_1 m_2... m_k$). + +**Proposition**: Let $b,m,N$ be positive integers with $b < m$. Then the least positive residue of $b^N$ modulo $m$ can be computed using $O((log_2 m)^2 log_2 N)$ bit operations. + +## Linear Congruences + +A congruence of the form $ax ≡ b$ (mod $m$) for an unknown integer $x$ is called a **linear congruence in one variable**. + +**Theorem**: Let $a,b,m$ be integers with $m > 0$ and $(a,m) = d$. If $d ∤ b$, then $ax ≡ b$ (mod $m$) has no solutions. If $d | b$, then $ax ≡ b$ (mod $m$) has exactly $d$ incongruent solutions modulo $m$. + +**Proposition**: Let $p$ be prime. The positive integer $a$ is its own inverse modulo $p$ if and only if $a ≡ 1$ (mod $p$) or $a ≡ -1$ (mod $p$). + +## The Chinese Remainder Theorem + +**The Chinese Remainder Theorem**: Let $m_1, m_2, ..., m_r$ be *pairwise relatively prime* positive integers. Then the system of congruence +- $x ≡ a_1$ (mod $m_1$) +- $x ≡ a_2$ (mod $m_2$) +- $...$ +- $x ≡ a_r$ (mod $m_r$) + +has a unique solution modulo $M = m_1 m_2 ... m_r$. + +**Lemma**: If $a$ and $b$ are positive integers, then the least positive residue of $2^a - 1$ (mod $2^b - 1$) is $2^r - 1$, where $r$ is the least positive residue of $a$ (mod $b$). + +**Lemma**: If $a$ and $b$ are positive integers, then the greatest common divisor of $2^a - 1$ and $2^b - 1$ is $2^(a,b) - 1$. + +**Proposition**: The positive integers $2^a - 1$ and $2^b - 1$ are relatively prime if and only if $a$ and $b$ are relatively prime. + +## Systems of Linear Congruences + +**Theorem**: Let $a,b,c,d,e,f,m$ be integers with $m > 0$ such that $(Δ, m) = 1$, where $Δ = ad - bc$. Then, the system of congruences +- $ax + by ≡ e$ (mod $m$) +- $cx + dy ≡ f$ (mod $m$) + +has a unique solution modulo $m$ given by +- $x ≡ \hat{Δ} (de - bf)$ (mod $m$) +- $y ≡ \hat{Δ} (af - ce)$ (mod $m$) + +where $\hat{Δ}$ is an inverse of $Δ$ modulo $m$. + +**Definition**: Let $A$ and $B$ be $n×k$ matrices with integer entries, with $(i,j)$th entries $a_ij$ and $b_ij$ respectively. We say that **A is congruent to B modulo m** if $a_ij ≡ b_ij$ (mod $m$) for all pairs $(i,j)$ with $1 ≤ i ≤ n$ and $1 ≤ j ≤ k$. We write $A ≡ B$ (mod $m$) if $A$ is congruent to $B$ (mod $m$). + +**Proposition**: If $A$ and $B$ are $n×k$ matrices with $A ≡ B$ (mod $m$), $C$ is a $k×p$ matrix, and $D$ is a $p×n$ matrix, all with integer entries, then $AC ≡ BC$ (mod $m$) and $DA ≡ DB$ (mod $m$). + +**Definition**: Definition of $\hat{A}$ as an inverse. todo + +**Proposition**: Let $A = \begin{bmatrix} a & b \\ c & d\end{bmatrix}$ be a matrix of integers such that $Δ = det A = ad - bc$ is relatively prime to the positive integer $m$. Then, the matrix $\hat{A} = \hat{Δ} \begin{bmatrix} d & -b \\ -c & a\end{bmatrix}$ is an inverse of $A$ modulo $m$. + +**Definition**: The **adjoint** of an $n×n$ matrix $A$ is the $n×n$ matrix with $(i,j)$th entry $C_ji$, where $C_ji$ is $(-1)^{i+j}$ times the determinant of the matrix obtained by deleting the $i$th row and $j$th column from $A$. The adjoint of $A$ is denoted by $adj(A)$. + +**Theorem**: If $A$ is an $n×n$ matrix with $det(A) ≠ 0$, then $A(adj(A)) = (det A) I$. + +**Proposition**: If $A$ is an $n×n$ matrix with integer entries and $m$ is a positive integer such that $(det A, m) = 1$, then the matrix $\hat{A} = \hat{Δ}(adj A)$ is an inverse of $A$ modulo $m$. + +# Chapter 4: Applications of Congruences <!-- done --> + +## Divisibility Tests + +**Divisibility Test**: If $d|b$ and $j,k$ are positive integers with $j < k$, then $n = (a_k ... a_1 a_0)_b$ is divisible by $d^j$ iff $(a_{j-1} ... a_i a_0)_b$ is divisible by $d^j$. +- ex. todo +- Proof: Since $b ≡ 0$ (mod $d$), $b^j ≡ 0$ (mod d^j). So $d | (a_k a_{k-1} ... a_0)$ if and only if $d | (a_{j-1} ... a_0)$. todo: fix + +**Divisibility Test**: If $d | (b-1)$, then $n = (a_k ... a_1 a_0)$ is divisible by $d$ if and only if $a_k + ... a_1 + a_0$ is divisible by $d$. +- ex. todo + +**Divisibility Test**: If $d | (b+1)$, then $n = (a_k ... a_1 a_0)$ is divisible by $d$ if and only if $(-1)^k a_k + ... -a_1 + a_0$ is divisible by $d$. +- ex. Let $n = (1001001111)_2$. Then $3 ∣ n$ as $n ≡ 1 - 1 + 1 - 1 + 0 - 0 + 1 - 0 + 0 - 1 ≡ 0$ (mod 3) and $3 ∣ 2 + 1$. + +# Chapter 5: Some Special Congruences <!-- done --> + +## Wilson's Theorem and Fermat's Little Theorem + +**Wilson's Theorem**: If $p$ is prime, then $(p-1)! ≡ -1$ (mod $p$). +- Proof: inverses cancel. The only numbers that are their own inverses in a prime field are $1$ and $p-1$. So $(p-1)! ≡ p-1 ≡ -1$ (mod $p$). + +**Corollary**: If $n$ is a positive integer satisfying $(n-1)! ≡ -1$ (mod $n$), $n$ is prime. +- Proof: Assume $n$ is composite. Proof by contradiction. todo + +**Fermat's Little Theorem**: If $p$ is prime and $a$ is a positive integer with $p ∤ a$, then $a^{p-1} ≡ 1$ (mod $p$). + +**Corollary**: If $p$ is a prime and $a$ is a positive integer with $p ∤ a$, then $a^p ≡ a$ (mod $p$). +- Proof: trivial. + +**Corollary**: If $p$ is prime and $a$ is an integer with $p ∤ a$, then $a^{p-2}$ is an inverse of $a$ modulo $p$. +- Proof: Fermat's little theorem tells us that $a^{p-1} ≡ 1$ (mod $p$). $a^{p-1} = aa^{p-2}$. + +**Corollary**: If $p$ is prime and $a,b$ are positive integers with $p ∤ a$, then the solutions of $ax ≡ b$ (mod $p$) are the integers $x ≡ a^{p-2}b$ (mod $p$). +- Proof: Take $ax ≡ b$ (mod $p$). Since $p$ does not divide $a$, we know $a^{p-2}$ is an inverse of $a$ (mod $p$). So $x ≡ a^{p-2}b$ (mod $p$). + +## Pseudoprimes + +**Definition**: Let $b$ be a positive integer. If $n$ is a composite positive integer and $b^n ≡ b$ (mod $n$), then $n$ is a **pseudoprime to the base b**. +- ex. 341 is a pseudoprime to the base 2. $2^340 ≡ 1$ (mod 341), and so $2^341 ≡ 2$ (mod 341). + +**Lemma**: If $d$ and $n$ are positive integers with $d ∣ n$, then $2^d - 1 ∣ 2^n - 1$. +- Proof: Since $d ∣ n$, $dt = n$ for some $t$. We have the identity $x^t - 1 = (x-1)(x^{t-1} + x^{t-2} + ... + 1)$, and so $2^n - 1 = 2^dt - 1 = (2^d - 1)(2^{d(t-1)} + x^{d(t-2)} + ... + 1)$. + +**Proof**: There are infinitely many pseudoprimes to the base 2. +We may prove this by showing that if $n$ is an odd pseudoprime to the base 2, $m=2^n - 1$ is also an odd pseudoprime to the base 2. +Let $n$ be an odd pseudoprime. Then $2^{n-1} ≡ 1$ (mod $n$) and $n$ is composite by definition. Let $m = 2^{n-1}$. It is composite, as $n$ is composite (by the above lemma). As $2^n - 2 = kn$, there is an integer $k$ s.t. $2^{m-1} = 2^{2^n - 2} = 2^{kn}$. todo: finish + +**Definition**: A composite integer that satisfies $b^{n-1} ≡ 1$ (mod $n$) for all positive integers $b$ with $(b,n)=1$ is called a **Carmichael number**. +- ex. $561 = (3)(11)(17)$ is a Carmichael number. If $(b, 561) = 1$, then $(b,3)=(b,11)=(b,17)=1$. So $b^2 ≡ 1$ (mod 3), $b^10 ≡ 1$ (mod 11), $b^16 ≡ 1$ (mod 17). So $b^560$... todo: finish + +**Theorem**: If $n = q_1 q_2 ... q_k$, where $q_j$ is a distinct prime satisfying $(q_j - 1) | (n - 1)$ for all $j$, then $n$ is a Carmichael number. + +**Definition**: Let $n$ be a positive integer with $n-1 = 2^s t$, where $s$ is a nonnegative integer and $t$ is an odd positive integer. We say that $n$ **passes Miller's test for the base b** if either $b^1 ≡ 1$ (mod $n$) or $b^{2^j t} ≡ -1$ (mod $n$) for some $j$ with $0 ≤ j ≤ s - 1$. +- ex. todo + +**Theorem**: If $n$ is prime and $b$ is a positive integer with $n ∤ b$, then $n$ passes Miller's test for the base $b$. + +**Definition**: If $n$ is composite and passes Miller's test for the base $b$, then we say $n$ is a **strong pseudoprime to the base b**. Strong pseudoprimes are exceedingly rare. +- ex. Let $n = 2047 = 23*89$. Then $2^2046 = (2^11)^186 = 2048^186 ≡ 1$ (mod 2047), so 2047 is a pseudoprime to the base 2. todo + +**Proof**: There are infinitely many strong pseudoprimes to the base 2. +- We may prove this by showing that if $n$ is a pseudoprime to the base 2, $N = 2^n - 1$ is a *strong* pseudoprime to the base 2. +- todo + +**Theorem**: If $n$ is an odd composite positive integer, then $n$ passes Miller's test for at most $(n-1)/4$ bases $b$ with $1 ≤ b ≤ n-1$. + +**Rabin's Probabilistic Primality Test** +- Let $n$ be a positive integer. Pick $k$ different positive integers less than $n$ and perform Miller's test on $n$ for each of those bases. If $n$ is composite the probability that $n$ passes all $k$ tests is less than (1/4)^k. + +**Conjecture**: For every composite positive integer $n$, there is a base $b$ with $b < 70 (log_2 n)^2$ such that $n$ fails Miller's test for the base $b$. If this conjecture is true, the following proposition provides a rapid primality test: + +**Proposition**: If the generalized Riemann hypothesis is valid, then there exists an algorithm to determine whether a positive integer $n$ is prime using $O((log_2 n)^5)$ bit operations. +- Proof: Let $b$ be a positive integer less than $n$. Note that Miller's test takes $O((log_2 b)^2)$ bit operations. Assuming the generalized Riemann hypothesis is true, if $n$ is composite, there is a base $b$ with $b < 70 (log_2 n)^2$ such that $n$ fails Miller's test for $b$. To discover this $b$, then, requires less than $O((log_n )^5)$ bit operations. + +## Euler's theorem + +**Euler's Totient Function**: Let $n$ be a positive integer. **Euler's totient function** / the **Euler phi-function** $ϕ(n)$ is defined to be the number of positive integers not exceeding $n$ which are relatively prime to $n$. + +**Definition**: A **reduced residue system modulo n** is a set of $ϕ(n)$ integers such that each element of the set is relatively prime to $n$, and no two different elements of the set are congruent modulo $n$. +- ex. $\{1, 3, 5, 7\}$ is a reduced residue system modulo 8. + +**Theorem**: If $r_1, r_2, ..., r_{ϕ(n)}$ is a reduced residue system modulo $n$, and if $a$ is a positive integer with $(a, n) = 1$, then the set $ar_1, ar_2, ..., ar_{ϕ(n)}$ is also a reduced residue system modulo $n$. +- Proof: Consider that $(a,n) = 1$... intuitive. todo. + +**Euler's Theorem**: If $m$ is a positive integer and $a$ is an integer with $(a,m) = 1$, then $a^{ϕ(m)} ≡ 1$ (mod $m$). +- ex. $\{1,3,5,7\}$ (mod 8): $3^{ϕ(8)} = 3^4 ≡ 1$ (mod 8) + +**Corollary**: Euler's Theorem is useful for finding inverses modulo $m$. If $a$ and $m$ are relatively prime, $aa^{ϕ(m)-1} = a^{ϕ(m)} ≡ 1$ (mod $m$). + +# Chapter 6: Multiplicative Functions <!-- done --> + +## The Euler ϕ-Function + +**Definition**: An **arithmetic function** is defined for all positive integers. + +**Definition**: An arithmetic function $f$ is **multiplicative** if $f(mn) = f(m)f(n)$ whenever $m$ and $n$ are relatively prime. + +**Theorem**: If $f$ is a multiplicative function and if $n = p_1^{a_1} p_2^{a_2} ... p_s^{a_s}$ is the prime power factorization of the positive integer $n$, then $f(n) = f(p_1^{a_1})f(p_2^{a_2})...f(p_s^{a_s})$. +- Proof: trivial. Prime factors are relatively prime to each other. + +**Theorem**: If $p$ is prime, then $ϕ(p) = p - 1$. Conversely, if $p$ is a positive integer with $ϕ(p) = p - 1$, then $p$ is prime. +- Proof: Primes are not factorable. Every number less than a prime is relatively prime to the prime. + +**Theorem**: Let $p$ be a prime and $a$ a positive integer. Then $ϕ(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)$. +- Proof: There are $p^{a-1}$ numbers that divide some $p^a$. So there are $p^a - p^{a-1}$ numbers that do not divide $p^a$. + +**Theorem**: The Euler ϕ-function is multiplicative. That is, for some relatively prime positive integers $m$ and $n$, $ϕ(mn) = ϕ(m)ϕ(n)$. +- Proof: somewhat intuitive. todo + +**Theorem**: Let $n = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ be the prime power factorization of the positive integer $n$. Then $ϕ(n) = n(1-\frac1p_1)(1-\frac1p_2)...(1-\frac1p_k)$. +- Proof: ϕ is multiplicative, so $ϕ(n) = ϕ(p_1^{a_1}) ϕ(p_2^{a_2}) ... ϕ(p_k^{a_k})$. From an above theorem, we know $ϕ(p_j^{a_j}) = p_j^{a_j} - p_j^{a_j - 1}$. $p_j^{a_j} - p_j^{a_j - 1} = p_j^{a_j}(1-\frac1p_j)$, so the product of all $p_j^{a_j} = n$ and so $ϕ(n) = n(1-\frac1p_1)(1-\frac1p_2)...(1-\frac1p_k)$. + +**Theorem**: Let $n$ be a positive integer. Then $\sum_{d ∣ n} ϕ(d) = n$. +- ex. Consider $n=18$. Then... todo. + +## The Sum and Number of Divisors + +**Definition**: The **sum of the divisors function** $σ$ is defined by setting $σ(n)$ equal to the sum of all the positive divisors of $n$. + +**Definition**: The **number of the divisors function** $τ$ is defined by setting $τ(n)$ equal to the number of positive divisors of $n$. + +**Theorem**: If $f$ is a multiplicative function, then the arithmetic function $F(n) = \sum_{d ∣ n} f(d)$ is also multiplicative. +- Proof: Trivial. + +**Lemma**: For a prime $p$ and positive integer $a$, $σ(p^a) = (1+p+p^2+...p^a) = \frac{p^{a+1} - 1}{p-1}$ and $τ(p^a) = a + 1$. + +**Theorem**: Consider a positive integer $n$ with prime factorization $n = p_1^{a_1} p_2^{a_2} ... p_s^{a_s}$. Then $σ(n) = Π_{j=1}^s \frac{p_j^{a_j+1} - 1}{p_j-1}$ and $τ(n) = Π_{j=1}^s (a_j + 1)$. +- Proof: Trivial. + +## Perfect Numbers and Mersenne Primes + +**Definition**: If $n$ is a positive integer and $σ(n) = 2n$, then $n$ is called a **perfect number**. +- ex. $σ(6) = 1 + 2 + 3 + 6 = 12$, so 6 is perfect. +- ex. $σ(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56$, so 28 is perfect. + +**Theorem**: The positive integer $n$ is an even perfect number if and only if $n = 2^{m-1}(2^m - 1)$ where $m$ is a positive integer such that $2^m - 1$ is prime. +- ex. + +**Theorem**: If $m$ is a positive integer and $2^m - 1$ is prime, then $m$ must be prime. +- Proof: If $m$ is not prime, $2^m - 1$ must be composite: $2^ab - 1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + ... + 2^a + 1)$. + +**Definition**: Given a positive integer $m$, $M_m = 2^m - 1$ is called the $m$th **Mersenne number**. Given a positive prime integer $p$ and $M_p = 2^p - 1$ is also prime, $M_p$ is called a **Mersenne prime**. +- ex. $M_7 = 2^7 - 1 = 127$ +- ex. $M_11 = 2^11 - 1 = 2047 = 23*89$ + +**Theorem**: If $p$ is an odd prime, then any divisor of the Mersenne number $M_p = 2^p - 1$ is of the form $2kp + 1$, for some positive integer $k$. + +**The Lucas-Lehmer Test**: Let $p$ be a prime and $M_p = 2^p - 1$ be the $p$th Mersenne number. Consider a recursive sequence of integers with $r_1 = 4$ and $r_k ≡ r_{k-1}^2 - 2$ (mod $M_p$) for $r_k < M_p$. Then, $M_p$ is prime if and only if $r_{p-1} ≡ 0$ (mod $M_p$). +- ex. Consider $M_5 = 2^5 = 31$. Then $r_1 = 4$, $r_2 ≡ 4^2 - 2 = 14$ (mod 31), $r_3 ≡ 14^2 - 2 ≡ 8$ (mod 31), $r_4 ≡ 8^2 - 2 ≡ 0$ (mod 31). $r_{5-1} ≡ 0$ (mod 31), so $M_5 = 31$ is prime. + +**Corollary**: Let $p$ be prime and let $M_p = 2^p - 1$ denote the $p$th Mersenne number. It is possible to determine whether $M_p$ is prime using $O(p^3)$ bit operations. + +known mersenne primes table + +Mersenne primes are of interest because of their ease in location and verification: the largest known prime, at any given time, is typically a Mersenne prime. It has been conjectured, but not proven, that there are infinitely many Mersenne primes. + +# Chapter 7: Cryptology + +**Caeser Cipher**: $C ≡ P + 3$ (mod 26) +- ex. todo + +Ciphers may be described by a **shift transformation**: $C ≡ P+k$ (mod 26), for some key $k$. More generally, ciphers of the form $C ≡ aP+b$ (mod 26) for some integers $a,b$ such that $(a,26)=1$ are considered **affine transformations**. This $(a,26)=1$ is so that as $P$ runs through a complete system of distinct residues, $C$ also does. + +The *inverse* relationship is given by $P ≡ \hat{a} (C-b)$ (mod 26), where $\hat{a}$ is an inverse of $a$ (mod 26). + +Ciphers like these encrypt *each character individually*, making them 1) trivially easy to bruteforce and 2) subject to *frequency analysis*. +- ex. if we know we are looking for $C ≡ P+k$ (mod 26): say the most common letter is P. we then set that equal to $e$, the most common letter in English. So $15_p ≡ 4_e + k$ (mod 26), so $k=11$ and we have out solution. +- ex. if we know we are looking for $C ≡ aP+b$ (mod 26): say the most common letters are $L$ and $U$. We then set those equal to $E$ and $T$, the first and second most common letters in English. Leaving us with two equations: $4_E a + b ≡ 11_L$ and $19_T a + b ≡ 20_U$ (mod 26). This is solvable: $a ≡ \hat{Δ}(d11-b20)$ and $b ≡ \hat{Δ}(a20-c11)$ + +# Chapter 8: Primitive Roots + +## The Order of an Integer and Primitive Roots + +**Definition**: Let $a$ and $m$ be relatively prime positive integers. Then, the least positive integer $x$ such that $a^x ≡ 1$ (mod $m$) is called the **order of a modulo m**. +- ex. $2^3 ≡ 1$ (mod 7), so $ord_7 2 = 3$. + +**Theorem**: If $a$ and $n$ are relatively prime integers with $n > 0$, then the positive integer $x$ is a solution of the congruence $a^x ≡ 1$ (mod $n$) if and only if $ord_n a ∣ x$. +- Proof: trivial. + +**Corollary**: If $a$ and $n$ are relatively prime integers with $n > 0$, then $ord_n a | ϕ(n)$. +- Proof: $(a,n) = 1$, so $a^{ϕ(n)} ≡ 1$ (mod $n$) by Euler's theorem. So by the above theorem, $a^x ≡ 1$ (mon $n$). + +**Theorem**: If $a$ and $n$ are relatively prime integers with $n > 0$, then $a^i ≡ a^j$ (mod $n$) where $i$ and $j$ are nonnegative integers if and only if $i ≡ j$ (mod $ord_n a$). +- ex. todo + +**Definition**: If $r$ and $n$ are relatively prime integers with $n > 0$ and $ord_n r = ϕ(n)$, then $r$ us called a **primitive root modulo n**. Not all integers have primitive roots. +- ex. $ord_7 3 = 6 = ϕ(7)$, so $3$ is a primitive root modulo 7. + +**Theorem**: If $r$ and $n$ are relatively prime positive integers with $n > 0$, and if $r$ is a primitive root modulo $n$, then the integers $r^1, r^2, ..., r^{ϕ(n)}$ form a reduced residue set modulo $n$. +- ex. todo + +**Theorem**: If $ord_m a = t$ and $u$ is a positive integer, then $ord_m (a^u) = t/(t,u)$. +- ex. todo + +**Corollary**: Let $r$ be a primitive root modulo $M$ where $m$ is an integer > 1. Then $r^u$ is a primitive root modulo $m$ if and only if $(u, ϕ(m)) = 1$. + +**Theorem**: If the positive integer $m$ has a primitive root, then it has a total of $ϕ(ϕ(m))$ incongruent primitive roots. + +## Primitive Roots for Primes + +**Definition**: Let $f(x)$ be a polynomial with integer coefficients. We say that an integer $c$ is a **root of f(x) modulo m** if $f(c) ≡ 0$ (mod $m$). It is easy to see that if $c$ is a root of $f(x)$ modulo $m$, then every integer congruent to $c$ modulo $m$ is also a root. + +**Lagrange's Theorem**: Let $f(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0$ be a polynomial of degree $n$ with integer coefficients and with leading coefficient $a_n$ not divisible by $p$. Then $f(x)$ has at most $n$ incongruent roots modulo $p$. + +**Theorem**: Let $p$ be prime and let $d$ be a divisor of $p-1$. Then the polynomial $x^d - 1$ has exactly $d$ incongruent roots modulo $p$. + +**Theorem**: Let $p$ be prime and let $d$ be a positive divisor of $p-1$. Then the number of incongruent integers of order $d$ modulo $p$ is equal to $ϕ(d)$. + +**Corollary**: Every prime has a primitive root. + +## Existence of Primitive Roots + +**Theorem**: If $p$ is an odd prime with a primitive root $r$, then either $r$ or $r+p$ is a primitive root modulo $p^2$. + +**Theorem**: Let $p$ be an odd prime, then $p^k$ has a primitive root for all positive integers $k$. Moreover, if $r$ is a primitive root modulo $p^2$, then $r$ is a primitive root modulo $p^k$, for all positive integers $k$. + +**Theorem**: If $a$ is an odd integer, then for some integer $k > 3$ $a^{ϕ(2^k)/2} = a^{2^{k-2}} ≡ 1$ (mod $2^k$). + +**Theorem**: Let $k ≥ 3$ be an integer. Then $ord_{2^k} 5 = ϕ(2^k)/2 = 2^{k-2}$. + +**Theorem**: If $n$ is a positive integer that is not a prime power or twice a prime power, then $n$ does not have a primitive root. + +**Theorem**: If $p$ is an odd prime and $t$ is a positive integer, then $2p^t$ has a primitive root. If $r$ is an primitive root modulo $p^t$, if it is odd $r$ is also a primitive root modulo $2p^t$, and if it is even $r + p^t$ is a primitive root modulo $2p^t$. + +**Theorem**: The positive integer $n$ has a primitive root if and only if $n = 2,4,p^t,2p^t$ for an odd prime $p$ and positive integer $t$. + +## Index Arithmetic + +**Definition**: Let $m$ be a positive integer with primitive root $r$. If $a$ is a positive integer with $(a,m) = 1$, then the unique integer $x$ with $1 ≤ x ≤ ϕ(m)$ and $r^x ≡ a$ (mod $m$) is called the **index of a to the base r modulo m**. With this definition, we have $a ≡ r^{ind_r a}$ (mod $m$). + +**Theorem**: Let $m$ be a positive integer with primitive root $r$, and let $a$ and $b$ be integers relatively prime to $m$. Then: +- $ind_r 1 ≡ 0$ (mod $ϕ(m)$) +- $ind_r (ab) ≡ ind_r a + ind_r b$ (mod $ϕ(m)$) +- $ind_r a^k ≡ k⋅ind_r a$ (mod $ϕ(m)$) for a positive integer $k$. + +**Definition**: If $m$ and $k$ are positive integers and $a$ is an integer relatively prime to $m$, then $a$ is a **kth power residue of m** if the congruence $x^k ≡ a$ (mod $m$) has a solution. + +**Theorem**: Let $m$ be a positive integer with a primitive root. If $k$ is a positive integer and $a$ is an integer relatively prime to $m$, then the congruence $x^k ≡ a$ (mod $m$) has a solution if and only if $a^{ϕ(m)/d} ≡ 1$ (mod $m$), where $d = (k, ϕ(m))$. + +**Corollary**: If there are solutions of $x^k ≡ a$ (mod $m$), then there are exactly $d$ incongruent solutions modulo $m$. + +**Theorem**: If $n$ is an odd composite positive integer, then $n$ passes Miller's test for at most $(n-1)/4$ bases $b$ with $1 ≤ b < n-1$. + +**Lemma**: Let $p$ be an odd prime and let $e,q$ be positive integers. Then the number of incongruent solutions of the congruence $x^{q-1} ≡ 1$ (mod $p^e$) is $(q,p^{e-1}(p-1))$. + +## Primality Testing Using Primitive Roots + +**Theorem**: If $n$ is a positive integer and if an integer $x$ exists such that $x^{n-1} ≡ 1$ (mod $n$) and $x^{(n-1)/q} ≢ 1$ (mod $n$) for all prime divisors $q$ of $n-1$, then $n$ is prime. + +**Corollary**: If $n$ is an odd positive integer and $x$ is a positive integer such that $x^{(n-1)/2} ≡ -1$ (mod $n$) and $x^{(n-1)/q} ≢ 1$ (mod $n$) for all odd prime divisors $q$ of $n-1$, then $n$ is prime. + +**Theorem**: If $n$ is composite, it can be proved with $O((log_2 n)^2)$ bit operations. + +**Theorem**: If $n$ is prime, it can be proved with $O((log_2 n)^4)$ bit operations. + +## Universal Exponents + +## Pseudo-random Numbers + +## The Splicing of Telephone Cables |