A long time ago, I assumed on a whim that the multiplicative group of integers mod \(p\) is isomorphic to the additive group of integers mod \(p-1\), where \(p\) is prime, to prove Fermat's little theorem and promised to later prove that this is indeed the case.
Well, it turns out that this is indeed the case!
At the time, I had neither the tools nor the mathematical maturity to undertake this task, which was evident by my inability to even know where to begin, but I have now gathered sufficient knowledge to finish what I started; I am true to my promises, even if it takes me a while to fulfill them!
Let us begin by proving that every cyclic group of order \(n\) is isomorphic to the additive group of integers mod \(n\), henceforth denoted by \(\mathbb Z_n\). I want to later on show that the multiplicative group of integers mod \(p\), where \(p\) is prime, is cyclic and thus prove our "big" claim. Let us denote this latter group by \(\mathbb Z_p^\times\).
Lemma 1. Every cyclic group of order \(n\) is isomorphic \(\mathbb Z_n\).
Proof. Let \(G\) be a cyclic group of order \(n\). Then there exists \(g\in G\) such that \(g^n=e\), where \(e\) is the identity, and \(\langle g\rangle=G\), that is, \(g\) generates \(G\). Observe that for any integer \(m\), by the division algorithm, \(m=qn+r\), where \(q\) and \(r\) are integers and \(0\leqslant r<n\). Therefore,
$$g^m=g^{qn+r}=g^{qn}g^r=eq^r=q^r,$$
which implies that \(g^m\) is congruent to \(g^r\) mod \(n\), if I may. We use this fact to define
$$\begin{align}\varphi:G\to\mathbb Z_n\newline g^{\left[k\right]}\mapsto \left[k\right]\end{align}$$
for any integer \(k\), where, naturally, \(\left[k\right]\) is its representative mod \(n\). Clearly, \(\varphi\) is well-defined, surjective, and injective. It is therefore a bijective map from \(G\) to \(\mathbb Z\). Moreover,
$$\varphi\left(g^{\left[a\right]}g^{\left[b\right]}\right)=\varphi\left(g^{\left[a\right]+\left[b\right]}\right)=\left[a\right]+\left[b\right]= \varphi\left(g^{\left[a\right]}\right)+\varphi\left(g^{\left[b\right]}\right).$$
Hence, \(\varphi\) is a bijective homomorphism and thus an isomorphism. \(\blacksquare\)
I will now show that if an abelian group has two elements of order \(m\) and \(n\), then it has an element of order \(\text{lcm}\left(m,n\right)\). I will later use this fact to show that \(\mathbb Z_p^\times\), where \(p\) is prime, has a generator (and is thus cyclic: food for our first lemma!). It goes without saying that \(\mathbb Z_p^\times\) is abelian.
Lemma 2. If an abelian group \(G\) has two elements of order \(m\) and \(n\), then \(G\) has an element of order \(\text{lcm}\left(m,n\right)\).
$$m=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdots\cdot p_k^{\alpha_k}\qquad\text{and}\qquad n=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\dots\cdot p_k^{\beta_k}$$
be the factorization into powers of primes of \(m\) and \(n\), and let \(\gamma_i=\max\left\{\alpha_i,\beta_i\right\}\) for every \(i\in\left\{1,2,\dots,k\right\}\). Then
$$\text{lcm}\left(m,n\right)=p_1^{\gamma_1}\cdot p_2^{\gamma_2}\cdot\dots\cdot p_k^{\gamma_k}.$$
Let \(\alpha_i’\) and \(\beta_i’\) be such that \(\alpha_i+\alpha_i’=\gamma_i\) and \(\beta_i+\beta_i’=\gamma_i\). Notice that either \(\alpha_i’\) or \(\beta_i’\) could be zero if \(\alpha_i\) or \(\beta_i\) is already \(\gamma_i\). Moreover, let \(g,h\in G\) such that \(g^m=e\) and \(h^n=e\), and consider:
$$\left(gh\right)^{\text{lcm}\left(m,n\right)}=\left(gh\right)^{p_1^{\gamma_1}\cdot p_2^{\gamma_2}\cdot\dots\cdot p_k^{\gamma_k}}=g^{p_1^{\gamma_1}\cdot p_2^{\gamma_2}\cdot\dots\cdot p_k^{\gamma_k}}h^{p_1^{\gamma_1}\cdot p_2^{\gamma_2}\cdot\dots\cdot p_k^{\gamma_k}}.$$
This last equality follows from the fact that \(G\) is abelian. Carrying on:
$$\begin{align}g^{p_1^{\gamma_1}\cdot p_2^{\gamma_2}\cdot\dots\cdot p_k^{\gamma_k}}h^{p_1^{\gamma_1}\cdot p_2^{\gamma_2}\cdot\dots\cdot p_k^{\gamma_k}}&=g^{p_1^{\alpha_1+\alpha_1'}\cdot p_2^{\alpha_2+\alpha_2'}\cdot\dots\cdot p_k^{\alpha_k+\alpha_k'}}g^{p_1^{\beta_1+\beta_1'}\cdot p_2^{\beta_2+\beta_2'}\cdot\dots\cdot p_k^{\beta_k+\beta_k'}}\newline&=g^{p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdots\cdot p_k^{\alpha_k}\cdot p_1^{\alpha_1'}\cdot p_2^{\alpha_2'}\cdot\cdots\cdot p_k^{\alpha_k'}}h^{p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\cdots\cdot p_k^{\beta_k}\cdot p_1^{\beta_1'}\cdot p_2^{\beta_2'}\cdot\cdots\cdot p_k^{\beta_k'}}\newline&=g^{mp}h^{nq}=ee=e,\end{align}$$
$$p=p_1^{\alpha_1'}\cdot p_2^{\alpha_2'}\cdot\cdots\cdot p_k^{\alpha_k'}\qquad\text{and}\qquad q=p_1^{\beta_1'}\cdot p_2^{\beta_2'}\cdot\dots\cdot p_k^{\beta_k'}.$$
Hence, \(G\) has an element of order \(\text{lcm}\left(m,n\right)\). \(\blacksquare\)
The Third and Final Lemma
Unlike the first two lemmas, I will not prove this one... yet. This is because it is not yet clear to me how one would go about proving it. Nevertheless, I will use it in tandem with the second lemma to show that \(\mathbb Z_p^\times\), where \(p\) is prime, has a generator.
Lemma 3 (Without Proof). A polynomial in \(\mathbb Z_p\left[X\right]\) of degree \(n\), where \(p\) is prime, has at most \(n\) roots in \(\mathbb Z_p\).
Here we put an end to our big claim!
Theorem. \(\mathbb Z_p^\times\cong\mathbb Z_{p-1}\), where \(p\) is prime.
Proof. Let \(m\) be the least common multiple of the orders of the elements of \(\mathbb Z_p^\times\). By Lemma 2, \(\mathbb Z_p^\times\) has an element of order \(m\). By Lagrange’s theorem, \(m\) divides \(p-1\), which implies that \(m\leqslant p-1\). Moreover, the order of every element in \(\mathbb Z_p^\times\) divides \(m\), which implies that each one of them is a root of the polynomial \(X^m-1\) in \(\mathbb Z_p\left[X\right]\). By Lemma 3, this polynomial has at most \(m\) roots, which implies that \(p-1\leqslant m\). Therefore, \(p-1=m\), so \(\mathbb Z_p^\times\) is cyclic. Hence, by Lemma 1, \(\mathbb Z_p^\times\) is isomorphic to \(\mathbb Z_{p-1}\). \(\blacksquare\)
theartofmadeline
dededos
baratheonpilled
areudirty
titsay
romaincrisis
tangentwithtanner