# Thread: order of an element in mulitpicative group

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

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

but

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

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

Thanks

As hint goes by the binomail theorem I get

$\displaystyle (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 $\displaystyle p^{n-1}|\left(\frac{p^{n-1}!}{(p^{n-1}-i)!(i)!} \right)p^i$

2. 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:

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

but

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

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

Thanks

As hint goes by the binomail theorem I get

$\displaystyle (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 $\displaystyle p^{n-1}|\left(\frac{p^{n-1}!}{(p^{n-1}-i)!(i)!} \right)p^i$
The result is actually stronger, it goes that: $\displaystyle (1+ap)^{p^{n-2}} \equiv 1 + ap^{n-1} (\bmod p^n)$.
Where, $\displaystyle n\geq 2, p>2, a\in \mathbb{Z}$.

We will prove this by induction.
When $\displaystyle n=2$ there is nothing to prove.
So say that, $\displaystyle (1+ap)^{p^{n-2}} \equiv 1 + ap^{n-1}(\bmod p^n)$.
We will prove it for $\displaystyle n+1$.

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

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

However, $\displaystyle (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 $\displaystyle 1\leq j\leq p-1$ then $\displaystyle p$ divides $\displaystyle {p\choose j}$.**

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

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

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

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

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

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

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