¿Cómo demostrar que un número entero grande dado no es un número cuadrado utilizando el mod?

Question

Dado un número entero grande como $4531893869$ la pregunta es cómo demostrar que este número no es un número cuadrado usando mod $11$ .

Básicamente lo que tenemos es algo así: $$ 4531893869 \equiv x \pmod{11}$$ y sabemos que $ x \in \{1\ldots10\}$ .

Según Wolfram Alpha el resultado es $8$ .

Pero no entiendo cómo esto nos mostrará que este gran número no es un número cuadrado. Tengo que usar explícitamente mod $11$ para resolver esta tarea pero no entiendo el contexto matemático.

Answer 1

Pista. Los cuadrados módulo 11 son $0,1,4,9,5,3$ . Desde $10^k\equiv (-1)^k \pmod{11}$ se deduce que el número $4531893869$ modulo $11$ se puede obtener calculando: $$-4+5-3+1-8+9-3+8-6+9\pmod{11}.$$ Si no pertenece a $\{0,1,4,9,5,3\}$ entonces $4531893869$ no puede ser un cuadrado módulo 11 y por lo tanto no es un cuadrado perfecto.

Answer 2

El punto clave es que no todos los valores mod $11$ puede ser un cuadrado. De hecho, para cualquier cuadrado $n^2$ , $n$ debe ser congruente con una de $0,1,...,10$ mod $11$ y así $n^2$ debe ser congruente con una de $0^2,1^2,...,10^2$ mod $11$ . Así que mientras ninguno de $0^2,1^2,...,10^2$ es congruente con $8$ mod $11$ no hay cuadrados congruentes con $8$ mod $11$ y tu número no puede ser cuadrado.

De hecho, puede ahorrarse algo de trabajo aquí: $10\equiv -1$ mod $11$ Así que $10^2\equiv(-1)^2=1^2$ Así que una vez que hayas comprobado $1^2$ no es necesario comprobar $10^2$ . De manera similar con otros pares de números que tienen suma $11$ por lo que, de hecho, es suficiente con no comprobar ninguna de $0^2,1^2,...,5^2$ es congruente con $8$ mod $11$ .

Answer 3

Sugerencia $\ {\rm mod}\ 11\!:\ n^{\large 2}\equiv 2^{\large 3}\equiv x\ $ cuando se eleva a $\color{#c00}5$ 'El poder contradice al pequeño Fermat, a saber.

$\quad\overset{(\ \ \ )^{\Large\color{#c00} 5}}\Longrightarrow\,\ \underbrace{ 1\equiv (n^{\large 2})^{\large\color{#c00} 5}}_{\rm Fermat}\!\equiv (2^{\large 3})^{\large\color{#c00} 5}\equiv (2^{\large 5})^{\large 3}\equiv (-1)^{\large 3}\equiv -1,\ $ pero $\,\ 1\not\equiv -1\pmod{\!11}$

Nota: $ $ Este método de prueba de cuadratura funciona en general - véase El criterio de Euler . Es mucho más eficiente que las pruebas enumerativas de fuerza bruta para números grandes.

Generalmente podemos refutar las igualdades de expresiones aritméticas enteras comprobando que no son congruentes módulo $m$ . Esto funciona porque la reducción modular es compatible con la suma y la multiplicación (véase el Reglas de suma y producto de congruencia ), por lo que preserva las igualdades (como congruencias) entre expresiones enteras compuestas por sumas y productos, es decir polinomio expresiones de números enteros, por ejemplo $$ P(i,j,k) = Q(i,j,k) \ \Rightarrow\ P(i,j,k)\equiv Q(i,j,k)\pmod m$$

para cualquier polinomio $P,Q$ con coeficientes enteros. Así que si la congruencia falla para algún módulo $m$ entonces la igualdad del lado izquierdo también debe fallar.