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.
$\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
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?