# Cyclic Group Problem

1. Jun 22, 2005

### 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?

2. Jun 22, 2005

### 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.

3. Jun 22, 2005

### AKG

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).

4. Jun 22, 2005

### 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.

5. Jun 22, 2005

### AKG

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?
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.

6. Jun 23, 2005

### 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] 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}|$. 7. Jun 23, 2005 ### AKG 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})$$

8. Jun 23, 2005

### NateTG

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

9. Jun 24, 2005

### 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.

10. Jun 24, 2005

### 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?

11. Jun 24, 2005

### 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}

12. Jun 24, 2005

### NateTG

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

13. Jun 24, 2005

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