Let there is a primitive root $r$ for $\mod n$
(1) Existence of a root for the equation $x^k \equiv a \pmod n$.
Then, between the below two statements which one is the iff statement for the (1)?
Let $d = \gcd(k, \phi(n))$
1) $a^{\phi(n) \over d}\equiv 1\pmod {\phi(n)}$
2) $a^{\phi(n) \over d}\equiv 1\pmod n$
Personally I vote to the 2nd statement is right.
Here is the ground Why I chose the 2nd statemnet.
My proof) I'm just considering the case for $gcd(n, a) = 1 $
$a^ {\phi(n) \over d}\equiv 1 (mod n)$
$\iff$ ${\phi(n) \over d} ind_r{a} \equiv 0(mod \phi(n))$for a primitive root, $r$
$\iff$ $d \vert ind_r{a}$
$\iff$ $\exists X(= ind_{r}x) \in Z$ $s.t.$ $kX \equiv ind_{r}{a}(mod \phi(n))$ for the integer set, $Z$
$\iff \exists x \in Z$ $s.t.$ $x^k \equiv a(mod n)$
But can't sure my decision is correct. What do you think?
Best Answer
$x\cong a^{1/k}\pmod n$.
For some $c$, $r^c\cong a^{1/k}\pmod n$.
Now $1\cong r^{c\phi(n)}\cong a^{\phi(n)/k}\pmod n$.
Finally, $d\mid k\implies k=f\cdot d$. So $1\cong a^{\phi(n)/(fd)}\pmod n\implies 1^f\cong a^{\phi(n)/d}\pmod n$ or $1\cong a^{\phi(n)/d}\pmod n$.