# Cyclic Group Problem

Homework Helper
Show that the set $X = \{x : 0 < x < p^m, x \equiv 1 (\mathop{\rm mod}p)\}$ where p is an odd prime, together with multiplication mod $p^m$ forms a cyclic group. It might help to write the x in X in the form:

$$x = 1 + a_1p^1 + \dots + a_{m-1}p^{m-1}$$

for $(a_1,\, a_2,\, \dots ,\, a_{m-1}) \in (\mathbb{Z}_p)^{m-1}$. I haven't been able to get anywhere this problem. I've tried to see if $1 + p + p^2 + /dots + p^{m-1}$ generates the group, but haven't had any success in doing so, and I'm not even sure that it does. I've also considered inductive proofs without success. Any hints?

Related Introductory Physics Homework Help News on Phys.org
Some of my calculations (tried it for p^m = 5^2, 3^3, 7^4 and 13^4) suggest that p + 1 will always be a generator. I don't know how to prove this though. The order of X is surely p^(m - 1), and using the binomial theorem, you can write (p + 1)^(p^(m - 1)) as a sum where every term except the first one (which happens to be 1) seems to contain "a lot" of factors of p, so it wouldn't surprise me if (p + 1)^(p^(m - 1)) is 1 modulo p^m. Of course, even more is needed to conclude that p + 1 is a generator.

Homework Helper
Muzza said:
Some of my calculations (tried it for p^m = 5^2, 3^3, 7^4 and 13^4) suggest that p + 1 will always be a generator. I don't know how to prove this though. The order of X is surely p^(m - 1), and using the binomial theorem, you can write (p + 1)^(p^(m - 1)) as a sum where every term except the first one (which happens to be 1) seems to contain "a lot" of factors of p, so it wouldn't surprise me if (p + 1)^(p^(m - 1)) is 1 modulo p^m. Of course, even more is needed to conclude that p + 1 is a generator.
Yeah, that's the approach I took more or less (using binomial theorem) but it didn't get me too far.

$$(p + 1)^{p^{m-1}} \equiv \left (\sum _{i=0} ^{p^{m-1}} {{p^{m-1}}\choose i}p^i \right )\, (\mathop{\rm mod} p^m)$$

$$\equiv \left ( \sum _{i=0} ^{m-1} {{p^{m-1}}\choose i}p^i \right )\, (\mathop{\rm mod} p^m)$$

Before I simplify this further, since the order of the group is $p^{m-1}$, then every element trivially satisfies $x^{p^{m-1}} \equiv 1\, (\mathop{\rm mod} p^m)$. We want to show that this occurs only when the exponent is $p^{m-1}$ for some x, that is that for some x, $x^{p^{m-2}} \not \equiv 1\, (\mathop{\rm mod} p^m)$. My two failed approaches have been:

a) to try to show directly that this is true for some x, and
b) to try to show that if x of a certain form has this property for m = n, then we can find an x with a similar form that has that property for m = n + 1 (an inductive proof).

NateTG
Homework Helper
For $m=2$, the elements of the group are of the form:
$1+pk$ and the group is clearly equivalent to addition mod $p$ - so any non-trivial element is a generator.

Now, let's take a look at $m>2$. By induction we can assume that the group for $p^k$ is cyclic for any $k<m$.

Let's take a look at a subgroup generated by a generator for the $p^{m-1}$ group in the $p^{m}$ group.
The subgroup will either be of order $p^{m-2}(p-1)$ and thus generate the entire group, or it will be of order $p^{m-3}(p-1)$. (It must be at least that size, and it must divide the order of the supergroup.)

In the latter case, we have elements of the subgroup in the form:
$$1+a_1p+a_2p^2...+k_{a_1,a_2,a_3,a_4,...}p^{m-1}$$

Since each possible set of leading terms must be represented, and can only be represented once, if you can show that some set of leading terms must have multiple $k$ then you're done.

Homework Helper
NateTG said:
Since each possible set of leading terms must be represented, and can only be represented once
How do you know this? Also, by "each possible set" I assume you mean "every subset of $\{0,\, 1,\, 2,\, \dots ,\, p-1\}$"; is that right?
if you can show that some set of leading terms must have multiple $k$ then you're done.
I don't follow. No set has multiple elements, perhaps you meant something like "every possible sequence..." but in that case, every sequence will contain multiple k. There are only p possible coefficients for the $p^{m-1}$ term, but the subgroup will contain at least $p^{m-3}(p-1)$ elements.

NateTG
Homework Helper
Um, I think I had the order of the group wrong. It should be $p^{m-1}$ e.g.:
The $3^3$ group contains the elements:
$$1,4,7,10,13,16,19,22,25[/itex] But that's not so important. Chopping off the last term in the polynomial expression for a group element is a homomorphism $G_{m} \rightarrow G_{m-1}$. Now, let's say that $g$ is a generator of $G_{m-1}$. It's pretty easy to see that $|g|=|G_{m}|$ or $|g|=|G_{m-1}|$, and that the same 'chop off the last term' function is an onto homomorphism $<g> \rightarrow G_{m-1}$, so if it's possible to show that the kernel of this homomorphism is non-trivial, then $|g| \neq |G_{m-1}| \Rightarrow |g| =|G_{m}|$. Science Advisor Homework Helper So we want to find a g such that there are integers k, l such that: [tex]g^k \equiv g^l (\mathop{\rm mod} p^{m-1})$$

That is, some g generates two distinct elements which are the same except for the $p^{m-1}$ term.

Trying Muzza's suggestion of p+1 for the groups with multiplication mod 27, 81, and 125, it seems to me that $(p+1)^{p^{m-2}+1} \equiv p+1 (\mathop{\rm mod} p^{m-1})$, so I'd like to prove it.

$$(p+1)^{p^{m-2}+1} = \sum _{k=0} ^{p^{m-2}+1}{{p^{m-2}+1}\choose k}p^k$$

$$\equiv \sum _{k=0} ^{p^{m-1}-1}{{p^{m-2}+1}\choose k}p^k (\mathop{\rm mod} p^{m-1})$$

We want

$$\sum _{k=1} ^{p^{m-1}-1}{{p^{m-2}+1}\choose k}p^k (\mathop{\rm mod} p^{m-1}) \equiv p (\mathop{\rm mod} p^{m-1})$$

I don't think it would be too hard to prove (I'm at work so I haven't even tried) that for k>1, the terms will be multiples of $p^{m-1}$ thus will disappear. For k=1, we get:

$$(p^{m-2}+1)p = p^{m-1} + p \equiv p (\mathop{\rm mod} p^{m-1})$$

NateTG
Homework Helper
AKG said:
Trying Muzza's suggestion of p+1 for the groups with multiplication mod 27, 81, and 125, it seems to me that $(p+1)^{p^{m-2}+1} \equiv p+1 (\mathop{\rm mod} p^{m-1})$, so I'd like to prove it.
That follows from the order of the group $p^{m-1}$.
The problem is showing that they are not equal $\mathop{\rm mod} p^m$.

matt grime
Homework Helper
result in units mod prime powers from leveque fundamentals of number theory thm 4.4

let p be a prime and suppose p does noy divide a. furthe let t be the order of a mod p and let p^z be the largets power of p dividing a^t-1

if p>2 or z>1 then the order of a mod p^n is

t if n <=z

tp^{n-z} for n>z

a suitable choice of a would appear to do the trick here.

Homework Helper
NateTG, yes, I wrote that stuff in a rush. Have we overlooked something very simple?

If p+1 is a not a generator of the group whose multiplication is mod $p^m$, then it's order divides $p^{m-2}$, so $(p+1)^{p^{m-2}} \equiv 1 (\mathop{\rm mod} p^m)$. But:

$$(p+1)^{p^{m-2}} = \sum _{k=0} ^{p^{m-2}}{{p^{m-2}}\choose k}p^k$$

$$= 1 + p^{m-1} + \sum _{k=2} ^{p^{m-2}}{{p^{m-2}}\choose k}p^k$$

Now the term for k=2 divides $p^m$, and with a little work, I hope that I can show that this is the case for k > 2 as well. This leaves us with:

$$(p+1)^{p^{m-2}} \equiv 1 + p^{m-1} (\mathop{\rm mod} p^m)$$

so (p+1) is a generator. I did this in a rush again, did I overlook something?

matt grime
Homework Helper
you're getting there though.

you can prove this by induction.

don't leap straight in and do it for p^{m-2}

instead consider (1+p)^1, then to the power 2 and so on.

you;ll fidn yuo can prove that

$$(1+p)^{p^{k-1}}= 1+ u_kp^k$$

where u_k is coprime to p (i think it must be u_k=1 always as well, but that's a hunch).

and in particluar that none of the powers is 1 mod p^m except the power p^{m-1}

NateTG
Homework Helper
It's certainly all there. Just a matter of putting it together, dotting i's and crossing t's at this point.

Thanks guys. It seems to me that the advantage of the inductive approach is that some work may be involved in showing that $p^m$ divides the sum:
$$\sum _{k=2} ^{p^{m-2}}{{p^{m-2}}\choose k}p^k$$
$$(p + 1)^{p^k} = \left ((p+1)^{p^{k-1}}\right )^p$$