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:
1,4,7,10,13,16,19,22,25[/itex]<br /> But that&#039;s not so important.<br /> <br /> Chopping off the last term in the polynomial expression for a group element is a homomorphism G_{m} \rightarrow G_{m-1}.<br /> <br /> Now, let&#039;s say that g is a generator of G_{m-1}. It&#039;s pretty easy to see that |g|=|G_{m}| or |g|=|G_{m-1}|, and that the same &#039;chop off the last term&#039; function is an onto homomorphism &amp;lt;g&amp;gt; \rightarrow G_{m-1}, so if it&#039;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