Número de pares ordenados $(x, y)$ tal que $0 \leq x, y\leq 18$ y $3x+4y+5$ es divisible por $19$

Question

El problema habría sido mucho más sencillo si no hubiera un término constante, (como $3x+4y$ divisible por 19) porque entonces todas las soluciones podrían haberse generado a partir de la solución de $3x+4y=19$ .

He probado muchas cosas, una de ellas la enumeración dolorosa. Las siguientes son las soluciones a $3x+4y+5=19k$ como trillizos ordenados $(x, y, k)$

( 0, 13, 3 ) ( 1, 17, 4 ) ( 2, 2, 1 ) ( 3, 6, 2 ) ( 4, 10, 3 ) ( 5, 14, 4 ) ( 6, 18, 5 ) ( 7, 3, 2 ) ( 8, 7, 3 ) ( 9, 11, 4 ) ( 10, 15, 5 ) ( 11, 0, 2 ) ( 12, 4, 3 ) ( 13, 8, 4 ) ( 14, 12, 5 ) ( 15, 16, 6 ) ( 16, 1, 3 ) ( 17, 5, 4 ) ( 18, 9, 5 )

Es evidente que hay 19 pares ordenados, uno por cada $x$ de $0$ a $18$ . ¿Por qué es así? Es decir, ¿por qué hay uno y sólo uno par ordenado para cada $x$ ? Creo que hay un par ordenado para una $x$ en cada $19$ números consecutivos para $y$ por ejemplo $1$ en $0$ a $18$ otro en $2$ a $20$ ...

Además, ¿cómo podemos concluir que siempre habrá algún par ordenado para cada $x$ ?

También he visto que esto no es especial para $19$ , ocurre para todos los números. Siento que me estoy perdiendo algo grande aquí.

Se agradecería cualquier ayuda.

Answer 1

Pista: Buscamos soluciones de $3x+4y+5\equiv 0\pmod{19}$ . Equivalentemente (multiplicar por $5$ ) estamos resolviendo $15x+y=\equiv -6\pmod{19}$ o, por el contrario $y\equiv 4x-6\pmod{19}$ . Ahora está claro que para cada $x$ hay un único $y$ en el intervalo $0$ a $18$ para los que la congruencia se mantiene. Es el resto cuando $4x-6$ se divide por $19$ .

Answer 2

Tenga en cuenta que $3x+4y+5$ es divisible por $19$ si y sólo si $5(3x+4y+5)=15x+20y+25$ es divisible por $19$ si y sólo si $15x+y+6$ es divisible por $19$ . Así que dado $x$ se puede calcular $y$ mediante la computación $4x+13$ modulo $19$ para conseguir $y$ .

Puede hacerlo porque $4$ es relativamente primo de $19$ . En general, dado $a,b,n$ , si $b$ y $n$ son relativamente primos entonces el número de pares $0\leq x,y<n$ tal que $ax+by+c$ es divisible por $n$ es $n$ .

Eso es porque hay un $b'$ para que $bb'=1+nk$ para algunos $k$ y $ax+by+c$ es divisible por $n$ si y sólo si $ab'x+bb'y+cb'$ es divisible por $n$ si y solo si $y+(ab'x+cb')$ es divisible por $n$ . Así que hay exactamente una $y$ para cada $x$ .