# Is 3 ever a seventh power mod a prime $p$ if $p\equiv 1 (7)$

I had a question asking when is 3 a seventh power modulo a prime $p$ if $p=1(7)$. However, I tried to find just one example using mathematica but I went up to primes in the thousands and I still couldn't find an example, so I began thinking this was a trick question.

-
What do you mean by $1(7)$? – Henning Makholm Nov 3 '12 at 17:03
$p$ is congruent to 1 modulo 7 – Steven-Owen Nov 3 '12 at 17:10
Since, in ${\mathbb{Z}}/757\mathbb Z$, we have $2^{84}=3$, we have $(2^{12})^7=3$, in other words $3 \equiv 311^7 \pmod{757}$. – Lubin Nov 3 '12 at 18:51

$3$ is not a seventh power $\pmod{29}$ since: $$3^{\frac{29-1}{7}}\equiv 81\equiv -6\not\equiv 1 \pmod{29}.$$ Another way to state the same is that the only seventh powers in $\mathbb{Z}_{/29\mathbb{Z}}^*$ are $\pm 1$ and $\pm 12$.

-
Like I said, I tested this case and all primes congruent to 1 modulo 7 up until the thousands. I'm asking if it can EVER happen. – Steven-Owen Nov 3 '12 at 17:12
Actually why does showing $3^{\frac{29-1}{7}}\not\equiv 1 (29)$ suffice in showing that $3$ is not a seventh power? – Steven-Owen Nov 3 '12 at 17:40
If $3 = x^7$ then $x^{29-1} = 3^{\frac{29-1}{7}}$ but the former quantity is 1 by Fermat's little theorem. – user29743 Nov 3 '12 at 17:42
Is the converse true? I.e. if $3^{\frac{p-1}7}\equiv 1 (p)$ is it true then $x^7 \equiv 3 (p)$ always has a solution? – Steven-Owen Nov 3 '12 at 17:50

There is much classical work on this and related questions. You can find pointers to the literature from the introduction of Stanislav Jakubec's  Criterion for 3 to be eleventh power,  Acta Mathematica et Informatica Universitatis Ostraviensis (1995), Vol. 03, 1, excerpted below

-

Based on what Jack and countinghaus said, I started looking for primes such that $3^{\frac{p-1}{7}}\equiv 1 (p)$ and found actually that $p=757$ works!

Others that work include: 1583, 1597, 2843, 2927.

However, I'm not sure if this will always work.

I know based on what they said, if $3$ is going to be a seventh root then $3^{\frac{p-1}{7}}\equiv 1 (p)$ must be true, but could someone tell me if the converse is true?

-
Yes, sure. When $p=7k+1$, the cyclic group of nonzero residues is of order $7k$, and its subgroup of $7$-th powers is cyclic of order $k$, and an element of the big group is in the subgroup if and only if its $k$-th power is identity. – Lubin Nov 3 '12 at 18:39
In general, suppose that $m$ has a primitive root. This is the case, for example, if $m$ is prime. Suppose $\gcd(a,m)=1$. Then the congruence $x^k\equiv a\pmod{m}$ has a solution iff $a^t\equiv 1\pmod{m}$, where $t=\varphi(m)/\gcd(k,\varphi(m))$. Take $a=3$, $k=7$, $m=p$. – André Nicolas Nov 3 '12 at 21:41
@AndréNicolas Thanks for yet another great answer. This was a problem given by Barry Mazur in a class back then. If I may is this correct, since $p=1+7l$ and $\phi(p)=1+l7-1$, then $(k, \phi(p))=7$ and $t=7l/7=l$ so there is a solution whenever $a^l\equiv 1\pmod p$? Thanks and best regards, – TheBirdistheWord May 23 at 14:31
@Andrew: Yes, my comment was intended to describe the (sort of) "general" case, and you have used it for our particular setting. – André Nicolas May 23 at 15:40