Encontrar posibles restos al dividir un número entero

Question

Estaba atascado tratando de resolver una pregunta de matemáticas de GRE, y esta pregunta vino a mi mente cuando miré la solución. La pregunta es

Para algunos enteros $q$ , $q^2 - 5$ es divisible por todo lo siguiente EXCEPTO

(A) $29$
(B) $30$
(C) $31$
(D) $38$
(E) $41$

Lo solucioné eliminando las respuestas (conectando los valores para $q$ que obviamente tomó algún tiempo y no funcionará para números más grandes), y la solución dice:

Empieza con algo pequeño. Recuerda que cuando se divide por $3, q^2$ tiene el resto $0$ o $1$ . Así que $q^2 - 5$ tiene el resto $1$ o $2$ que significa no divisible por $3$ así que B.

¿Cómo sabemos que el resto cuando $ \frac {q^2}{3}$ sólo va a ser $0$ o $1$ sólo? Sé que el resto TIENE que ser menos de 3, pero ¿cómo se puede saber que no puede ser $2$ ? ¿Y cómo deduce que sólo puede ser $1$ o $2$ cuando $5$ se resta del resultado? Es fácil de ver cuando se conectan los valores y se comprueban, pero ¿hay un método generalizado para averiguarlo?

Answer 1

$q$ es un número entero, así que puede ser congruente con $0$ , $1$ o $2$ mod $3$ . Otra forma de escribir $q \equiv 2$ mod $3$ es $q \equiv -1$ mod $3$ . Esto significa que $q^2 \equiv 1$ mod $3$ porque $(-1)^2=1$ . Por lo tanto, $q^2$ tiene el resto de sólo $1$ o $0$ .

Puedes extender esto al mod $5$ porque todos los números enteros son congruentes con $0$ , $1$ , $2$ , $3$ , $4$ mod $5$ o alternativamente $0$ , $1$ , $2$ , $-2$ , $-1$ . La cuadratura de un número significa que el número al cuadrado es congruente con $1$ o $2^2$ o es un múltiplo de $5$ .

Answer 2

Cuando miras las cosas modulares $3$ hay tres tipos de números: los de la forma $3k$ (múltiplos de 3), los de la forma $3k+1$ y los de la forma $3k+2$ . Intentemos cuadrarlas, y veamos qué forma tiene:

$$ \begin {align} (3k)^2 &= 9k^2=3(3k^2) \\ (3k+1)^2 &= 9k^2+6k+1=3(3k^2+2k)+1 \\ (3k+2)^2 &= 9k^2+12k+4=3(3k^2+4k+1)+1 \end {align}$$

Como pueden ver, cada cuadrado tiene la forma $3K$ o $3K+1$ para algunos nuevos $K$ .

Una forma más fácil de comprobar esto es simplemente mirar $0^2$ , $1^2$ y $2^2$ ya que los números $0$ , $1$ y $2$ sirven como representantes de las tres clases mencionadas anteriormente.

En cuanto a la sustracción $5$ puedes hacer cálculos similares.

$$(3k+1)-5=3k-4=3k-6+2=3(k-2)+2$$

o para usar una notación más compacta:

$$1-5 \equiv 2 \pmod {3}$$

También puede verificar que $0-5 \equiv 1 \pmod3 $ .

Answer 3

Ver cualquier número entero que no sea un múltiplo de 3 puede ser escrito como $$ q = 3K \pm 1 $$ Por lo tanto, $$ \ q^2 = 9\ k^2 \pm 6K + 1 $$

así que, cuando se divide por 3, siempre da el resto como 1.

Mientras que para los enteros que son múltiplos de 3, dan el resto como 0.

¡¡Espero que esto ayude!!

Answer 4

$q^2-5=( q^2-1) +4 = ( q+1) (q-1) +4$

Ahora $q-1, q, q+1$ son tres enteros consecutivos y por lo tanto uno de ellos debe ser un múltiplo de 3

Caso $1$ : $q-1$ o $q+1$ es un múltiplo de $3$ entonces, $q^2-5$ no es porque $4$ no es un múltiplo de $3$

Caso $2$ : $q$ o $q^2$ es un múltiplo de $3$ pero entonces $q^2 -5$ no es un múltiplo de $3$

Así que $q^2 -5$ nunca puede ser un múltiplo de $3$ y por lo tanto la respuesta es B $30$