¿Encontrar todas las posible $x$ dado el % de congruencia $(x+y)^p-y^p \equiv 1 \pmod{q}$para ambos $p<q$ prime?

Question

Unos pocos ejemplos.

$$\begin{array}{c|c|l} \text{prime } p & \text{prime } q & \text{possible values } x \\ \hline 3 & 5 & [1, 2, 4] \\ 5 & 13 & [1, 3, 5, 8, 9, 10] \\ 13 & 17 & [1, 4, 7, 10, 14, 15, 16] \\ 23 & 37 & [1, 2, 3, 6, 11, 12, 15, 18, 19, 22, 29, 30, 35] \\ \end{matriz} $$

Se observa que el número de soluciones es limitado. $x=1$ es siempre una solución si tenemos $y=q-1$.

¿Hay una manera general de encontrar posibles soluciones para $x$?

Answer 1

Si $z = x+y$, que se está resolviendo $z^p \equiv 1 + y^p \mod q$.

Si $\gcd(p, q-1) = 1$, el mapa de $t \mapsto t^p$ es uno-a-uno en $\mathbb Z/q \mathbb Z$, por lo que siempre hay un $z$. Si $\gcd(p, q-1) = g > 1$, el mapa no es ni de uno a uno ni sobre, por lo $y$ no hay solución y para los demás, hay varios. El cero $p$'th poderes de mod $q$ forman un subgrupo de el grupo multiplicativo de mod $q$.

Por ejemplo, si $p = 5$$q = 11$, $5$'th poderes de mod $11$ $0, 1, 10$. $z^5 \equiv y^5 + 1$ tiene soluciones $y^5 = 0, z^5 = 1$ correspondiente a $y=0, z = 1,3,4,5,9$, e $y^5=10, z^5 = 0$ correspondiente a $z=0, y=2,6,7,8,10$.