Hi, need a some help with this proof.

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

How do I go about this?

Thank You for any help.

Printable View

- Sep 29th 2011, 04:08 AMalexgeek101Multiplicative order
Hi, need a some help with this proof.

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

How do I go about this?

Thank You for any help. - Sep 29th 2011, 06:19 AMymarRe: Multiplicative order
You have to try first. What is the definition of the multiplicative order?

- Sep 29th 2011, 07:51 AMDevenoRe: Multiplicative order
step one: what is $\displaystyle (1 + p)^p \ (mod \ p^2)$? justify your answer.

- Oct 1st 2011, 04:22 AMalexgeek101Re: Multiplicative order
- Oct 1st 2011, 08:14 AMDevenoRe: Multiplicative order
try expanding $\displaystyle (1+p)^p$ using the binomial theorem. which terms don't have $\displaystyle p^2$ in them?

- Oct 1st 2011, 08:35 AMalexgeek101Re: Multiplicative order
$\displaystyle (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 $\displaystyle (1+p)^p$ the only terms than don't have $\displaystyle p^2$ in them are $\displaystyle 1$ and $\displaystyle p$.

So where to from here then?

Thanks for your help Dev - Oct 1st 2011, 08:43 AMDevenoRe: Multiplicative order
um, no....

the coefficent of p in the expansion is p:

$\displaystyle (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 $\displaystyle (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? - Oct 1st 2011, 08:49 AMalexgeek101Re: Multiplicative order
- Oct 1st 2011, 09:00 AMDevenoRe: 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". - Oct 1st 2011, 09:05 AMalexgeek101Re: Multiplicative order