How do I find what $b$ satisfies $b^{176} \equiv -1 \mod 353$?
This all comes from the original problem of using Proth's Theorem to prove the primality of $353$. Using Wolfram Alpha, $3^{176} \equiv -1 \mod 353$ but I need to at least show why that’s the case, and I’m not sure what the easiest way to do that is.
Would I use the Jacobi symbol or something? Exponentiation ($2^{176} = 2^{128}\cdot 2^{32}\cdot 2^{16}\equiv 1$) seems like it would take forever, especially if I had to test several $b$ values
The computation with bare hands is not that difficult at all... The following computations are done modulo $p=353$, equal means equal in the ring $\Bbb Z/353$. We have $3p=3\cdot 353=1059$, so numbers near $1000$ are getting smaller modulo $p$. $$ \begin{aligned} 3^{176} &=3^2\cdot (3^6)^{29}=9\cdot 729^{29}=9\cdot(23)^{29} \\ &=9\cdot 23\cdot(23^2)^{14} =207\cdot 529^{14} =207\cdot 176^{14} =207\cdot (352/2)^{14} \\ &=207\cdot(-1/2)^{14} =207/(16\cdot 1024) =207/(-16\cdot 35) \\ &=-207/560=-207/207=-1\ . \end{aligned} $$ We have now a generator of the units in $\Bbb Z/p=\Bbb F_p$. The structure of this units group $(\Bbb F_p)^\times$ is the one of a cyclic group. The element $3$ is a generator, since $352=2^5\cdot 11$, and neither $3^{(p-1)/2}$, nor $3^{(p-1)/11}$ is one. All other generators are of the shape $3^k$ with $k$ relatively prime to the order of the units group.