Need a simple example of computing the power residue What is a simple but non-trivial, correct example of computing
$a^{(Np-1)/n} \equiv {\zeta_n}^r$ mod $p$
in the definition of the power residue symbol?
This formula is given in two articles (and plenty more, no doubt): The Wikipedia article on the power residue symbol and one on Encyclopedia of math. The formula only works for relatively prime $n$ and the generator of the ideal $p$, so to be extra careful about violating any assumptions, I tried to compute the above formula using three distinct primes:

*

*$a = 7$

*$n = 5$

*$p$ = the ideal generated by $71$
The norm, $Np$, is $|\{u + v\zeta_5 + w{\zeta_5}^2 + x{\zeta_5}^3+ y{\zeta_5}^4 : 0 <= u,v,w,x,y < 71\}|$ = $71^5$ = $1804229351$. (I suspect this computation is my problem since as I explain below, with this value of $Np$, all $5th$ power residue symbols are $1$).
My computation for this example continues,
$a^{(Np-1)/n} = 7^{1804229350/5} = 7^{360845870} \equiv 1$ mod $71$ (since $70|360845870$). So, ${(7/71)}_5 \equiv \zeta^r = 1$ (so $r = 0$). Since the power residue symbol is $1$, $7$ is a $5th$ power mod $71$.
This is both trivial and incorrect:

*

*It is trivial because the power residue symbol is $1$; the congruence mod $p$ doesn't need anything from $\mathbb{Z}[\zeta_5]$ that is not in $\mathbb{Z}$.

*It is incorrect because the only power residue symbols that should be $1$ are those for $a \in \{1,32,37,51,48,23,34,70,45,39,26,20,41\}$, as these are the actual non-zero $5th$ powers mod $71$. Worse still, the calculation above would yield $1$ for any $a$, not just $a = 7$, because it depended only on the fact that $70|360845870$ -- not the value of $a$.

This was just one of my several attempts to find a non-trivial, correct example of a power residue symbol. All of them ended with $r=0$, whether or not $a$ was an $nth$ power. Please correct my computation of $Np$, or another flaw in this computation.
Note: I chose $n$ and the generator $g=71$ of $p$ so that $n | g - 1$, so $(Np-1)/n$ is an integer. When $n$ does not divide $g-1$, everything is an $nth$ power mod $p$. You don't need the power residue formula to know that.
 A: As you noted in the comments, the norm of the ideal $(71) \subset \mathbb Z[\zeta_5] = \mathcal O_{\mathbb Q(\zeta_5)}$ is $71^4$.  But there is a more fundamental problem here:  the ideal $(71)$ isn't prime in $\mathbb Z[\zeta_5]$; in fact, it factors as a product of four distinct primes $\mathfrak{p_1, p_2, p_3, p_4}$, each with norm $71$.
The usual way to determine how primes factor in extensions of number fields is with the Dedekind-Kummer theorem.  In this case, the ring of integers is generated by the element $\zeta_5$ with minimal polynomial $x^4 + x^3 + x^2 + x + 1$.  This polynomial factors over $\mathbb F_{71}$ as $(x - z_1)(x - z_2)(x - z_3)(x - z_4)$ where $z_1, \dots, z_4$ are the four primitive fifth roots of unity modulo $71$--which exist because $71 \equiv 1 \pmod 5$, and which are distinct.  (In fact the four roots are $5$, $25$, $54$, and $57$.)  Since there are four distinct factors, each with degree $1$, the ideal $(71)$ factors as a product of four distinct primes, each with norm $71^1$.  In fact we can even say what they are:  we have $\mathfrak p_i = (71, \zeta_5 - z_i)$ for $i = 1, 2, 3, 4$.
The good news is that we can use any of the $\mathfrak p_i$ to compute the power residue symbol, and it will tell us information about fifth powers in $\mathbb Z/71\mathbb Z$.  This is because the power residue symbol gives information about $n$-th powers in the quotient field $\mathcal O_k/\mathfrak p$, and because $\mathfrak p$ has norm $71$, this quotient field has cardinality $71$ and is therefore isomorphic to $\mathbb Z/71\mathbb Z$.  (You can also directly write down an isomorphism
$$
\mathbb Z[\zeta_5]/(71, \zeta_5 - z_i) \to \mathbb Z/(71)
$$
when $z_i$ is a primitive fifth root of unity mod $71$.  On the other hand, $\mathbb Z[\zeta_5]/(71)$ has cardinality $71^4$ and is therefore not isomorphic to $\mathbb Z/71\mathbb Z$; it happens to be isomorphic to a direct product of four copies of $\mathbb Z/71\mathbb Z$.)
The actual calculation is simpler than you might expect:
$$
7^{\frac{N \mathfrak{p} - 1}{5}} = 7^{\frac{71 - 1}{5}} = 7^{14} \equiv 54 \pmod{71}.
$$
Since this isn't $1$, it follows that $7$ cannot be a fifth power mod $71$.  And this doesn't require any fancy theorems; if $7$ were congruent to $a^5$ mod $71$ for some $a$, then we would have $7^{14} \equiv a^{70} \equiv 1 \pmod{71}$ by Fermat's little theorem.
However, I've cheated slightly:  the power residue symbol is not actually equal to $54$; it's the unique fifth root of unity that's congruent to $54$ modulo $\mathfrak p$.  Which root of unity this is will depend on our choice of prime ideal $\mathfrak p$.  For example, if we take $\mathfrak p = (71, \zeta_5 - 5)$, then we have:
\begin{align*}
\zeta_5 & \equiv 5 \mod p, \\
\zeta_5^2 & \equiv 25 \mod p, \\
\zeta_5^3 & \equiv 54 \mod p, \\
\zeta_5^4 & \equiv 57 \mod p,
\end{align*}
and thus $\left( \frac{7}{\mathfrak p} \right)_5 = \zeta_5^3$.
Of course this last step is unnecessary if you only want to know whether $7$ is a fifth power modulo $71$, but it's important for the power reciprocity law, because there you need to compare power residue symbols modulo two different prime ideals (perhaps lying over two different primes in $\mathbb Z$).  It's a priori nonsensical to compare primitive fifth roots of unity in $\mathbb Z/71\mathbb Z$ with (e.g.) those in $\mathbb Z/31\mathbb Z$, but it's easy to compare primitive fifth roots of unity in $\mathbb Z[\zeta_5]$ with each other.
One last comment:  your last paragraph isn't quite correct when $n$ is composite.  Everything mod $\mathfrak p$ is an $n$-th power if and only if $n$ is relatively prime to $N\mathfrak p - 1$.  In general, if $\gcd(n, N\mathfrak p - 1) = d$, then $\mathcal O_k/\mathfrak p$ contains exactly $d$ $n$-th roots of unity (namely, the $d$-th roots of unity) and exactly $\frac{N\mathfrak p - 1}{d}$ nonzero $n$-th powers (namely, the nonzero $d$-th powers).
