0
$\begingroup$

I am trying,without success,to prove this statement:

Let the divisors of $p-1$ be $d_1,d_2,\cdots$ Prove that if we have a primitive root $g \mod p$ ,then for each $d_i$ there is an element with period $d_i$

I am trying,without success,to prove this statement:

Let the divisors of $p-1$ be $d_1,d_2,\cdots$ Prove that if we have a primitive root $g \mod p$ ,then for each $d_i$ there is an element with period $d_i$

My thinking:

It's given that $g$ is a primitive root ,now let $g=a^t$ where $a$ is not a multiple of $p$ and $t$ is some real number ,so we have that $a^{t},a^{2t},a^{3t},\cdots \equiv 1 \mod p$

Now I know that from Fermat we have $a^{p-1} \equiv 1 \mod p$, so $p-1=t\cdot k $ for some integer $k$.

Since we have that each of $d_i$ is a divisor of $p-1$ we have that $p-1=d_i \cdot q $ where $q$ is an integer,then $d_i \cdot q =t\cdot k$ so I have that $$ a^{d_i}=a^{tk/q} =(a^{tk})^{1/q}$$

Since we have $a^{tk}\equiv 1 \mod p $ we have also that $\left(a^{tk}\right)^{1/q} \equiv 1^{1/q} \equiv 1 \mod p$

Now I don't know what should I do now ,I am terribly confused (I haven't someone to ask for advice)

$\endgroup$
11
  • 1
    $\begingroup$ What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something. $\endgroup$
    – Wojowu
    Jan 15, 2016 at 13:24
  • $\begingroup$ Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 \mod p$ $\endgroup$
    – Mr. Y
    Jan 15, 2016 at 13:34
  • $\begingroup$ In that case, $g=a^t$ never holds for $p>2$, because $a^t\equiv 1$ and $g\not\equiv 1$. $\endgroup$
    – Wojowu
    Jan 15, 2016 at 13:37
  • $\begingroup$ Can't I have $g=a^{t}$ for some real $t$ ? $\endgroup$
    – Mr. Y
    Jan 15, 2016 at 13:45
  • 1
    $\begingroup$ It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $a\equiv b\mod p$, then $a^t=b^t\mod p$. Instead, I would suggest you looking at the integer powers of $g$ itself. $\endgroup$
    – Wojowu
    Jan 15, 2016 at 13:56

1 Answer 1

4
$\begingroup$

It's a much more general fact. If $g$ is an element of period $n$ in a group, and $m$ divides $n$, then the period of $g^{n/m}$ is $m$.

Even more generally, when $k$ is arbitrary, then the period of $g^{k}$ is $$ \frac{n}{\gcd(n, k)}. $$


Proof of the first statement.

For $1 \le k < m$, we have $(n/m) \cdot k < n$, so $(g^{n/m})^{k} = g^{(n/m)\cdot k} \ne 1$. However $(g^{n/m})^{m} = g^{(n/m) \cdot m} = g^{n} = 1$, so the period of $g^{n/m}$ is exactly $m$.

$\endgroup$
1
  • $\begingroup$ If it's not too much disturb,where can I see the proof of this ? $\endgroup$
    – Mr. Y
    Jan 15, 2016 at 14:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .