Zorn’s lemma: a nonempty partially ordered set in which every chain has an upper bound has a maximal element. It gives a maximal ideal containing any proper ideal of a ring with \(1\), an algebraic closure of every field, and a basis of every vector space. Euler’s totient \(\varphi(n)\) is the number of generators of a cyclic group of order \(n\) and the degree \([\QQ(\zeta_n):\QQ]\) of the \(n\)th cyclotomic field. The Chinese remainder theorem gives \(R/(I\cap J)\cong R/I\times R/J\) for comaximal ideals \(I,J\) of a commutative ring \(R\), in particular \(\ZZ/mn\ZZ\cong\ZZ/m\ZZ\times\ZZ/n\ZZ\) for coprime \(m,n\). Euler’s theorem \(a^{\varphi(n)}\equiv1\pmod{n}\) for \(\gcd(a,n)=1\) is Lagrange’s theorem in \((\ZZ/n\ZZ)^\times\), and Fermat’s little theorem is its case \(n=p\) prime.
Chain in a poset (Tag D-P6XOT)
Let \((X,\leq)\) be a partially ordered set. A chain in \(X\) is a subset \(C\subseteq X\) that is totally ordered by \(\leq\): for all \(c,c'\in C\), \(c\leq c'\) or \(c'\leq c\).
Let \((X,\leq)\) be a partially ordered set and \(S\subseteq X\). An upper bound of \(S\) is an element \(x\in X\) such that \(s\leq x\) for all \(s\in S\).
Zorn's lemma (Tag FT-PUVIQ)
Let \((P,\le)\) be a partially ordered set in which every chain has an upper bound in \(P\). Then \(P\) has a maximal element: an element \(m\in P\) such that \(m\le x\) with \(x\in P\) implies \(x=m\).
The empty chain is a chain, so the hypothesis forces \(P\) to be nonempty.
Zorn's lemma (Tag T-V7JRG)
If \(P\) is a poset in which every chain has an upper bound in \(P\), then \(P\) has a maximal element.
Krull's theorem on maximal ideals (Tag FF-QELG7)
Let \(R\) be a commutative ring. Every proper ideal \(I\subsetneq R\) is contained in a maximal ideal of \(R\). In particular, applying this to \(I=0\), every nonzero commutative ring has a maximal ideal.
Let \(P\) be the set of proper ideals of \(R\) containing \(I\), ordered by inclusion; it contains \(I\). The union of a nonempty chain in \(P\) is an ideal containing \(I\), and it is proper because it does not contain \(1\), so it is an upper bound in \(P\); the empty chain has the upper bound \(I\). By Zorn's lemma, \(P\) has a maximal element, which is a maximal ideal of \(R\) containing \(I\).
Krull's theorem on maximal ideals (Tag T-QSTRJ)
Let \(R\) be a nonzero ring. Then every proper ideal of \(R\) is contained in a proper maximal ideal; in particular, \(R\) has a proper maximal ideal.
Existence of maximal ideals (Tag PR-UTFSY)
Let \(R\) be a ring and \(I\subsetneq R\) a proper ideal. Then \(I\) is contained in a maximal ideal of \(R\).
Let \(\mathcal S\) be the set of proper ideals of \(R\) containing \(I\), ordered by inclusion; it is nonempty since \(I\in\mathcal S\). If \(\mathcal C\subseteq\mathcal S\) is a nonempty chain, then \(J\coloneqq\bigcup_{J'\in\mathcal C}J'\) is an ideal containing \(I\), and \(1\notin J\) because \(1\) lies in no proper ideal, so \(J\in\mathcal S\) is an upper bound for \(\mathcal C\). By Zorn’s lemma \(\mathcal S\) has a maximal element \(\mathfrak m\). Any ideal strictly containing \(\mathfrak m\) contains \(I\) and is not in \(\mathcal S\), so it equals \(R\); thus \(\mathfrak m\) is a maximal ideal.
Euler's totient function (Tag D-JX3YC)
Euler’s totient function \(\phi\colon\ZZ_{\geq 1}\to\ZZ_{\geq 1}\) is \[ \phi(n) \coloneqq \size \theset{ k\in\ZZ \st 1\leq k\leq n,\ \gcd(k ,n ) = 1}. \]
Euler's totient of a prime power (Tag FF-SOE5P)
For a prime \(p\) and an integer \(k\ge1\), the Euler totient of \(p^k\) is \[ \phi(p^k)=p^{k-1}(p-1)=p^k\qty{1-\frac1p}. \]
An integer \(m\) with \(1\le m\le p^k\) fails to be coprime to \(p^k\) exactly when \(p\divides m\), and there are \(p^{k-1}\) such multiples of \(p\). So \(\phi(p^k)=p^k-p^{k-1}\).
Fermat's little theorem (Tag FT-RVIGS)
Let \(p\) be a prime and let \(a\in\ZZ\). Then \[ a^p\equiv a\pmod p, \] and if \(p\nmid a\), then \(a^{p-1}\equiv1\pmod p\).
If \(p\nmid a\), the class of \(a\) lies in the group \(\FF_p^\times\) of order \(p-1\), so \(a^{p-1}\equiv1\pmod p\) by Lagrange’s theorem, and multiplying by \(a\) gives \(a^p\equiv a\pmod p\). If \(p\divides a\), both sides of \(a^p\equiv a\) are \(0\) modulo \(p\).
Euler's theorem (Tag FT-BAV4D)
Let \(n\ge1\) and let \(a\in\ZZ\) with \(\gcd(a,n)=1\). Then \[ a^{\phi(n)}\equiv1\pmod n, \] where \(\phi\) is the Euler totient function.
The class of \(a\) lies in the group \((\ZZ/n\ZZ)^\times\) of order \(\phi(n)\), so its order divides \(\phi(n)\) by Lagrange’s theorem.
If \(n>1\) and \(d=\gcd(a,n)>1\), then \(a^k\not\equiv1\pmod n\) for every \(k\ge1\), since \(d\) divides both \(a^k\) and \(n\) but not \(1\). For \(a=2\) and \(n=4\), \(2^{\phi(4)}=2^2=4\equiv0\pmod4\).
Chinese remainder theorem (Tag T-TTZ2Y)
Let \(p\) and \(q\) be positive integers with \(\gcd(p, q) = 1\). Then \[ \ZZ/pq\ZZ \cong \ZZ/p\ZZ \times \ZZ/q\ZZ. \]
Injective maps are the maps with a left inverse (Tag FD-JI2RH)
Let \(X\) be a nonempty set and \(f\colon X\to Y\) a map of sets. Then \(f\) is injective, that is, \(f(x) = f(x')\) implies \(x=x'\) for all \(x,x'\in X\), if and only if \(f\) has a left inverse: a map \(g\colon Y\to X\) with \(g(f(x))=x\) for every \(x\in X\).
If \(g\) is a left inverse and \(f(x)=f(x')\), then \(x=g(f(x))=g(f(x'))=x'\). Conversely, suppose \(f\) is injective and fix \(x_0\in X\). Define \(g(y)\) to be the unique \(x\in X\) with \(f(x)=y\) when \(y\in f(X)\), and \(g(y)\coloneqq x_0\) otherwise; then \(g(f(x))=x\) for every \(x\in X\).
The hypothesis \(X\neq\emptyset\) is needed: for a nonempty set \(Y\), the empty map \(\emptyset\to Y\) is injective but has no left inverse, since there is no map \(Y\to\emptyset\).
Surjective maps are the maps with a right inverse (Tag FD-BWVRA)
Let \(f\colon X\to Y\) be a map of sets. Then \(f\) is surjective, that is, for every \(y\in Y\) there exists \(x\in X\) with \(f(x)=y\), if and only if \(f\) has a right inverse: a map \(g\colon Y\to X\) with \(f(g(y))=y\) for every \(y\in Y\).
If \(g\) is a right inverse, then each \(y\in Y\) equals \(f(g(y))\), so \(f\) is surjective. Conversely, if \(f\) is surjective, then each fiber \(f^{-1}(y)\) is nonempty, and the axiom of choice gives a map \(g\colon Y\to X\) with \(g(y)\in f^{-1}(y)\) for every \(y\); then \(f(g(y))=y\).