Merge pull request #1167 from jxu/patch-13

jakobkogler · web-flow · commit c6b74b592d25 · 2023-10-16T21:09:46.000+02:00
Phi: add multiplicative group info
diff --git a/src/algebra/phi-function.md b/src/algebra/phi-function.md
@@ -143,6 +143,11 @@ $$a^n \equiv a^{n \bmod \phi(m)} \pmod m$$
 
 This allows computing $x^n \bmod m$ for very big $n$, especially if $n$ is the result of another computation, as it allows to compute $n$ under a modulo.
 
+### Group Theory
+$\phi(n)$ is the [order of the multiplicative group mod n](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) $(\mathbb Z / n\mathbb Z)^\times$, that is the group of units (elements with multiplicative inverses). The elements with multiplicative inverses are precisely those coprime to $n$.
+
+The [multiplicative order](https://en.wikipedia.org/wiki/Multiplicative_order) of an element $a$ mod $n$, denoted $\operatorname{ord}_n(a)$, is the smallest $k>0$ such that $a^k \equiv 1 \pmod m$. $\operatorname{ord}_n(a)$ is the size of the subgroup generated by $a$, so by Lagrange's Theorem, the multiplicative order of any $a$ must divide $\phi(n)$. If the multiplicative order of $a$ is $\phi(n)$, the largest possible, then $a$ is a [primitive root](primitive-root.md) and the group is cyclic by definition. 
+
 ## Generalization
 
 There is a less known version of the last equivalence, that allows computing $x^n \bmod m$ efficiently for not coprime $x$ and $m$.
