# order of an element in mulitpicative group

• Jan 20th 2009, 02:38 PM
TheEmptySet
order of an element in mulitpicative group
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$
• Jan 20th 2009, 03:37 PM
ThePerfectHacker
Quote:

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. (Surprised)
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 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.
• Feb 15th 2009, 12:25 PM
TheEmptySet
Thanks for that awsome proof. It was very informative and the generalzation was awsome. :)