2
$\begingroup$

Problem statement:

Let $p_1$ and $p_2$ be two distinct prime numbers where $p_2 < p_1$. I want to prove that if $g \in \mathbb{Z}_{p_1}^{*}$ has the property that $g^{p_2} \equiv 1 \mod p_1$, then the set $S = \{g^{i} \bmod p_1 \mid 0 \leq i < p_2\}$ is closed under multiplication (i.e., $S$ is a subgroup of $\mathbb{Z}_{p_1}^{*}$).

Solution attempt:

By Lagrange's theorem we know that the order of any proper subgroup $H$ must divide the order of the finite group $G$. We also know that the order of $g$ is defined as the smallest positive integer $d$ such that $$ g^d \equiv 1 \mod p. $$ So, my idea is that we need to show that the order of $S$ divides the order of $\mathbb{Z}_{p_1}^* = \phi(p_1) = p_1 - 1$.

For the elements $g \in \mathbb{Z}_{p_1}^*$ that have the property that $g^{p_2} \equiv 1 \mod p_1$ we know by the definition of the order of $g$ that the order for the cyclic subgroup $S$ generated by $g$ must be $p_2$.

Here is where I get confused...

Question(s):

  1. We know that $|S| = p_2$. For $S$ to be a proper subgroup of $\mathbb{Z}_{p_1}^*$, $p_2$ must divide the order of the group which is $p_1 - 1$. It is clear that this is not always the case. I've gone wrong and I don't know how to proceed.
$\endgroup$
3
  • $\begingroup$ You are going down the wrong path. $p_1$ plays no role here (other than the fact that $\Bbb Z_{p_1}^*$ is a monoid, i.e. closed under multiplication). Similarly primality is not relevant. For $\,g\,$ in any monoid, if $\,g^k = 1\,$ for $\,k\ge 1\,$ then $\,S = \{1,g,g^2,\ldots,g^{k-1}\}\,$ is closed under multiplication simply because a product has form $\,g^n,\,$ and $\,\color{#c00}{g^k=1}\Rightarrow g^n = g^{n\bmod k},\,$ since by division $\,n = kq+r,\ 0\le r\le k-1,\,$ so $\, g^n = (\color{#c00}{g^k})^q g^r = \color{#c00}{1}^kg^r = g^r.\ \ $ $\endgroup$ Commented Nov 28, 2024 at 19:40
  • $\begingroup$ Above is a simply a special case of ubiquitous mod order reduction. Note also $\,(g^i)^{-1} = g^{k-i}\,$ by $\,g^{k-i}g^i = g^k = 1.\ \ $ $\endgroup$ Commented Nov 28, 2024 at 19:41
  • $\begingroup$ Re: your wrong path: generally in any group of order $\,n,\,$ if $\,g^k = 1\,$ and $\,k\,$ is coprime to $\,n\,$ then $\,g = 1,\,$ since - by Lagrange - the order of $\,g\,$ divides the coprimes $\,k,n\,$ so it must be $1$, hence $\,S = \langle g\rangle = \{1\}\,$ (which is trivially closed under multiplication). This is what happens in your case when the prime $\,p_2\nmid p_1-1.\,$ So nothing is "wrong" in this case. But none of this is relevant to your original problem. $\endgroup$ Commented Nov 28, 2024 at 19:56

1 Answer 1

Reset to default
2
$\begingroup$

You can get it simpler.

Since $p_2<p_1$ :

You get with any $(i,j) \in [|0,p_2|[$ :

$$ g^{i+j} \mod p_1 $$

Two cases :

  • $i+j\geq p_2$, you know $g^{p_2}=1 \mod p_1$, so you get $g^{i+j}=g^{i+j \mod p_2} \mod p_1 $ and so you get back in $S$.
  • $i+j<p_2$ , so you're in $S$.

In order to be a subgroup, you have to proove that :

$$ (a,b) \in S \implies a \times b^{-1}\in S $$

In other words, taken $(i,j)$ above gives :

$$ g^{i}g^{-j} \mod p_1 $$

So that we want $(i-j \mod p_2) \in [|0,p_2|[ $, which is the case always.

So the group $S$ is a subgroup relatively to $Z_{p_1}^*$.

But $|S|\neq p_2$ in general. Because $p_2$ may not be the minimal order of the element $g$.

$\endgroup$
3
  • $\begingroup$ More clearly viewed as a special case of mod order reduction - see my comments on the question. $\endgroup$ Commented Nov 28, 2024 at 20:01
  • $\begingroup$ In the first part you prove the property that is "Closure". In the second part you seem to be doing something with an inverse, but I don't exactly understand why? Are you trying to prove the existence of an inverse element and that multiplying by that yields the identity element $e=1$ in this case? Associativity holds as the group operation is multiplication, identity element exists as per definition of $S$, closure you have proven, so what is left to prove is the existence of an inverse element for all $g \in \mathbb{Z}_{p_1}^*$, right? $\endgroup$ Commented Dec 7, 2024 at 18:32
  • $\begingroup$ I prove first closure, as you want to do in your OP. Then I precise that in order to prove that a group is a subgroup you just have to prove it contains neutral, isn't empty so, and $a.b^{-1} \in S$ when $(a,b) \in S^2$. So I prove this is closed under multiplication, is indeed a subgroup and then because Lagrange theorem hold, it proves that the minimal order of $g$ is less than $p_2$. Hope this clarify. $\endgroup$ Commented Dec 8, 2024 at 13:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.