0. Elementary stuff you should know how to prove by now
- Division algorithm for integers/polynomials in an integral domain
- Bezout
- Existence and uniqueness of prime factorisation
1. For $p$ prime, $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$ is cyclic
In other words, there always exists a primitive element $\mod p$ for $p$ prime. This theorem is very well-known, and feels trivial. It's not - there is a lot of groundwork that simply can't be avoided.
Intermediate results:
1.1 Lagrange's theorem for polynomials
In an integral domain, a polynomial of degree $d$ can have at most $d$ roots.
Proof:
We induct on the degree of the polynomial.
For $n=1$, write $p(x)=ax+b$, $a \neq 0$.
Suppose there are two distinct solutions, $x$ and $y$. Then, by subtracting, $a(x-y)=0$. In an integral domain, this implies $x=y$.
For the inductive step, the division algorithm for polynomials (which is valid in an integral domain) implies that for any root $x_0$ of a polynomial $p$, $p$ can be factored as $(x-x_0)g(x)$. In an integral domain, the degree of a product of polynomials is the sum of the degrees of the factors. Thus, $p$ has at most one more root than $g$, and so at most $n$ roots in total, by the induction hypothesis. $\square$
1.2 For $p$ prime, $F = \mathbb{Z}/p\mathbb{Z}$ is a field
Proof:
Pick any non-zero element $a$. We need to find an inverse for $a$.
Define a map $\phi_a : F \to F$ by $\phi_a(z)=az$. This is an injection, as $F$ is an integral domain (immediate from the definition of a prime number). An injection from a finite set to itself must necessarily be a surjection. Thus, $ab=1$ for some $b \in F$, proving that $a$ has a multiplicative inverse. $\square$
1.3 The Euler totient function $\phi$ is multiplicative
Note: $\phi$ is not totally multiplicative. E.g. $\phi(2)=1$, $\phi(4)=2$.
We define $\phi(n)$ as the number of positive integers less than $n$ that are coprime to $n$, and observe that Bezout implies that $\phi(n)= \left| (\mathbb{Z}/n\mathbb{Z})^\times \right|$.
Proof:
The Chinese Remainder Theorem gives a bijection (more precisely, an isomorphism) between $\left(\mathbb{Z}/m_1m_2\mathbb{Z}\right)^\times$ and $\left(\mathbb{Z}/m_1\mathbb{Z}\right)^\times\times\left(\mathbb{Z}/m_2\mathbb{Z}\right)^\times$ whenever $m_1$ and $m_2$ are coprime, giving $\phi(m_1m_2)=\phi(m_1)\phi(m_2)$. $\square$
1.4 The Eulier totient function has the property: $\displaystyle \sum_{d \mid n} \phi(d) = n$.
Proof:
We establish the fact that for any multiplicative function $\varphi$, $F(n) = \displaystyle \sum_{d \mid n} \varphi(d)$ is also multiplicative.1
Let $m$ and $n$ be coprime. Then:
$$F(mn)=\displaystyle \sum_{d \mid m_1} \varphi(d) = \sum_{d_1 \mid m, d_2 \mid n} \varphi(d_1d_2)$$$$ = \sum_{d_1 \mid m, d_2 \mid n} \varphi(d_1)\varphi(d_2) = \left(\sum_{d_1 \mid m} \varphi(d_1)\right)\left(\sum_{d_2 \mid n} \varphi(d_2)\right)$$$$=F(m)F(n)$$
Observe that $\phi(p^k)=p^{k-1}(p-1)$, so $F_\phi(p^k)=1 + (p-1) + \dots + (p^k-p^{k-1}) = p^k$. Thus, $F_\phi(n)=F_\phi(p_1^{n_1}\dots p_k^{n_k})=p_1^{n_1}\dots p_k^{n_k}=n$. $\square$
Proof of 1.
For each divisor $d$ of $p-1$, we show that if there is an element of order $d$, there must in fact be (exactly) $\phi(d)$ elements of order $d$. Thus, if $S_d$ is the set of elements of order $d$, then $|S_d|=\phi(d)$, or $|S_d|=0$. Since $\displaystyle \sum_{d \mid p-1} (\phi(d) - |S_d|) = p-1 - (p-1) = 0$, it follows that $|S_d|=\phi(d)$ for each $d$ dividing $p-1$ (if any of the $|S_d|$ are empty, the above formula can't hold), and so in particular $S_{p-1}$ is non-empty.
Let $a$ be an element of order $d$. By Lagrange's theorem $x^{d} \equiv 1 \mod p$ has at most $d$ solutions. Any element of order $d$ is a solution to this equation. But we can list $d$ distinct solutions: $1,a,a^2,\ldots,a^{d-1}$. Observe that $a^k$ has order $d$ exactly when $(d,k)=1$. Thus, there are exactly $\phi(d)$ elements of order $d$. $\square$
We call the elements of order $p-1$ the primitive roots $\mod p$. From the above, there are $\phi(p-1)$ of them.
2. For $p$ an odd prime, $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$ is cyclic for any $k$.
We prove this by exhibiting an element of order $p^{k-1}(p-1)$.
Let $g_1$ be a primitive element of $\left(\mathbb{Z}/p\mathbb{Z})\right)^\times$.
Compute $g_1^{p-1}-1 \mod p^2$. If it's zero, set $g=g_1+p$. If it's non-zero, set $g=g_1$.
Then $g$ generates $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$.
We have chosen $g$ such that $g^{p-1}=1+bp$, where $b$ is coprime to $p$.
Thus, $g^{p^{k-1}(p-1)}=(1+bp)^{p^{k-1}}=1+bp{p^{k-1} \choose 1}+ \dots \equiv 1 \mod p^{k}$. So the order of $g$ (mod $p^k$) divides $p^{k-1}(p-1)$, and doesn't divide $p-1$.
Noting that $g^{p^{k-2}(p-1)}=(1+bp)^{p^{k-2}}=1+bp{p^{k-2} \choose 1} + (bp)^2{p^{k-2} \choose 2} + \dots \not\equiv 1 \mod p^{k}$, we can conclude that $g$ has order exactly $p^{k-1}(p-1)$, and so $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$ is cyclic. $\square$
3. Reserved space for other relevant results/properties proved on example sheets
In other words, there always exists a primitive element $\mod p$ for $p$ prime. This theorem is very well-known, and feels trivial. It's not - there is a lot of groundwork that simply can't be avoided.
Intermediate results:
1.1 Lagrange's theorem for polynomials
In an integral domain, a polynomial of degree $d$ can have at most $d$ roots.
Proof:
We induct on the degree of the polynomial.
For $n=1$, write $p(x)=ax+b$, $a \neq 0$.
Suppose there are two distinct solutions, $x$ and $y$. Then, by subtracting, $a(x-y)=0$. In an integral domain, this implies $x=y$.
For the inductive step, the division algorithm for polynomials (which is valid in an integral domain) implies that for any root $x_0$ of a polynomial $p$, $p$ can be factored as $(x-x_0)g(x)$. In an integral domain, the degree of a product of polynomials is the sum of the degrees of the factors. Thus, $p$ has at most one more root than $g$, and so at most $n$ roots in total, by the induction hypothesis. $\square$
1.2 For $p$ prime, $F = \mathbb{Z}/p\mathbb{Z}$ is a field
Proof:
Pick any non-zero element $a$. We need to find an inverse for $a$.
Define a map $\phi_a : F \to F$ by $\phi_a(z)=az$. This is an injection, as $F$ is an integral domain (immediate from the definition of a prime number). An injection from a finite set to itself must necessarily be a surjection. Thus, $ab=1$ for some $b \in F$, proving that $a$ has a multiplicative inverse. $\square$
1.3 The Euler totient function $\phi$ is multiplicative
Note: $\phi$ is not totally multiplicative. E.g. $\phi(2)=1$, $\phi(4)=2$.
We define $\phi(n)$ as the number of positive integers less than $n$ that are coprime to $n$, and observe that Bezout implies that $\phi(n)= \left| (\mathbb{Z}/n\mathbb{Z})^\times \right|$.
Proof:
The Chinese Remainder Theorem gives a bijection (more precisely, an isomorphism) between $\left(\mathbb{Z}/m_1m_2\mathbb{Z}\right)^\times$ and $\left(\mathbb{Z}/m_1\mathbb{Z}\right)^\times\times\left(\mathbb{Z}/m_2\mathbb{Z}\right)^\times$ whenever $m_1$ and $m_2$ are coprime, giving $\phi(m_1m_2)=\phi(m_1)\phi(m_2)$. $\square$
1.4 The Eulier totient function has the property: $\displaystyle \sum_{d \mid n} \phi(d) = n$.
Proof:
We establish the fact that for any multiplicative function $\varphi$, $F(n) = \displaystyle \sum_{d \mid n} \varphi(d)$ is also multiplicative.1
Let $m$ and $n$ be coprime. Then:
$$F(mn)=\displaystyle \sum_{d \mid m_1} \varphi(d) = \sum_{d_1 \mid m, d_2 \mid n} \varphi(d_1d_2)$$$$ = \sum_{d_1 \mid m, d_2 \mid n} \varphi(d_1)\varphi(d_2) = \left(\sum_{d_1 \mid m} \varphi(d_1)\right)\left(\sum_{d_2 \mid n} \varphi(d_2)\right)$$$$=F(m)F(n)$$
Observe that $\phi(p^k)=p^{k-1}(p-1)$, so $F_\phi(p^k)=1 + (p-1) + \dots + (p^k-p^{k-1}) = p^k$. Thus, $F_\phi(n)=F_\phi(p_1^{n_1}\dots p_k^{n_k})=p_1^{n_1}\dots p_k^{n_k}=n$. $\square$
Proof of 1.
For each divisor $d$ of $p-1$, we show that if there is an element of order $d$, there must in fact be (exactly) $\phi(d)$ elements of order $d$. Thus, if $S_d$ is the set of elements of order $d$, then $|S_d|=\phi(d)$, or $|S_d|=0$. Since $\displaystyle \sum_{d \mid p-1} (\phi(d) - |S_d|) = p-1 - (p-1) = 0$, it follows that $|S_d|=\phi(d)$ for each $d$ dividing $p-1$ (if any of the $|S_d|$ are empty, the above formula can't hold), and so in particular $S_{p-1}$ is non-empty.
Let $a$ be an element of order $d$. By Lagrange's theorem $x^{d} \equiv 1 \mod p$ has at most $d$ solutions. Any element of order $d$ is a solution to this equation. But we can list $d$ distinct solutions: $1,a,a^2,\ldots,a^{d-1}$. Observe that $a^k$ has order $d$ exactly when $(d,k)=1$. Thus, there are exactly $\phi(d)$ elements of order $d$. $\square$
We call the elements of order $p-1$ the primitive roots $\mod p$. From the above, there are $\phi(p-1)$ of them.
2. For $p$ an odd prime, $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$ is cyclic for any $k$.
We prove this by exhibiting an element of order $p^{k-1}(p-1)$.
Let $g_1$ be a primitive element of $\left(\mathbb{Z}/p\mathbb{Z})\right)^\times$.
Compute $g_1^{p-1}-1 \mod p^2$. If it's zero, set $g=g_1+p$. If it's non-zero, set $g=g_1$.
Then $g$ generates $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$.
We have chosen $g$ such that $g^{p-1}=1+bp$, where $b$ is coprime to $p$.
Thus, $g^{p^{k-1}(p-1)}=(1+bp)^{p^{k-1}}=1+bp{p^{k-1} \choose 1}+ \dots \equiv 1 \mod p^{k}$. So the order of $g$ (mod $p^k$) divides $p^{k-1}(p-1)$, and doesn't divide $p-1$.
Noting that $g^{p^{k-2}(p-1)}=(1+bp)^{p^{k-2}}=1+bp{p^{k-2} \choose 1} + (bp)^2{p^{k-2} \choose 2} + \dots \not\equiv 1 \mod p^{k}$, we can conclude that $g$ has order exactly $p^{k-1}(p-1)$, and so $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$ is cyclic. $\square$
3. Reserved space for other relevant results/properties proved on example sheets
1 Note to self: it feels like there is something more to be said here. Link to lattices?
No comments:
Post a Comment