order of an element in mulitpicative group

**TheEmptySet** · January 20th 2009, 02:38 PM

This problem is from Abstract Algebra 3rd edition Dummit and Foote.

Let p be an odd prime and n a positive integer. Use the Binomial Theorem to show that:

$(1+p)^{p^{n-1}} = 1 (\mbox{mod } p^n)$

but

$(1+p)^{p^{n-2}} \ne 1 (\mbox{mod } p^n)$

Deduce that that $1+p$ is an element of order $p^{n-1}$ in the multiplicative group $(\mathbb{Z}/p^n\mathbb{Z} \mbox{ }\cdot)$

Thanks

As hint goes by the binomail theorem I get

$(1+p)^{p^{n-1}}=1+\sum_{i=1}^{p^{n-1}}\binom{p^{n-1}}{i}p^i=1+\sum_{i=1}^{p^{n-1}}\left(\frac{p^{n-1}!}{(p^{n-1}-i)!(i)!} \right)p^i$

What I have been trying from here (with no sucess) is to show that $p^{n-1}|\left(\frac{p^{n-1}!}{(p^{n-1}-i)!(i)!} \right)p^i$

**ThePerfectHacker** · January 20th 2009, 03:37 PM

Originally Posted by TheEmptySet

This problem is from Abstract Algebra 3rd edition Dummit and Foote.

Let p be an odd prime and n a positive integer. Use the Binomial Theorem to show that:

$(1+p)^{p^{n-1}} = 1 (\mbox{mod } p^n)$

but

$(1+p)^{p^{n-2}} \ne 1 (\mbox{mod } p^n)$

Deduce that that $1+p$ is an element of order $p^{n-1}$ in the multiplicative group $(\mathbb{Z}/p^n\mathbb{Z} \mbox{ }\cdot)$

Thanks

As hint goes by the binomail theorem I get

$(1+p)^{p^{n-1}}=1+\sum_{i=1}^{p^{n-1}}\binom{p^{n-1}}{i}p^i=1+\sum_{i=1}^{p^{n-1}}\left(\frac{p^{n-1}!}{(p^{n-1}-i)!(i)!} \right)p^i$

What I have been trying from here (with no sucess) is to show that $p^{n-1}|\left(\frac{p^{n-1}!}{(p^{n-1}-i)!(i)!} \right)p^i$

The result is actually stronger, it goes that: $(1+ap)^{p^{n-2}} \equiv 1 + ap^{n-1} (\bmod p^n)$ .
Where, $n\geq 2, p>2, a\in \mathbb{Z}$ .

We will prove this by induction.
When $n=2$ there is nothing to prove.

So say that, $(1+ap)^{p^{n-2}} \equiv 1 + ap^{n-1}(\bmod p^n)$ .
We will prove it for $n+1$ .

Here is a useful result: if $a\equiv b (\bmod p^k) \implies a^p \equiv b^p (\bmod p^{k+1})$ *.

With this result we get, $(1+ap)^{p^{n-1}}\equiv (1+ap^{n-1} )^p (\bmod p^{n+1} )$ .

However, $(1+ap^{n-1})^p \equiv 1 + ap\cdot p^{n-1} + \sum_{j=2}^p {p\choose j} a^j p^{j(n-1)}$ ... [1]

Here is another result: if $1\leq j\leq p-1$ then $p$ divides ${p\choose j}$ .**

Thus every term in sum of [1] for $j=2,...,p-1$ is divisble by $p^{1 + 2(n-1)}$ notice that $1+2(n-1) \geq n+1$ .
Therefore, each term for $j=2,...,p-1$ is divisible by $p^{n+1}$ . For the last term ( $j=p$ ) in sum of [1] we have $a^p p^{p(n-1)}$ . But $p(n-1) \geq n+1$ since $p>3$ . And so we have shown that $p^{n+1}$ divides each term for $j=2,...,p$ in the sum of [1]. Thus, the sum is equivalent to 0 mod $p^{n+1}$ .

Thus, $(1+ap^{n-1})^p \equiv 1 + a p^n (\bmod p^{n+1})$ .

*)Argue by induction. If $a\equiv b(\bmod p^k)$ it means $a = b + qp^k$ for some $q\in \mathbb{Z}$ . Now raise both sides to the $p$ power and apply the binomial theorem again. I think the result that appears in ** (just below) will be useful in this proof.

**)Because ${p\choose j} = \frac{p(p-1)...(p-j+1)}{j!}$ is an integer, since $\gcd(j!,p)=1$ for $1<j<p$ we have that $j!$ divides $(p-1)...(p-j+1)$ . Thus, it leaves a factor of $p$ . Thus, $p$ divides ${p\choose j}$ .

------
We can now prove a stronger result. That the order of $1+ap$ is $p^{n-1}$ mod $p^n$ . Where $p>2,p\not | a, n\geq 2$ .

Okay we have shown $(1+ap)^{p^{n-1}} \equiv 1 + ap^n (p^{n+1})$ . This implies, $(1+ap)^{p^{n-1}} \equiv 1 (\bmod p^n)$ . But, $(1+ap)^{p^{n-2}} \equiv 1 + ap^{n-2} (\bmod p^n)$ (use binomial theorem). However, $1+ap^{n-2}\not \equiv 1 (\bmod p^n)$ since $p\not | a$ . The rest follows.

**TheEmptySet** · February 15th 2009, 12:25 PM

Thanks for that awsome proof. It was very informative and the generalzation was awsome.

Thread: order of an element in mulitpicative group

LinkBack

Thread Tools

Display

order of an element in mulitpicative group

Similar Math Help Forum Discussions

Prove that in any group, an element has the same order of its inverse

order of an element of a group

Group Theory - order of element

Finding the order of a group element

group element order

Search Tags