2
$\begingroup$

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$

I have two questions about this:

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 8 at 21:00
  • 1
    $\begingroup$ @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. $\endgroup$
    – poncho
    Jan 8 at 22:52
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Jan 8 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.