Proposiciones y resoluciones 1 Flashcards
Proposición 1.1.2. Sean b ∈ N, con b ≥ 2 y x ∈ N, entonces existen a0,a1,…,an enteros tales que podemos escribir a x en base b como
Sean b ∈ N, con b ≥ 2 y x ∈ N, entonces existen a0,a1,…,an enteros tales que podemos escribir a x en base b como
Demostración por inducción en x, aplicamos hipótesis inductiva en q y despejamos.
Proposición 1.2.6. Dados a,b ∈ Z con a,b ≠ 0 entonces mcd(a,b)…
Proposición 1.2.6. Dados a,b ∈ Z con a,b ≠ 0 entonces:
1. mcd(a,b) = mcd(b,a − bx) para todo x ∈ Z.
2. En particular, si r es el resto de dividir a entre b, se tiene que mcd(a,b) = mcd(b,r).
Demostración.
Por la propiedad (3) de los ejemplos anteriores, basta con probarlo para a y b positivos.
* Llamemos d = mcd(a,b) y d’ = mcd(b,a−bx). Como d | a y d | b, por lo visto en las propiedades 1.1.5, tenemos que d divide a cualquier combinación lineal entera de a y b, en particular, d | a − bx. Por lo tanto d ∈ Div(b) ∩ Div(a − bx), y entonces d ≤ máx(Div(b) ∩ Div(a − bx)) = d’.
* Por otro lado, d’ | b y d’ | a−bx; utilizando el mismo razonamiento tenemos que d’ divide a (a−bx)+x(b) = a. Así que d’ ∈ Div(a) ∩ Div(b) y tenemos que d’ ≤ máxDiv(a) ∩ Div(b) = d.
Proposición 1.2.15 relación MCM y MCD
Proposición 1.2.15. Dados a,b ∈ Z no nulos, se cumple que
mcm(a,b) = |ab| / mcd(a,b) .
Prueba de irracionalidad y proposición
Algoritmo de euclides extendido
Proposición 1.6.1. Sean a > 1, b > 1 enteros, primos entre sí…
Proposición 1.6.1. Sean a > 1, b > 1 enteros, primos entre sí. Entonces no hay enteros x, y no negativos con ax + by = ab − a − b.
Proposición 1.6.2. Sean a y b enteros positivos tales que mcd(a,b) = 1….
Proposición 1.6.2. Sean a y b enteros positivos tales que mcd(a,b) = 1. Si n ≥ ab−a−b+1, entonces existen enteros no negativos x, y tales que ax + by = n
Demostración. Por el Teorema 1.5.3, como mcd(a,b) = 1, existe un par de enteros (x0,y0) que cumplen
ax0 + by0 = n ≥ ab − a − b + 1, que nos permite expresar todas las soluciones en la forma
x = x0 + bk, y = y0 − ak, k ∈ Z.
Usando el algoritmo de división, podemos dividir y0 por a y escribir y0 = at + y1, con 0 ≤ y1 ≤ a − 1, para algún entero t. Probaremos que x1 = x0 + bt es no negativo. Si x1 ≤ −1, entonces, como y1 ≤ a − 1,
n = ax0 + by0 = a(x1 − bt) + b(y1 + at) = ax1 + by1 ≤ a(−1) + b(a − 1) = ab − a − b, que contradice la hipótesis n ≥ ab−a−b+1.
Concluimos que (x1,y1) es una solución de enteros no negativos
Proposición 1.7.5. Sean a,b enteros positivos con descomposición en factores primos…
Proposición 1.7.5. Sean a,b enteros positivos con descomposición en factores primos
a = 2^a2.3^a3.5^a5 ··· y b = 2^b2.3^b3.5^b5 ··· ,
entonces:
1. a | b si y sólo si ap ≤ bp para todo p.
2. mcd(a,b) = 2^d2.3^d3.5^d5 ··· siendo dp = mín{ap,bp} para todo primo p.
3. mcm(a,b) = 2^m2.3^m3.5^m5 ··· siendo mp = máx{ap,bp} para todo primo p
Proposición 2.2.3. 1. La congruencia módulo n es una relación de equivalencia…
Proposición 2.2.3.
1. La congruencia módulo n es una relación de equivalencia (reflexiva, simétrica y transitiva).
2. a ≡ b (mód n) si y sólo si a ≡ b (mód (−n)).
3. a ≡ b (mód n) si y sólo si a y b tienen el mismo resto al dividirlos entre n.
4. Dado n ∈ Z+, y a ∈ Z existe un único r ∈ {0, 1,··· ,n − 1} tal que a ≡ r (mód n) (r es el resto de dividir a entre n).
Proposición 2.2.4. [Propiedades Cancelativas] Sea a,b,c,n ∈ Z con c ≠ 0
Proposición 2.3.1. (propiedades de las congruencias) Sean a,b,c,n,m ∈ Z
Proposición 2.3.1. Sean a,b,c,n,m ∈ Z.
1. a ≡ b (mód n) y c ≡ d (mód n) ⇒ a + c ≡ b + d (mód n) y a.c ≡ b.d (mód n).
2. b ≡ c (mód n) ⇒ a + b ≡ a + c (mód n).
3. a ≡ b (mód n) y m|n ⇒ a ≡ b (mód m).
4. a ≡ b (mód m) ⇒ n.a ≡ n.b (mód m).
5. a ≡ b (mód m) y n ∈ N ⇒ a^n ≡ b^n (mód m).
Proposición 2.3.2. Si los dígitos de a son a = ak ···a1a0. Entonces 3 | a
Proposición 2.3.2. Si los dígitos de a son a = ak ···a1a0. Entonces 3 | a si y sólo si 3 | a0 + a1 + ··· + ak.
Demostración. Tenemos que a = ak10k + ···a110 + a0. Tenemos que 3 | a si y sólo si a ≡ 0 (mód 3); es decir, si y sólo si ak10k + ··· + a110 + a0 ≡ 0 (mód 3).
Ahora 10 ≡ 1 (mód 3), y entonces (por la última propiedad de la proposición anterior) 10i ≡ 1i (mód 3) para todo i ∈ N. Así que 10i ≡ 1 (mód 3) y por lo tanto para todo i = 0,··· ,k tenemos que ai10i ≡ ai (mód 3) (por la propiedad (4)); y sumando, utilizando la propiedad (1) obtenemos que a = ak10k + ··· + a110 + a0 ≡ ak + ··· + a1 + a0 (mód 3).
Entonces (por la transitividad de la congruencia) a ≡ 0 (mód 3) ⇔ ak +···+a1 +a0 ≡ 0 (mód 3); es decir 3 divide a a, si y sólo si 3 divide a la suma de sus dígitos
Observar que en la última proposición, lo único que utilizamos (además de las propiedades de congruencia) es que 10 ≡ 1 (mód 3). Como también 10 ≡ 1 (mód 9), de forma análoga se prueba el siguiente criterio de divisibilidad entre 9:
Proposición 2.3.3. Si los dígitos de a son a = ak ···a1a0. Entonces 9 | a si y sólo si 9 | a0 + a1 + ··· + ak.
