Cyclic Group Problem: Showing X Forms a Group

[AKG]

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?

 

[Muzza]

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.

 

[AKG]

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]

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.

 

[AKG]

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]

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:
[tex]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}|$.

 

[AKG]

So we want to find a g such that there are integers k, l such that:

$$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]

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]

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.

 

[AKG]

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]

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]

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

 

[AKG]

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$$

but with the inductive approach the analogous thing to be proved only requires that we know that gcd(p,a) = 1 for all natural a less than p, since:

$$(p + 1)^{p^k} = \left ((p+1)^{p^{k-1}}\right )^p$$