• Support PF! Buy your school textbooks, materials and every day products Here!

Cyclic Group Problem

  • Thread starter AKG
  • Start date
  • #1
AKG
Science Advisor
Homework Helper
2,565
4
Show that the set [itex]X = \{x : 0 < x < p^m, x \equiv 1 (\mathop{\rm mod}p)\}[/itex] where p is an odd prime, together with multiplication mod [itex]p^m[/itex] forms a cyclic group. It might help to write the x in X in the form:

[tex]x = 1 + a_1p^1 + \dots + a_{m-1}p^{m-1}[/tex]

for [itex](a_1,\, a_2,\, \dots ,\, a_{m-1}) \in (\mathbb{Z}_p)^{m-1}[/itex]. I haven't been able to get anywhere this problem. I've tried to see if [itex]1 + p + p^2 + /dots + p^{m-1}[/itex] 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?
 

Answers and Replies

  • #2
695
0
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
AKG
Science Advisor
Homework Helper
2,565
4
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.

[tex](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)[/tex]

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

Before I simplify this further, since the order of the group is [itex]p^{m-1}[/itex], then every element trivially satisfies [itex]x^{p^{m-1}} \equiv 1\, (\mathop{\rm mod} p^m)[/itex]. We want to show that this occurs only when the exponent is [itex]p^{m-1}[/itex] for some x, that is that for some x, [itex]x^{p^{m-2}} \not \equiv 1\, (\mathop{\rm mod} p^m)[/itex]. 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
NateTG
Science Advisor
Homework Helper
2,450
5
For [itex]m=2[/itex], the elements of the group are of the form:
[itex]1+pk[/itex] and the group is clearly equivalent to addition mod [itex]p[/itex] - so any non-trivial element is a generator.


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

Let's take a look at a subgroup generated by a generator for the [itex]p^{m-1}[/itex] group in the [itex]p^{m}[/itex] group.
The subgroup will either be of order [itex]p^{m-2}(p-1)[/itex] and thus generate the entire group, or it will be of order [itex]p^{m-3}(p-1)[/itex]. (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:
[tex]1+a_1p+a_2p^2...+k_{a_1,a_2,a_3,a_4,...}p^{m-1}[/tex]

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 [itex]k[/itex] then you're done.
 
  • #5
AKG
Science Advisor
Homework Helper
2,565
4
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 [itex]\{0,\, 1,\, 2,\, \dots ,\, p-1\}[/itex]"; is that right?
if you can show that some set of leading terms must have multiple [itex]k[/itex] 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 [itex]p^{m-1}[/itex] term, but the subgroup will contain at least [itex]p^{m-3}(p-1)[/itex] elements.
 
  • #6
NateTG
Science Advisor
Homework Helper
2,450
5
Um, I think I had the order of the group wrong. It should be [itex]p^{m-1}[/itex] e.g.:
The [itex]3^3[/itex] 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 [itex]G_{m} \rightarrow G_{m-1}[/itex].

Now, let's say that [itex]g[/itex] is a generator of [itex]G_{m-1}[/itex]. It's pretty easy to see that [itex]|g|=|G_{m}|[/itex] or [itex]|g|=|G_{m-1}|[/itex], and that the same 'chop off the last term' function is an onto homomorphism [itex]<g> \rightarrow G_{m-1}[/itex], so if it's possible to show that the kernel of this homomorphism is non-trivial, then [itex]|g| \neq |G_{m-1}| \Rightarrow |g| =|G_{m}|[/itex].
 
  • #7
AKG
Science Advisor
Homework Helper
2,565
4
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})[/tex]

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

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

[tex](p+1)^{p^{m-2}+1} = \sum _{k=0} ^{p^{m-2}+1}{{p^{m-2}+1}\choose k}p^k[/tex]

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

We want

[tex]\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})[/tex]

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 [itex]p^{m-1}[/itex] thus will disappear. For k=1, we get:

[tex](p^{m-2}+1)p = p^{m-1} + p \equiv p (\mathop{\rm mod} p^{m-1})[/tex]
 
  • #8
NateTG
Science Advisor
Homework Helper
2,450
5
AKG said:
Trying Muzza's suggestion of p+1 for the groups with multiplication mod 27, 81, and 125, it seems to me that [itex](p+1)^{p^{m-2}+1} \equiv p+1 (\mathop{\rm mod} p^{m-1})[/itex], so I'd like to prove it.
That follows from the order of the group [itex]p^{m-1}[/itex].
The problem is showing that they are not equal [itex]\mathop{\rm mod} p^m[/itex].
 
  • #9
matt grime
Science Advisor
Homework Helper
9,395
3
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
AKG
Science Advisor
Homework Helper
2,565
4
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 [itex]p^m[/itex], then it's order divides [itex]p^{m-2}[/itex], so [itex](p+1)^{p^{m-2}} \equiv 1 (\mathop{\rm mod} p^m)[/itex]. But:

[tex](p+1)^{p^{m-2}} = \sum _{k=0} ^{p^{m-2}}{{p^{m-2}}\choose k}p^k[/tex]

[tex] = 1 + p^{m-1} + \sum _{k=2} ^{p^{m-2}}{{p^{m-2}}\choose k}p^k[/tex]

Now the term for k=2 divides [itex]p^m[/itex], 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:

[tex](p+1)^{p^{m-2}} \equiv 1 + p^{m-1} (\mathop{\rm mod} p^m)[/tex]

so (p+1) is a generator. I did this in a rush again, did I overlook something?
 
  • #11
matt grime
Science Advisor
Homework Helper
9,395
3
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

[tex] (1+p)^{p^{k-1}}= 1+ u_kp^k[/tex]

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
NateTG
Science Advisor
Homework Helper
2,450
5
It's certainly all there. Just a matter of putting it together, dotting i's and crossing t's at this point.
 
  • #13
AKG
Science Advisor
Homework Helper
2,565
4
Thanks guys. It seems to me that the advantage of the inductive approach is that some work may be involved in showing that [itex]p^m[/itex] divides the sum:

[tex]\sum _{k=2} ^{p^{m-2}}{{p^{m-2}}\choose k}p^k[/tex]

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:

[tex](p + 1)^{p^k} = \left ((p+1)^{p^{k-1}}\right )^p[/tex]
 

Related Threads on Cyclic Group Problem

  • Last Post
Replies
2
Views
4K
  • Last Post
2
Replies
37
Views
7K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
14
Views
18K
  • Last Post
Replies
6
Views
7K
  • Last Post
Replies
18
Views
2K
  • Last Post
Replies
2
Views
2K
Top