Diferencia entre revisiones de «Aritmética modular»

Sean a,b,c∈ℤ, n∈ℕ y (c,n)=d. Entonces ac≡bc (mod n) si y sólo si a≡b (mod n/dnd).

|1=Se supondrá que ac≡bc (mod n). Por lo tanto, n{{!}}c(a−b). Por propiedad de [[divisibilidad]], n/dnd{{!}}(c/d)cd(a−b). Note que n/dnd,c/d∈ℤcd∈ℤ, pues (c,n)=d implica (c/dcd,n/dnd)=1. De esto último, se consigue que n/d∤c/dnd∤cd. Por lo tanto, n/dnd{{!}}(a−b). Entonces a≡b (mod n/dnd).

Nuestra hipótesis es a≡b (mod n/dnd). Por lo tanto, n/dnd{{!}}(a−b). Por propiedad de divisibilidad, n{{!}}d(a−b). Adicionalmente, ya que (c,n)=d entonces d{{!}}c. Esto implica que d(a−b){{!}}c(a−b). Por transitividad de la divisibilidad, n{{!}}c(a−b). Por lo tanto, ac≡bc (mod n).