Encuentra la fórmula para calcular el número de enteros congruentes a n mod p entre a y b inclusive donde a,b son enteros

Question

Como se lee en el título, el objetivo es encontrar una fórmula que dé un número de enteros congruentes a n mod p entre a y b.

Por ejemplo, si $(a,b)=(0,100)$ Hay $51$ enteros congruentes $0$ mod $2$ entre $0$ y $100$ inclusive. Si $(a,b)=(32,456)$ Hay $106$ enteros congruentes $2$ mod $4$ entre $32$ y $456$ inclusive.

¿Existe ya una fórmula? Y si es así, ¿cuál es esa fórmula?

Con un poco de investigación, podemos encontrar para los enteros en 0,1 mod 2, para los enteros en 0,1,2 mod 3, etc... Pero sin duda debe tener un patrón para encontrar una fórmula.

Answer 1

Voy a escribir una fórmula $H(a, b, n, p)$ para el número de elementos congruentes con $n$ , modulo $p$ en el intervalo $a \le k < b$ . Si quieres aplicarlo para obtener la respuesta a la pregunta que has formulado, tienes que evaluar $H(a, b+1, n, p)$ para que la suma sea inclusiva en ambos extremos. Estoy asumiendo aquí que $b \ge a$ .

Además, voy a utilizar la convención de los informáticos de que $$ (x, y) \mapsto x \bmod y $$ es un función definido en pares de enteros, donde $y$ debe ser positivo, y que el valor de esta función es el número en el rango $0, 1, \ldots, y-1$ que es congruente con $x$ , modulo $y$ .

Obsérvese que para cualquier $a, b, n, p$ y $s$ tenemos $$ H(a, b, n, p) = H(a-s, b-s, n-s, p), $$ por lo que elegir $s = a$ podemos simplemente calcular nuestra respuesta calculando $$ H(a-a, b-a, n-a, p) = H(0, b-a, n-a, p). $$ A continuación, observe que si ajustamos $n-a$ por algún múltiplo de $p$ la respuesta sigue siendo la misma, por lo que si decimos $n' = (n-a) \bmod p$ entonces sólo tenemos que calcular $$ H(0, b-a, n', p) $$ y ahora $n'$ es un número entre $0$ y $p-1$ . Para simplificar un poco más, escribamos $b' = b-a$ por lo que buscamos calcular $$ H(0, b', n', p). $$ En cualquier lapso de $p$ enteros secuenciales, hay UNO que es congruente con $n'$ Así que veamos cuántos tramos de este tipo hay, empezando por $0$ y detenerse cuando aún es menor que $b'$ . Eso es exactamente $$ U(b', p) = \lfloor \frac{b'}{p} \rfloor. $$ Lo que queda es una secuencia de menos de $p$ números de $pU(b', p)$ a $b'$ en el que puede haber o no un número congruente con $n'$ . Tomado $\bmod p$ Esta secuencia tiene el siguiente aspecto $$ 0, 1, 2, \ldots, (b'-1) \bmod p $$ y tenemos que añadir uno a nuestra cuenta exactamente si uno de esos números es $n'$ . En resumen, obtenemos $$ H(0, b', n', p) = U(b', p) + \begin{cases} 1 & n' < (b' \bmod p) \\ 0 & n' \ge (b' \bmod p) \end{cases}. $$

Sustituyendo esto por los valores originales, obtenemos $$ H(a, b, n, p) = \lfloor \frac{b-a}{p} \rfloor + \begin{cases} 1 & (n \bmod p) < ((b-a) \bmod p) \\ 0 & (n \bmod p) \ge ((b-a) \bmod p) \end{cases}. $$

Es posible que haya alguna forma bonita de simplificar esto un poco, pero... creo que ya he dicho bastante.

Answer 2

Dada la gama $[a,b]$ y la congruencia $k \mod n$ , entonces primero, restar $k$ de cada uno de $a$ y $b$ para crear una nueva gama $[a-k,b-k]$ .

Esto no cambia el tamaño de ninguna de las clases de congruencia de usar $n$ .

Queremos encontrar el tamaño de cada clase de congruencia para los residuos $0,\dots,n-1$ y empezamos con $a-k \mod n$ Esto tiene $\lfloor\frac{b-k-(a-k)}{n}\rfloor+1=\lfloor\frac{b-a}{n}\rfloor+1$ elementos en él.

El siguiente residuo que examinamos es $a-k+1 \mod n$ que tiene $\lfloor\frac{b-k-(a-k+1)}{n}\rfloor+1=\lfloor\frac{b-a-1}{n}\rfloor+1$ elementos en él.

Y continuar hasta el residuo $a-k+n-1 \mod n$ que tiene $\lfloor\frac{b-k-(a-k+n-1)}{n}\rfloor+1=\lfloor\frac{b-a-n+1}{n}\rfloor+1$ elementos en él.

Answer 3

Con la ayuda de las respuestas que has enviado, he podido encontrar un formulario que me parece bastante sencillo. Luego no estoy 100% seguro de que funcione siempre.

Dejemos que $S$ sea el número de enteros congruentes con ${n}\pmod p$ en el intervalo $a$ inclusivo y $b$ inclusivo

$T=n-a+p\lfloor\frac{b-n}{p}\rfloor$

$S =\lfloor\frac{T}{p}\rfloor+1$