problema de divisibilidad y mcd

Sean a y b números enteros positivos. Prueba de que si el número 100 a b − 1 divide numero ( 100 a 2 − 1 ) 2 entonces también divide el número ( 100 b 2 − 1 ) 2 .

Mi intento:

Notemos que

b 2 ( 100 a 2 − 1 ) 2 − a 2 ( 100 b 2 − 1 ) 2 = ( 100 a 2 b − b ) 2 − ( 100 a b 2 − a ) 2 = ( 100 a 2 b − b − 100 a b 2 + a ) ( 100 a 2 b − b + 100 a b 2 − a ) = ( 100 a b ( a − b ) + ( a − b ) ) ( 100 a b ( a + b ) − ( a + b ) ) = ( a − b ) ( 100 a b + 1 ) ( a + b ) ( 100 a b − 1 ) .

Esto significa que 100 a b − 1 | a 2 ( 100 b 2 − 1 ) 2 , entonces si demostramos que mcd ( 100 a b − 1 , a 2 ) = 1 la prueba está completa. Ahora sé que debería ser trivial mostrar que estos números son relativamente primos, pero de alguna manera no tengo idea de cómo hacerlo.

También estoy interesado si hay una manera de resolver este problema usando aritmética modular.

Si d > 1 es un factor primo de a 2 entonces d | a y d | 100 a b entonces d ⧸ | 100 a b − 1 (es uno menos que un múltiplo de d ). Entonces los términos no tienen factores primos en común y mcd ( 100 a b − 1 , a 2 ) = 1 .
¡Gracias! Ahora lo entiendo :)
Edité mi respuesta para mostrar cómo interpretar su prueba modularmente de una manera muy simple.
@BillDubuque ¡Gracias! ¡Ustedes son increíbles!

Respuestas (2)

Para un argumento aritmético modular:

Dejar norte = 100 a b − 1 y modulo de trabajo norte .

Empezando con ( 100 a 2 − 1 ) 2 ≡ 0 , multiplicar por 10 4 b 4 :

( 10 4 a 2 b 2 − 100 b 2 ) 2 ≡ 0.

Desde 10 2 a b ≡ 1 , tenemos ( 1 − 100 b 2 ) 2 ≡ 0.

¿Podría explicar un poco más la última línea? Lo entiendo 10 2 a b ≡ 1 por que estos significa que ( 1 − 100 b 2 ) 2 ≡ 0 . Lo siento si esta es una pregunta estúpida. Estoy empezando a aprender algo de teoría básica de números.
En la línea anterior he reemplazado 10 4 a 2 b 2 = ( 100 a b ) 2 por 1 .
creo que entiendo Así que digamos que ( X − y ) 2 ≡ 0 (mod n) y sabemos que X ≡ 1 entonces podemos escribir eso ( 1 − y ) 2 ≡ 0 ?
Sí, eso es correcto. ¡Los argumentos aritméticos modulares son tan fáciles!
¡Gracias! Solo tengo una pregunta. Qué propiedades de la aritmética modular estamos usando cuando reemplazamos x por 1. Quiero decir que es obvio para mí que si X ≡ 1 entonces X − y ≡ 1 − y pero ¿por qué esto también es cierto cuando tenemos ( X − y ) 2 ? ¿Es porque podemos multiplicar las congruencias?
Desde X ≡ 1 , tenemos X − y = 1 + k norte − y para algunos k . Cuando esto se eleva al cuadrado, podemos ignorar todos los múltiplos de norte si estamos trabajando modulo norte .
Al llevar a cabo un argumento aritmético modular de este tipo, simplemente trate X y 1 como el mismo.
Bueno. ¡Gracias otra vez!
@S.Dolan Cuidado. No siempre es el caso, cuando se trata de aritmética modular, que un número X puede ser reemplazado por cualquier otro número y congruente con X .
Siempre es el caso de los elementos del anillo de números enteros mod N involucrados en las operaciones aritméticas. Por supuesto, no es el caso de otros elementos como los que se utilizan en la notación estándar de potencias.
@alicia211 X ≡ a ⇒ F ( X ) ≡ F ( a ) para cualquier polinomio F ( X ) con coeficientes enteros - consulte la Regla de congruencia polinomial y otras leyes aritméticas de congruencia básicas demostradas allí. Agregué una respuesta que da una derivación más motivada usando aritmética modular, que muestra cómo es un caso especial de un método conocido más general.

Mostramos cómo la aritmética modular nos permite verla como un caso especial de inversión de polinomios , es decir, que F ( a ) = 0 ⇒ F ~ ( a − 1 ) = 0 , dónde F ~ denota el polinomio inverso (reciproco).

Aquí la aritmética mod funciona muy bien: modificación 100 a b − 1 tenemos 100 a b ≡ 1 entonces a ≡ 1 / ( 100 b ) . Podemos sustituir esto en cualquier ecuación polinomial F ( a ) ≡ 0 luego borra los denominadores para obtener una ecuación gramo ( b ) ≡ 0 para b . Aquí F ( a ) ≡ ( 100 a 2 − 1 ) 2 ≡ 0 por lo que dijo s tu b s t i t tu t i o norte para a rendimientos

0 ≡ F ( a ) ≡ [ 100 ( 100 b ) 2 − 1 ] 2 ≡ [ 1 − 100 b 2 100 b 2 ] 2 ⇒ ( 1 − 100 b 2 ) 2 ≡ 0

Su prueba, vista modularmente, esencialmente cuadra la siguiente ecuación (compare aquí )

b ( 100 a a − 1 ) ≡ a ( 1 − 100 b b ) ⟺     b   ( b − 1   a − 1 ) ≡ a ( 1 −   a − 1   b ) ,   es cierto por ambos ≡ a − b

Entonces al cuadrar obtenemos ( 100 a a − 1 ) 2 ≡ 0 ⇒ a 2 ( 1 − 100 b b ) 2 ≡ 0 ⇒ ( 1 − 100 b b ) 2 ≡ 0 cancelando dos veces la unidad (invertible) a , es decir, escalando por a − 1 ( ≡ 100 b ) .

Observación Podemos hacer toda la aritmética sin fracciones escalando F ( a ) por ( 100 b 2 ) 2 (esto es esencialmente lo que se hace en la respuesta de S. Dolan, pero ahí está la idea clave ( mi yo i metro i norte a t i o norte ) no se destaca).

Arriba hay una ligera variación del siguiente resultado bien conocido: si a es una raiz de un polinomio F ( X ) entonces a − 1 es una raíz del polinomio recíproco (inverso) X d F ( 1 / X ) , d := grado ⁡ F , como anteriormente.

Así, usando aritmética modular podemos expresar el problema usando ecuaciones (congruencias) y esto nos permite usar hechos bien conocidos sobre la relación entre una ecuación para a y uno por su inversa a − 1 . Esta relación se ofuscaría si usáramos solo lenguaje de divisibilidad (frente a ecuaciones de congruencia ).

Véase también aquí para un análogo lineal , que puede verse como la unicidad de los inversos .
Ver también aquí para pruebas de divisibilidad recíproca/inversa.
problema de divisibilidad y mcd
RespuestasAquíPolítica de privacidad1y, 0v