Number Theory Concept

NuncChaos · Poincare Conjecture Offline Joined: 03 Feb 2008 Posts: 149

Let $p$ be a prime and $g$ an integer such that the period of $g (mod p)$ is $p-1$ . Let all $d_k$ be divisors of $p-1$ . Prove that there is an element with period $d_k$ for all $d_k$

It says in the book that since g has period p-1, then $g^{(p-1)/(d_1)}, g^{(p-1)/(d_2)}...$ all have periods $d_1, d_2...$ , respectively.

Why is this?

**Posted:** Thu Nov 05, 2009 11:42 am

mavropnevma

For $d \mid p-1$ , let $k$ be the multiplicative order (not period) of $g^{\frac {p-1} {d}}$ modulo $p$ . This means $\left (g^{\frac {p-1} {d}}\right )^k = g^{k\frac {p-1} {d}} \equiv 1 \pmod{p}$ , so $p-1 \mid k\frac {p-1} {d}$ , i.e. $d \mid k$ . But $\left (g^{\frac {p-1} {d}}\right )^d = g^{p-1} \equiv 1 \pmod{p}$ , so $d$ is the multiplicative order of $g^{\frac {p-1} {d}}$ .

**Posted:** Thu Nov 05, 2009 12:47 pm

_________________
Listen to REMBETIKA for decoding the handle.