La probabilidad de satisfacer $a_1x_1 + a_2x_2 + ... \equiv a_{n+1} \mod p$ donde p es primo

Question

El libro de texto que estoy leyendo afirma que la probabilidad de encontrar una solución satisfactoria a $a_1x_1 + a_2x_2 + ... \equiv a_{n+1} \mod p$ donde $a_1...a_{n+1}$ son constantes es siempre $\frac{1}{p}$ si $p$ es primo. El libro de texto pasa entonces a un tema completamente diferente. No estoy seguro de por qué es así ¿alguna idea de cómo pensar en esto?

Puedo ver que $a_1x_1 \equiv a_{n+1} \mod p$ tiene una probabilidad de $\frac{1}{p}$ porque sólo hay una solución posible. Esto se debe a que $p$ es primo. Pero no sé por qué es la misma probabilidad cuando involucramos más variables?

Gracias

Answer 1

Todos los módulos matemáticos $p$ .

Para ser extremadamente preciso, es necesario este descargo de responsabilidad:

Si $a_1 = a_2 = \dots = a_n = 0$ entonces la probabilidad es $1$ (si $a_{n+1} = 0$ ) o $0$ (si $a_{n+1} \neq 0$ ).

Ahora que este caso especial está fuera del camino, podemos asumir algunas $a_j \neq 0$ . Entonces podemos reordenar la ecuación como

$$x_j = a_j^{-1} (a_{n+1} - \sum_{i = 1\\i \neq j}^n a_i x_i )$$

En otras palabras, no importa cómo se elijan los valores de los otros $x_i$ hay exactamente una $x_j$ que satisface la ecuación. Así, la probabilidad para un vector uniformemente aleatorio es $1/p$ .

(De hecho, esta prueba muestra que sólo se necesita una aleatoriedad uniforme en un variable donde el coeficiente es distinto de cero... las otras variables pueden ser aleatorias de alguna manera no uniforme, o elegidas por un adversario, etc.)

Tiene usted toda la razón en que $p$ ser primo se utiliza para proporcionar la existencia de la inversa $a_j^{-1}$ .

(Si $p$ es compuesta, la prueba sigue funcionando siempre que se tenga una variable aleatoria uniforme con un coeficiente $a_j$ que tiene una inversa. Por ejemplo, en el módulo $6$ tenemos $1\times 1 = 5 \times 5 = 1$ por lo que si algún coeficiente es $1$ o $5$ la probabilidad seguirá siendo $1/p$ .)