Sea [math] n – 1 = kq + r [/ math], donde [math] q [/ math] es un entero no negativo y [math] r \ in \ left \ lbrace 0, 1, \ cdots, k – 1 \ right \ rbrace [/ math]. Cuando [matemática] n – 1 [/ matemática] se divide por [matemática] k [/ matemática], entonces [matemática] q [/ matemática] es el cociente y [matemática] r [/ matemática] es el resto. (Vea el lema al final si desea una prueba más formal de la existencia de [math] q [/ math] y [math] r [/ math].) Luego:
[matemáticas] \ lceil \ frac {n} {k} \ rceil = \ lceil \ frac {kq + r + 1} {k} \ rceil [/ math]
[matemáticas] = \ lceil q + \ frac {r + 1} {k} \ rceil [/ math]
Como [math] 0 <\ frac {r + 1} {k} \ leq 1 [/ math], y dado que [math] q [/ math] es un entero, se deduce que [math] \ lceil q + \ frac {r + 1} {k} \ rceil = q + 1 [/ matemática], como [matemática] 0 <\ frac {r + 1} {k} <1 [/ matemática], en cuyo caso [matemática] q + \ frac {r + 1} {k} [/ math] redondea hasta [math] q + 1 [/ math], que es el siguiente entero más alto, o bien [math] \ frac {r + 1} {k } = 1 [/ math], en cuyo caso [math] q + \ frac {r + 1} {k} [/ math] ya es el entero [math] q + 1 [/ math].
- ¿Por qué la función de estimación primaria de ejemplo cuenta menos los compuestos?
- ¿Cómo demostró Euler la conexión entre los números primos y la función Zeta de Riemann?
- Cómo comenzar a aprender teoría de números
- ¿Cuál es el algoritmo más eficiente para encontrar el período de Pisano para un entero dado (incluso para enteros grandes)?
- ¿Debería estudiar cálculo, matemática, teoría de números, álgebra universitaria, trigonometría, análisis y prueba matemática por completo al mismo tiempo o centrarme en algunos de ellos?
También,
[matemáticas] \ lfloor \ frac {n-1} {k} \ rfloor + 1 = \ lfloor \ frac {kq + r} {k} \ rfloor + 1 [/ math]
[matemáticas] = \ lfloor q + \ frac {r} {k} \ rfloor + 1 [/ math]
pero, dado que [math] 0 \ leq \ frac {r} {k} <1, \ lfloor q + \ frac {r} {k} \ rfloor [/ math] se redondea al siguiente entero inferior, que es [math ] q [/ math], entonces [math] \ lfloor q + \ frac {r} {k} \ rfloor + 1 = q + 1 [/ math].
Como [math] \ lceil \ frac {n} {k} \ rceil [/ math] y [math] \ lfloor \ frac {n-1} {k} \ rfloor + 1 [/ math] ambos son iguales [math] q + 1 [/ matemáticas], son iguales. QED
Lema Para todos los enteros positivos [matemática] n [/ matemática] y [matemática] k [/ matemática], hay un entero no negativo [matemática] q [/ matemática] y una [matemática] r \ in \ left \ lbrace 0, 1 , \ cdots, k – 1 \ right \ rbrace [/ math], de modo que [math] n – 1 = kq + r [/ math].
Prueba. Supongamos que esto no es así. Entonces, hay una [matemática] n [/ matemática] y una [matemática] k [/ matemática], de modo que [matemática] n – 1 [/ matemática] no se puede expresar como [matemática] kq + r [/ matemática] . Además, para cualquier [matemática] k [/ matemática], deje que [matemática] n_0 [/ matemática] sea el menor (entero positivo) [matemático] n [/ matemático] tal que [matemático] n – 1 [/ matemático] no se puede expresar como [math] kq + r [/ math]. Si [math] 1 \ leq n_0 \ leq k [/ math], entonces [math] n_0 – 1 = kq + r [/ math] con [math] q = 0 [/ math] y [math] r = n_0 – 1 [/ matemáticas]. De lo contrario, [math] n_0 – k [/ math] es un entero positivo y, por lo tanto, [math] n_0 – k – 1 [/ math] se puede expresar como [math] kq + r [/ math], ya que si fuera no, entonces [matemática] n_0 [/ matemática] no fue la más baja [matemática] n [/ matemática] de modo que [matemática] n – 1 [/ matemática] no se puede expresar como [matemática] kq + r [/ matemática]. Pero entonces, [matemática] n_0 – 1 = k (q + 1) + r [/ matemática], y [matemática] q + 1 [/ matemática] es un entero no negativo, entonces [matemática] n_0 – 1 [/ matemática] es, de hecho, expresable como [math] kq + r [/ math]. Por lo tanto, existe una contradicción que invalida la suposición de que el lema es falso, por lo que el lema debe ser verdadero.