# Multiplicative order

• September 29th 2011, 04:08 AM
alexgeek101
Multiplicative order
Hi, need a some help with this proof.

Prove the multiplicative order of $(1+n) \ mod \ n^2$ is $n$ for odd prime $n$.

Thank You for any help.
• September 29th 2011, 06:19 AM
ymar
Re: Multiplicative order
You have to try first. What is the definition of the multiplicative order?
• September 29th 2011, 07:51 AM
Deveno
Re: Multiplicative order
step one: what is $(1 + p)^p \ (mod \ p^2)$? justify your answer.
• October 1st 2011, 04:22 AM
alexgeek101
Re: Multiplicative order
Quote:

Originally Posted by Deveno
step one: what is $(1 + p)^p \ (mod \ p^2)$? justify your answer.

I am sorry, I don't know.

I can see that $n^2$ does not divide $(1+n)^n$.

$\frac{(1+n)^n}{n^2}=0$

$(1+n)^n=0$

which is false for positive n.

I need a little more help if you can.

• October 1st 2011, 08:14 AM
Deveno
Re: Multiplicative order
try expanding $(1+p)^p$ using the binomial theorem. which terms don't have $p^2$ in them?
• October 1st 2011, 08:35 AM
alexgeek101
Re: Multiplicative order
Quote:

Originally Posted by Deveno
try expanding $(1+p)^p$ using the binomial theorem. which terms don't have $p^2$ in them?

$(p+1)^p= \sum_{k=0}^p \tbinom pk p^k \cdot 1^{p-k} = \sum_{k=0}^p \tbinom pk p^k$

So in the expansion of $(1+p)^p$ the only terms than don't have $p^2$ in them are $1$ and $p$.

So where to from here then?

• October 1st 2011, 08:43 AM
Deveno
Re: Multiplicative order
um, no....

the coefficent of p in the expansion is p:

$(p+1)^p = 1 + p^2 + \frac{p(p-1)}{2}p^2 + \dots$ where all the remaining terms involve higher powers of p.

thus $(p+1)^p = 1 (mod\ p^2)$.

so the multiplicative order of p+1 (mod p^2) has to divide p. what are our choices, given that p is an odd prime?
• October 1st 2011, 08:49 AM
alexgeek101
Re: Multiplicative order
Quote:

Originally Posted by Deveno
um, no....

the coefficent of p in the expansion is p:

$(p+1)^p = 1 + p^2 + \frac{p(p-1)}{2}p^2 + \dots$ where all the remaining terms involve higher powers of p.

thus $(p+1)^p = 1 (mod\ p^2)$.

so the multiplicative order of p+1 (mod p^2) has to divide p. what are our choices, given that p is an odd prime?

Oh yeah, slight error on my part. So if the order of p+1 mod p^2 has to divide p and p is an odd prime, then by the definition of a prime, the order of p+1 mod p^2 has to be p.
• October 1st 2011, 09:00 AM
Deveno
Re: Multiplicative order
almost...why isn't the order of p+1, 1 (after all, 1 divides p)?

it's a small detail, and easily answered, but it never hurts to dot the "i's" and cross the "t's".
• October 1st 2011, 09:05 AM
alexgeek101
Re: Multiplicative order
Quote:

Originally Posted by Deveno
almost...why isn't the order of p+1, 1 (after all, 1 divides p)?

it's a small detail, and easily answered, but it never hurts to dot the "i's" and cross the "t's".

Yes, of course! That makes perfect sense. Thanks again for your fantastic help.