Cada entero que tiene la forma [matemáticas] 3n + 1 [/ matemáticas] y [matemáticas] 5n + 2 [/ matemáticas] también tiene la forma [matemáticas] 15n + 7 [/ matemáticas]. ¿Podemos generalizar esto para cualquier número entero que tenga la forma [math] pn + \ frac {p-1} {2} [/ math] y [math] qn + \ frac {q-1} {2} [/ math] para primos [matemáticas] p, q [/ matemáticas]?

Answer 1

Este es un caso especial del teorema del resto chino .

Teorema del resto chino (CRT). Dados enteros positivos [matemática] m_1, m_2, m_3, \ ldots, m_k [/ math], parprime coprime y enteros [math] r_1, r_2, r_3, \ ldots, r_k [/ math], con [math] 0 \ le r_i \ le m_i-1 [/ math] para cada [math] i [/ math], de modo que hay infinitos enteros [math] N [/ math] que satisfacen

[matemática] N \ equiv r_i \ pmod {m_i} [/ matemática], [matemática] i \ in \ {1,2,3, \ ldots, k \} [/ matemática].

Además, si [matemática] N_1 [/ matemática] y [matemática] N_2 [/ matemática] son ​​dos soluciones, entonces es necesario y suficiente que [matemática] N_1-N_2 [/ matemática] sea divisible por [matemática] M = \ displaystyle \ prod_ {i = 1} ^ k m_i [/ ​​math].

La existencia de [math] N [/ math] simplemente significa que existen enteros [math] n_1, n_2, n_3, \ ldots, n_k [/ math] tales que

[matemática] N = m_1n_1 + r_1 = m_2n_2 + r_2 = m_3n_3 + r_3 = \ cdots = m_kn_k + r_k [/ math].

---

En el problema dado, [math] n [/ math] no representa un valor específico de un entero. Se utiliza para representar la forma del entero, la progresión aritmética a la que pertenece el entero. Por ejemplo, progresiones aritméticas con diferencia común [matemática] 3 [/ matemática] y que contiene [matemática] 1 [/ matemática] y progresiones aritméticas con diferencia común [matemática] 5 [/ matemática] y que contiene [matemática] 2 [/ matemática] son progresiones aritméticas con diferencia común [matemáticas] 15 [/ matemáticas] y que contienen [matemáticas] 7 [/ matemáticas].

Ahora suponga que [matemáticas] p [/ matemáticas], [matemáticas] q [/ matemáticas] son primos distintos. Estamos buscando una [matemática] N [/ matemática] para la cual

[matemáticas] N \ equiv \ frac {p-1} {2} \ pmod {p} [/ matemáticas] y [matemáticas] N \ equiv \ frac {q-1} {2} \ pmod {q} \ ldots ( 1) [/ matemáticas]

CRT asegura que esto sea posible, y además dice que todas las soluciones se obtienen de una solución específica al sumar o restar múltiplos de [math] pq [/ math]. Entonces, el conjunto de todas las soluciones forma una progresión aritmética con diferencia común [math] pq [/ math] y que contiene [math] N [/ math], para algún número entero [math] N [/ math].

Podemos suponer que tanto [math] p [/ math] como [math] q [/ math] son impares . Queremos [math] n_1 [/ math] y [math] n_2 [/ math] de modo que

[matemáticas] pn_1 + \ frac {p-1} {2} = qn_2 + \ frac {q-1} {2} [/ matemáticas].

Así [matemáticas] q \ mid \ big (pn_1 + \ frac {p-1} {2} – \ frac {q-1} {2} \ big) = \ big (pn_1 + \ frac {pq} {2} \ big )[/matemáticas],

y así [matemáticas] 2q \ mid (2pn_1 + p) = p (2n_1 + 1) [/ matemáticas].

Por lo tanto, [math] q \ mid (2n_1 + 1) [/ math], y podemos elegir [math] n_1 = \ frac {q-1} {2} [/ math].

Esto da [matemáticas] N = p \ frac {q-1} {2} + \ frac {p-1} {2} = \ frac {pq-1} {2} \ pmod {pq} [/ math], es decir, [math] N [/ math] tiene la forma [math] pqn + \ frac {pq-1} {2} [/ math]. [matemáticas] \ blacksquare [/ matemáticas]

Answer 2

Usemos el teorema del resto chino.

Si [matemáticas] a [/ matemáticas] [matemáticas] \ equiv -1 \ equiv 2 \ pmod {3} [/ matemáticas] y [matemáticas] a [/ matemáticas] [matemáticas] \ equiv -2 \ equiv 3 \ pmod { 5} [/ math], entonces el CRT nos dice que [math] a [/ math] también es equivalente a algún número [math] x [/ math] mod [math] 3 \ times 5 = 15 [/ math]. Podemos calcular el número explícitamente con la identidad de Bezout. Debido a que 3 y 5 son números coprimos, hay dos enteros [matemática] m_1 [/ matemática] y [matemática] m_2 [/ matemática] tal que [matemática] 3m_1 + 5m_2 = 1 [/ matemática]. Entonces [matemáticas] x = 2 \ cdot 5 \ cdot m_2 + 3 \ cdot 3 \ cdot m_1 [/ math].

Encontrar los valores [matemática] m_1 = -3 [/ matemática] y [matemática] m_2 = 2 [/ matemática] nos da [matemática] x = 20 + (-27) = -7 [/ matemática], como descubriste. Es decir, si [matemática] a = 3n_1 + 1 [/ matemática] y [matemática] a = 5n_2 +2 [/ matemática], entonces [matemática] a = 15n_3 + 7 [/ matemática].

Por lo tanto, los valores especiales [matemática] \ frac {p-1} {2} [/ matemática] y [matemática] \ frac {q-1} {2} [/ matemática] no son necesarios para que esta relación funcione. Dados dos primos [matemática] p [/ matemática] y [matemática] q [/ matemática], los números de la forma [matemática] pn_1 + j [/ matemática] y [matemática] qn_2 + k [/ matemática] también de la forma [math] pqn_3 + x [/ math]. Podemos calcular [matemáticas] x [/ matemáticas] al encontrar primero [matemáticas] pm_1 + qm_2 = 1 [/ matemáticas]; luego [math] x = -jqm_2 -kpm_1 [/ math] (y luego ajuste agregando o quitando [math] pq [/ math], si lo desea).

Answer 3