# Proof of Lagrange's Theorem?

In the book Cryptography Engineering, Design Principles and Practical Applications, by Niels Ferguson, Bruce Schneier and Tadayoshi Kohno, in a section discussing multiplicative groups, the authors assert, “For any element $$g$$ [of a multiplicative group $$G$$ modulo $$p$$], the order of $$g$$ is a divisor of $$p-1$$. This isn’t too hard to see.” (Emphasis mine.)

The authors continue with a paragraph or two explaining this property, which I understand to be Lagrange’s Theorem (or at least a consequence of it), and which I paraphrase here:

• Consider a group $$G$$ modulo a prime $$p$$
• Let $$g$$ be a primitive element of $$G$$; that is, $$g$$ generates every element in $$G$$
• Let $$h$$ be any other element in $$G$$ (one that generates a proper subgroup of $$G$$)
• Then $$g^x = h \pmod{p}$$ for some integer $$x$$, which must be true because $$g$$ generates the whole group
• Consider the elements generated by $$h$$; these are $$1, h, h^{2}, h^{3}, ...$$, which are equal to $$1, g^{x}, g^{x2}, g^{x3}, ...$$
• The order of $$h$$ is the smallest $$q$$ at which $$h^q = 1 \pmod{p}$$, which is the same as saying it is the smallest $$q$$ such that $$g^{xq} = 1 \pmod{p}$$
• For any $$t$$, $$g^t = 1 \pmod{p}$$ is the same as saying $$t = 0 \pmod{p-1}$$, so $$q$$ is the smallest $$q$$ such that $$xq = 0 \pmod{p-1}$$; this happens when $$q = (p-1) / gcd(x, p-1)$$
• Therefore, $$q$$ must be a factor of $$p-1$$

First, is the foregoing bullet list sufficiently rigorous to qualify as a proof of Lagrange’s Theorem?

Second, in the second to last bullet, in which it is asserted, "...this happens when $$q = (p-1) / gcd(x,p-1)$$, this seems to me a leap of faith (or, more likely, a misunderstanding on my part of how to get from $$xq = 0 \pmod{p-1}$$ to $$q = (p-1) / gcd(x,p-1)$$). Can someone please explain?

First, is the foregoing bullet list sufficiently rigorous to qualify as a proof of Lagrange’s Theorem?

Well, no, Lagrange's Theorem is considerably broader than what you stated. It applies to all finite groups (even ones which don't have a generator, or for that matter, are not Abelian). At best, that (tries to) show one of the consequences of Lagrange's Theorem.

Lagrange's Theorem is: for any finite group $$S$$ and a subgroup $$T$$ of $$S$$, the size (number of elements) of $$S$$ is always divisible by the size of $$T$$.

Second, in the second to last bullet, in which it is asserted, "...this happens when $$q = (p-1) / gcd(x,p-1)$$, this seems to me a leap of faith (or, more likely, a misunderstanding on my part of how to get from $$xq = 0 \pmod{p-1}$$ to $$q = (p-1) / gcd(x,p-1)$$). Can someone please explain?

Well, here is the approach I would take; in general $$ab = 0 \pmod{c}$$ iff all the prime factors of $$c$$ (counting multiplicity) appear somewhere in either $$a$$ or $$b$$. Now, if the $$b$$ as a prime factor $$d$$ that does not appear in $$c$$ (or occurs more times in $$b$$ than it does in $$c$$), then there is a smaler $$b' = b/d$$ that also satisfies $$ab' = 0 \bmod{c}$$.

Hence, if $$q$$ is the smallest solution (greater than 0) of $$xq = 0 \pmod{p-1}$$, then $$q$$ must be a product only of prime factors of $$p-1$$ (and those prime factors occur no more times than they occur in $$p-1$$), that is, $$q$$ itself is a factor of $$p-1$$.

Still, I think relying on the more general Lagrange's theorem (of which this is a simple consequence) is a bit cleaner - IMHO, the theorem that $$\mathbb{Z}_p^*$$ (for prime $$p$$) always has a generator is rather deeper than Lagrange's theorem. I know a relatively simple proof of Lagrange's theorem; I don't know of a correspondingly simple from that $$\mathbb{Z}_p^*$$ has a generator, especially since $$\mathbb{Z}_n^*$$ does not if $$n$$ has two distinct odd prime factors.

• Thanks, as always, for the thorough explanation, @poncho. You write, "I know a relatively simple proof of Lagrange's Theorem;" Would love to see that, as I have only seen relatively non-simple ones. Jan 8 at 21:00
• @divaconhamdip: well, if $G$ is the full group (of size $g$), and $H$ is the subgroup (of size $h$), then you can divide the elements of $G$ into a number of sets, each of size $h$. If there are $k$ sets, then (as all the elements of $G$ appear in exactly one of the sets), we have $g = kh$, that is, $h$ is a factor of $g$. The only thing left is forming the sets: take the first set as the elements $H = \{ a_0=I, a_1, ..., a_{h-1}\}$. Then, repeatedly: select an element $b$ that is not in any of the sets, form the set $\{ba_0, ba_1, ..., ba_{h-1}\}$. Repeat until all elements are accounted. Jan 8 at 22:52
• @divaconhamdip: you need to show that every element is within a set, that all the elements of any set is unique (that is, no set contains a duplicate), and that there are no duplicate elements between the sets; those are straight-forward. Jan 8 at 22:53