10.5 Applications to number theory

We now use some of the tools from group theory to look back at questions linked to modular arithmetic.

History:

It is worth noting that much of the following theory predates and motivated the development of abstract group theory, in particular the study of Abelian groups (from 1800). Alongside Symmetry groups and Transformation groups (which we did not explore), Abelian groups were concrete examples of groups that drove this development.

First, recall that \((\mathbb{Z}/n\mathbb{Z},\cdot)\) is not a group as some elements (such as \([0]\)) do not have a multiplicative inverse (recall Proposition 10.13). Let us define the following group.

Definition 10.28:

\(U_n\) is the subset \(\{[a]:a\in\mathbb{Z}\mbox{ and }\gcd(a,n)=1\}\) of \(\mathbb{Z}/n\mathbb{Z}\).

Remark:

If \(\gcd(a,n)=1\) then \(\gcd(a+nt,n)=1\) for any \(t\in\mathbb{Z}\) and so it makes no difference which element of \([a]\) we use to check the condition for \([a]\in U_n\). Since every congruence class \([a]\) contains an element \(a\) with \(0\leq a<n\), we’ll usually use these elements.

Theorem 10.29:

\((U_n,\cdot)\) is an abelian group.

Proof.

Suppose \([a],[b]\in U_n\), so \(\gcd(a,n)=1=\gcd(b,n)\). Then \(\gcd(ab,n)=1\) and so \([ab]\in U_n\) and \(U_n\) is closed under multiplication.

Since \[([a][b])[c]=[abc]=[a]([b][c])\] multiplication on \(U_n\) is associative.

\([1]\) is an identity element, since \([1][a]=[a]=[a][1]\) for any \(a\).

If \([a]\in U_n\), so \(\gcd(a,n)=1\), then \(as+nt=1\) for integers \(s,t\), and \(\gcd(s,n)=1\). So \([s]\in U_n\) is an inverse of \([a]\).

So \(U_n\) is a group under multiplication. It is abelian since \([a][b]=[ab]=[b][a]\) for all \(a,b\in\mathbb{Z}\).

□

Interest:

The notation \(U\) stands for “units”. In Algebra 2, you’ll see that a unit is an element which has a multiplicative inverse, so \(U_n\) is the group of units of \(\mathbb{Z}/n\mathbb{Z}\).

Similar links can be made with \((\mathbb{R},+)\) and \((\mathbb{R}\setminus\{0\},\cdot)\) or with \((\mathbb{Z},+)\) and \((\{-1,1\},\cdot)\).

Example:

If \(p\) is a prime, then \(U_p=\{[1],[2],\dots,[p-1]\}\) has order \(p-1\).

Example:

\(U_4=\{[1],[3]\}\), \(U_6=\{[1],[5]\}\) both have order \(2\). \(U_8=\{[1],[3],[5],[7]\}\) and \(U_{10}=\{[1],[3],[7],[9]\}\) have order \(4\).

Unlike \((\mathbb{Z}/n\mathbb{Z},+)\), \((U_n,\times)\) is not always cyclic (although it sometimes is).

Example:

\(U_{10}\) is cyclic, with generator \([7]\): \([7]^0=[1]\), \([7]^1=[7]\), \([7]^2=[49]=[9]\), \([7]^3=[7][9]=[63]=[3]\), so \[\langle [7]\rangle =\{[1],[3],[7],[9]\rangle=U_{10}.\]

Example:

\(U_8\) is not cyclic. \([3]^2=[9]=[1]\), \([5]^2=[25]=[1]\) and \([7]^2=[49]=[1]\), so every element has order \(2\) apart from \([1]\), which has order \(1\). In particular there are no elements of order \(|U_8|=4\), so the group is not cyclic, and is a Klein 4-group.

Remark:

In fact, \(U_n\) is cyclic if and only if \(n=2\), \(n=4\) or \(n=p^r\) or \(n=2p^r\) for \(p\) an odd prime and \(r\geq1\), but this is beyond the scope of this unit.

We can now apply Lagrange’s theorem to \(U_n\) to get an important number theory result.

Theorem 10.30: (Fermat’s Little Theorem)

Let \(p\) be a prime and \(a\) an integer not divisible by \(p\). Then \[a^{p-1}\equiv 1\pmod{p}.\]

Proof.

We’ll apply Corollary 10.20 to the group \(G=U_p\). Since \(p\) is prime, \(U_p=\{[1],[2],\dots,[p-1]\}\) has order \(p-1\), and if \(a\) is not divisible by \(p\) then \([a]\in U_p\). So by Corollary 10.20, \[[a]^{p-1}=[1]\] in \(U_p\), or in other words \[a^{p-1}\equiv 1\pmod{p}.\]

□

This simplifies calculating powers of integers modulo a prime:

Example:

Suppose we want to calculate \(7^{100}\pmod{31}\). The straightforward way to do this would involve multiplying by seven \(99\) times (although even without Fermat’s Little Theorem a more intelligent approach would use many fewer multiplications). But by Fermat’s Little Theorem with \(p=31\), \[7^{30}\equiv1\pmod{31},\] and so \[7^{100}=(7^{30})^3\times 7^{10}\equiv 1^3\times 7^{10}\pmod{31}.\] So without much calculation at all we reduce the problem to calculating a tenth power instead of a hundredth power. And then, to finish, \(7^2=49\equiv 18\pmod{31}\), so \(7^3\equiv7\times 18=126\equiv2\pmod{31}\) and \[7^{10}=(7^3)^3\times 7\equiv 2^3\times 7=56\equiv25\pmod{31}.\]

History:

Pierre de Fermat, French lawyer and government official (1601 - 1665) worked on several number theory problems alongside his job. He wrote the above theorem however he did not write down a proof for fear it would be too long - he certainly was not aware of group theory tools that would have provided a short proof.

There is a generalization to powers modulo \(m\) where \(m\) is not prime, but the statement is a bit more complicated, since \(U_m\) is not just \(\{[1],[2],\dots,[m-1]\}\). So first, let’s introduce some standard notation for the order of this group.

Definition 10.31:

Euler’s phi function is the function \(\varphi\) from positive integers to positive integers with \(\varphi(m)\) equal to the number of integers \(a\) such that \(0<a\leq m\) and \(\gcd(a,m)=1\).

Remark:

This is precisely the order of \(U_m\), since \(U_m=\{[a]:\gcd(a,m)=1\}\).

Example:

If \(p\) is prime, then \(\varphi(p)=p-1\).

Theorem 10.32: (Fermat-Euler Theorem)

Let \(m>0\) and \(a\) be integers with \(\gcd(a,m)=1\). Then \[a^{\varphi(m)}\equiv1\pmod{m}.\]

Proof.

Apply Corollary 10.20 to the group \(G=U_m\). The condition \(\gcd(a,m)=1\) means that \([a]\in U_m\), and \(|U_m|=\varphi(m)\), so the corollary gives \[[a]^{\varphi(m)}=[1]\] in \(U_m\), or in other words \[a^{\varphi(m)}\equiv1\pmod{m}.\]

□

History:

Leonhard Euler, Swiss mathematician (1707 - 1783), wrote down a proof of Fermat’s Little Theorem in 1736 (nearly a 100 year after Fermat wrote down the statement). He then extended Fermat’s theorem to all cases. While he used modular arithmetic notation as we do today, it wasn’t until 1801 that Gauss revisited the proof and gave a shorter and simpler version using group theory ideas.

Many of the groups \(U_n\) are direct products in disguise.

Proposition 10.33:

Let \(m,n\) be positive integers with \(\gcd(m,n)=1\). Then \[U_{mn}\cong U_m\times U_n.\]

Proof.

Define a map \[\varphi:U_{mn}\to U_m\times U_n\] by \(\varphi([a]_{mn})=([a]_m,[a]_n)\) (where we use subscripts such as \([a]_m\) to indicate a congruence class\(\pmod{n}\)). This makes sense, since if \(\gcd(a,mn)=1\), then \(\gcd(a,m)=1\) and \(\gcd(a,n)=1\).

By Theorem 10.14, we know given \(a \in \mathbb{Z}/m\mathbb{Z}\) and \(b \in \mathbb{Z}/n\mathbb{Z}\) there exists \(x\in \mathbb{Z}/mn\mathbb{Z}\) such that \(\varphi(x)=(a,b)\). Furthermore, \(x\) is unique in \(\mathbb{Z}/mn\mathbb{Z}\). Hence \(\varphi\) is bijective [for all \(([a]_m,[b]_n)\in U_m\times U_n\), there exists a unique \([x]\in U_{mn}\) such that \(\varphi([x]_{mn})=([a]_m,[b]_n)\) ]

Since \(\varphi\) is bijective, and \[\varphi([a]_{mn}[a']_{mn})=([aa']_m,[aa']_n) =([a]_m,[a]_n)([a']_m,[a']_n)=\varphi([a]_{mn})\varphi([a']_{mn}),\] \(\varphi\) is an isomorphism.

□

Remark:

The conclusion of the above is not true if \(\gcd(m,n)\neq1\). For example, \(|U_4|=2\), but \(|U_{16}|=8\), so \(U_{16}\) can’t be isomorphic to \(U_4\times U_4\).

We have an immediate corollary

Corollary 10.34:

If \(\gcd(m,n)=1\) then \(\varphi(mn)=\varphi(m)\varphi(n)\).

Example:

We calculate \(7^{100} \pmod{30}\). Since \(30=2\cdot3\cdot5\) and \(\gcd(2,3)=1\), \(\gcd(6,5)=1\) we have \(\varphi(30)=\varphi(2)\varphi(3)\varphi(5)=1\cdot2\cdot4=8\). So as \(\gcd(7,30)=1\) by Fermat-Euler we have \(7^8\equiv 1\pmod{30}\). Hence \(7^{100}\equiv7^{96}\cdot7^4\equiv(7^8)^{12}\cdot(7^2)^2\equiv 1\cdot19^2\equiv(-11)^2\equiv121\equiv1\pmod{30}\).