I am working on a problem that requires to find what values of $n$ will give a solution to the equation: $$1 + b^n \equiv c^n \pmod p$$ (where $p$ is a known prime and $0<b,c,n<p$ )
I tried the naive approach but that takes way lot of time. Is there any way to speed up the searching? Also is there a way to count the number of values of $n$ in $(0,p)$ that satisfy the equation?
NOTE : I just want to find the values (or at least the count) of $n$ but not the all possible solutions for a certain value of $n$. Thank you :)
For any given $n$, there will a fixed number of solutions of $b^n=k \bmod p$ - this number $s_n = (p-1)/\gcd(p-1,n)$. Whenever $\gcd(p-1,n)=1$, every $k\in [1..p{-}1]$ will be a solution for exactly one $b$. Otherwise, the exact location of these solutions in $[1..p{-}1]$ is hard to predict, so the number of such solutions that are separated by $1$ (to give solutions to $1+b^n\equiv c^n\bmod p$) is also difficult to know. A few cases are obvious, like $n=(p-1)/2$, when $s_n=2$ and there are no solutions for $p>3$.