Matemática Discreta 1
Divisibilidad

Divisibilidad

Dados dos enteros xx e yy decimos que yy dvidide a xx (y∣xy \mid x),
si x=y⋅q,  q∈Zx = y \cdot q, \;q \in \mathbb{Z}.

Si xx es divisible por yy, entonces xx es un múltiplo de yy.

Propiedades básicas divide a

Sean a,b,c∈Za, b, c \in \mathbb{Z}, entonces:

1) 1∣a1 \mid a

a=1⋅aa=a⋅1−a=a⋅(−1)a = 1 \cdot a \\ a = a \cdot 1 \\ -a = a \cdot (-1)

2) a∣0a \mid 0 y solo 0∣00 \mid 0

0=a⋅00∣a  ⟹  a=0⋅q=00 = a \cdot 0 \\ 0 \mid a \implies a = 0 \cdot q = 0

3) Si a∣b  ⟹  a∣bca \mid b \implies a \mid bc

a∣b  ⟹  b=a⋅qbc=a⋅qc  ⟹  a∣bca \mid b \implies b = a \cdot q \\ bc = a \cdot qc \implies a \mid bc

4) Si a∣ba \mid b y a∣(b+c)a \mid (b + c)

a∣b∧a∣c  ⟹  b=a⋅q∧c=a⋅q′b+c=a⋅q+a⋅q′=a(q+q′)  ⟹  a∣(b+c)a \mid b \land a \mid c \implies b = a \cdot q \land c = a \cdot q' \\ b + c = a \cdot q + a \cdot q' = a(q + q') \implies a \mid (b + c)

5) Si a∣ba \mid b y a∣c  ⟹  a∣(rb+sc)∀r,s∈Za \mid c \implies a \mid (rb + sc) \forall r, s \in \mathbb{Z}

a∣b∧a∣c  ⟹  b=a⋅q∧c=a⋅q′rb+sc=a⋅rq+a⋅sq′=a(rq+sq′)  ⟹  a∣(rb+sc)a \mid b \land a \mid c \implies b = a \cdot q \land c = a \cdot q' \\ rb + sc = a \cdot rq + a \cdot sq' = a(rq + sq') \implies a \mid (rb + sc)

6) Si a∣b+ca \mid b + c y a∣c  ⟹  a∣ba \mid c \implies a \mid b

a∣b+c∧a∣c  ⟹  b+c=a⋅q∧c=a⋅q′b=(b+c)−c=a⋅q−a⋅q′=a(q−q′)  ⟹  a∣ba \mid b + c \land a \mid c \implies b + c = a \cdot q \land c = a \cdot q' \\ b = (b + c) - c = a \cdot q - a \cdot q' = a(q - q') \implies a \mid b

7) Si a∣b  ⟹  ±a∣±ba \mid b \implies \pm a \mid \pm b

a∣b  ⟹  b=a⋅q  ⟹  −b=a⋅(−q)  ⟹  a∣−b−b=−a⋅q  ⟹  −a∣−bb=−a⋅(−q)  ⟹  −a∣ba \mid b \implies b = a \cdot q \implies \\ -b = a \cdot (-q) \implies a \mid -b \\ -b = -a \cdot q \implies -a \mid -b \\ b = -a \cdot (-q) \implies -a \mid b \\

D1) a∣aa \mid a (Reflexividad)

D2) a∣b∧b∣a  ⟹  a=ba \mid b \land b \mid a \implies a = b (Antisimetría)

D3) a∣b∧b∣c  ⟹  a∣ca \mid b \land b \mid c \implies a \mid c (Transitividad)

Algoritmo de la división

Sean a∈Za \in \mathbb{Z} y b∈Nb \in \mathbb{N} existen enteros únicos qq y rr tales que:

a=b⋅q+r,  0≤r<ba = b \cdot q + r , \;0 \leq r < b

Donde qq es el cociente y rr es el resto de dividir bb por aa.

Ejemplo:

a=13,  b=513=5⋅2+3a = 13, \;b = 5 \\ 13 = 5 \cdot 2 + 3

Ejercicios resueltos - Algoritmo de la división

1.

Dado m∈Nm \in \mathbb{N} hallar los restos posibles de m2m^2 y m3m^3 en la división por 33.

El primer paso es dividir mm por 33 usando el algoritmo:

m=3⋅q+r,  0≤r<3,r∈{0,1,2}m = 3 \cdot q + r, \;0 \leq r < 3, r \in \{0, 1, 2\}

Para m2m^2:

m2=(3⋅q+r)2m^2 = (3 \cdot q + r)^2

Ahora expandimos y aplicamos factor común de 33:

3⋅q2+3⋅2qr+r2=3⋅(q2+2qr)+r23 \cdot q^2 + 3 \cdot 2qr + r^2 = 3 \cdot (q^2 + 2qr) + r^2

El resto de dividir m2m^2 por 33 es r2r^2. Ahora podemos calcular los restos posibles de m2m^2

0≤r<3  ⟹  0≤r2<3,  r2∈{0,1}\begin{align*} 0 \leq r < 3 &\implies 0 \leq r^2 < 3, \;r^2 \in \{0, 1\} \\ \end{align*}

Desarrollos en base bb

Todo natural xx se puede expresar como:

x=rn10n+rn−110n−1+…+r110+r0x = r_n 10^n + r_{n-1} 10^{n-1} + \ldots + r_1 10+ r_0

Donde rn≠0r_n \neq 0 y 0≤ri<100 \leq r_i < 10.

xx se representa como (rnrn−1…r1r0)10(r_n r_{n-1} \ldots r_1 r_0)_{10}.

Ejemplo:

Si queremos escribir el número 407407 de la siguiente forma (base 55):

407=rn5n+rn−15n−1+…+r15+r0407 = r_n 5^n + r_{n-1} 5^{n-1} + \ldots + r_1 5 + r_0

Con 0≤ri<50 \leq r_i < 5 lo podemos hacer de forma algorítmica:

Necesitamos dividir el número original y los sucesivos cocientes por 55:

407=5⋅81+2  (1)81=5⋅16+1  (2)16=5⋅3+1  (3)3=5⋅0+3  (4)\begin{align*} 407 &= 5 \cdot 81 + 2 \; (1) \\ 81 &= 5 \cdot 16 + 1 \; (2) \\ 16 &= 5 \cdot 3 + 1 \; (3) \\ 3 &= 5 \cdot 0 + 3 \; (4) \end{align*}

Y ahora reemplazamos los valores de los cocientes:

407=5⋅81+2  (1)=5⋅(5⋅16+1)+2  (2)=52⋅16+5+2  =52⋅(5⋅3+1)+5+2  (3)=53⋅3+52⋅1+5⋅1+2  \begin{align*} 407 &= 5 \cdot 81 + 2 \; (1) \\ &= 5 \cdot (5 \cdot 16 + 1) + 2 \; (2) \\ &= 5^2 \cdot 16 + 5 + 2 \; \\ &= 5^2 \cdot (5 \cdot 3 + 1) + 5 + 2 \; (3) \\ &= 5^3 \cdot 3 + 5^2 \cdot 1 + 5 \cdot 1 + 2 \; \\ \end{align*}

Por lo que el número 407407 en base 55 sería (3112)5(3112)_5.

Conversiones de base

Podemos calcular la conversión de un número de base bb a base 1010.

Ejemeplo:

Convertir (1304)6(1304)_6 a base 1010:

(1304)6=1⋅63+3⋅62+0⋅61+4⋅60=1⋅216+3⋅36+0⋅6+4⋅1=216+108+0+4=328\begin{align*} (1304)_6 &= 1 \cdot 6^3 + 3 \cdot 6^2 + 0 \cdot 6^1 + 4 \cdot 6^0 \\ &= 1 \cdot 216 + 3 \cdot 36 + 0 \cdot 6 + 4 \cdot 1 \\ &= 216 + 108 + 0 + 4 \\ &= 328 \end{align*}

Si quisieramos convertir (1304)6(1304)_6 a otra base (por ejemplo, 55), primero lo convertimos a base 1010 y luego a la base deseada.

Ejercicios resueltos - Desarrollos en base bb y conversiones de base

1.

Convertir (1011)2(1011)_2 a base 1010:

(1011)2=1⋅23+0⋅22+1⋅21+1⋅20=8+0+2+1=11(1011)_2 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = 11

2.

Convertir (B38)16(B38)_{16} a base 88:

Para resolver este ejercicio, primero necesitamos saber que los números en base 1616 son 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Sabiendo esto, necesitamos convertirlo a base 1010 y luego a base 88.

(B38)16=11⋅162+3⋅161+8⋅160=2816+48+8=2872(B38)_{16} = 11 \cdot 16^2 + 3 \cdot 16^1 + 8 \cdot 16^0 = 2816 + 48 + 8 = 2872

Ahora convertimos 28722872 a base 88:

2872=8⋅359+0  (1)359=8⋅44+7  (2)44=8⋅5+4  (3)5=8⋅0+5  (4)\begin{align*} 2872 &= 8 \cdot 359 + 0 \; (1) \\ 359 &= 8 \cdot 44 + 7 \; (2) \\ 44 &= 8 \cdot 5 + 4 \; (3) \\ 5 &= 8 \cdot 0 + 5 \; (4) \end{align*}

Podemos decir que (B38)16=(5470)8(B38)_{16} = (5470)_8.

Máximo común divisor (mcd)

Sean a,b∈Za, b \in \mathbb{Z} alguno de ellos no nulo, denotamos mcd(a,b)mcd(a, b) o (a,b)(a, b) al máximo común divisor entre aa y bb.

Propiedades del mcd

1) mcd(a,b)=mcd(b,a)=mcd(±a,±b)mcd(a, b) = mcd(b, a) = mcd(\pm a, \pm b)

2) a>0,  mcd(a,0)=a,  mcd(a,a)=aa > 0,\;mcd(a,0) = a,\;mcd(a, a) = a

3) mcd(1,b)=1mcd(1, b) = 1

4) mcd(a,b)=mcd(a,b−a)mcd(a, b) = mcd(a, b - a)

Algoritmo de Euclides

Sean a,b∈Za, b \in \mathbb{Z}, con b≠0b \neq 0, entonces:
a=bq+r→mcd(a,b)=mcd(b,r)a = bq + r \rightarrow mcd(a, b) = mcd(b, r)

Ejemplo:

Encontrar el mcd(174,72)mcd(174, 72)

174=72⋅2+30  ⟹  mcd(174,72)=mcd(72,30)72=30⋅2+12  ⟹  mcd(72,30)=mcd(30,12)30=12⋅2+6  ⟹  mcd(30,12)=mcd(12,6)12=6⋅2+0  ⟹  mcd(12,6)=mcd(6,0)=6174 = 72 \cdot 2 + 30 \implies mcd(174, 72) = mcd(72, 30) \\ 72 = 30 \cdot 2 + 12 \implies mcd(72, 30) = mcd(30, 12) \\ 30 = 12 \cdot 2 + 6 \implies mcd(30, 12) = mcd(12, 6) \\ 12 = 6 \cdot 2 + 0 \implies mcd(12, 6) = mcd(6, 0) = 6

Por lo tanto, mcd(174,72)=6mcd(174, 72) = 6.

Notemos que:

mcd(72,174)=(72,174−72)=(72,102)mcd(72,102)=(72,102−72)=(72,30)mcd(30,72)=(30,72−30)=(30,42)mcd(30,42)=(30,42−30)=(30,12)mcd(12,30)=(12,30−12)=(12,18)mcd(12,18)=(12,18−12)=(12,6)mcd(6,12)=(6,12−6)=(6,6)=6\begin{align*} mcd(72, 174) = (72, 174 - 72) = (72, 102) \\ mcd(72, 102) = (72, 102 - 72) = (72, 30) \\ mcd(30, 72) = (30, 72 - 30) = (30, 42) \\ mcd(30, 42) = (30, 42 - 30) = (30, 12) \\ mcd(12, 30) = (12, 30 - 12) = (12, 18) \\ mcd(12, 18) = (12, 18 - 12) = (12, 6) \\ mcd(6, 12) = (6, 12 - 6) = (6, 6) = 6 \end{align*}

Tenemos la propiedad de que mcd(a,b)=mcd(a,b−a)mcd(a, b) = mcd(a, b - a)

Ejemplo 2:

Encontrar el mcd(174,72)mcd(174, 72) y escribir d=s⋅174+t⋅72d = s \cdot 174 + t \cdot 72

174=72⋅2+30  ⟹  30=174−72⋅2  (1)72=30⋅2+12  ⟹  12=72−30⋅2  (2)30=12⋅2+6  ⟹  6=30−12⋅2  (3)12=6⋅2+0\begin{align*} 174 = 72 \cdot 2 + 30 &\implies 30 = 174 - 72 \cdot 2 \; (1) \\ 72 = 30 \cdot 2 + 12 &\implies 12 = 72 - 30 \cdot 2 \; (2) \\ 30 = 12 \cdot 2 + 6 &\implies 6 = 30 - 12 \cdot 2 \; (3) \\ 12 = 6 \cdot 2 + 0 \end{align*}

Sabemos que mcd(174,72)=6mcd(174, 72) = 6, por lo que podemos reemplazar los valores de los restos:

6=30−12⋅2  (3)=1⋅30−2⋅(72−30⋅2)  (2)=1⋅30+(−2)⋅72+4⋅30=5⋅30+(−2)⋅72=5⋅(174−72⋅2)+(−2)⋅72=5⋅174+(−10)⋅72+(−2)⋅72=5⋅174+(−12)⋅72\begin{align*} 6 &= 30 - 12 \cdot 2 \; (3) \\ &= 1 \cdot 30 - 2 \cdot (72 - 30 \cdot 2) \; (2) \\ &= 1 \cdot 30 + (-2) \cdot 72 + 4 \cdot 30 \\ &= 5 \cdot 30 + (-2) \cdot 72 \\ &= 5 \cdot (174 - 72 \cdot 2) + (-2) \cdot 72 \\ &= 5 \cdot 174 + (-10) \cdot 72 + (-2) \cdot 72 \\ &= 5 \cdot 174 + (-12) \cdot 72 \end{align*}

Por lo que d=6,  s=5,  t=−12d = 6, \;s = 5, \;t = -12.

Mínimo común múltiplo (mcm)

Si a,b∈Za, b \in \mathbb{Z}, alguno de ellos no nulo, denotamos mcm(a,b)mcm(a, b) al mínimo común múltiplo entre aa y bb.

La forma de calcularlo es:

mcm(a,b)=∣ab∣mcd(a,b)mcm(a, b) = \frac{|ab|}{mcd(a, b)}

Si aa y bb son naturales coprimos, entonces mcd(a,b)=1mcd(a, b) = 1 y mcm(a,b)=abmcm(a, b) = ab.

Factorización prima

Teorema Fundamental de la Aritmética

Todo entero n>1n > 1 puede ser escrito de manera única como producto de primos (salvo el orden de los factores).

Propiedades de la factorización prima

Sean a∈Za \in \mathbb{Z} y pp primo:

1) p∤  a  ⟹  mcd(a,p)=1p \not{\mid} \; a \implies mcd(a, p) = 1

2) p,p′p, p' primos y p∣p′  ⟹  p=p′p \mid p' \implies p = p'

3) n>0n > 0 no primo   ⟹  ∃m>0\implies \exists m > 0 tal que m∣n,  m≤nm \mid n, \; m \leq \sqrt{n}

Criterio de la raíz

Sea n≥2n \geq 2, si para todo mm tal que 1<m≤n1 < m \leq \sqrt{n}, se cumple que m∤  nm \not{\mid} \; n, entonces nn es primo.

Ejemplo:

Podemos verificar si 467467 es primo o no:

467≈21.62≤m≤21  ⟹  3,5,7,11,13,17,19∤  467\begin{align*} \sqrt{467} &\approx 21.6 \\ 2 \leq m \leq 21 &\implies 3, 5, 7, 11, 13, 17, 19 \not{\mid} \; 467 \end{align*}

Comprobamos que los números no dividen a 467467, por lo que 467467 es primo.

Teorema - Numeros pares

Si m,n∈Zm, n \in \mathbb{Z}, tales que m≥2∧n≥2  ⟹  m2≠2n2m \geq 2 \land n \geq 2 \implies m^2 \neq 2n^2.

No puede ocurrir que m2=2n2m^2 = 2n^2 porque si ocurriera ese número tendría en la descomposición prima por un lado 22 a una potencia impar y por otro lado 22 a una potencia par.

Con esto podemos probar que 2\sqrt{2} es irracional. Para ello suponemos que 2\sqrt{2} es racional:

2=mn\sqrt{2} = \frac{m}{n}

Entendemos esta fracción como una fracción irreducible, sin embargo esto no se cumple:

2=m2n2  ⟹  2n2=m22 = \frac{m^2}{n^2} \implies 2n^2 = m^2

m2=2n2m^2 = 2n^2, por lo que mm es par. Sabiendo que mm es par, lo reescribimos como m=2km = 2k:

4k2=2n2  ⟹  2k2=n24k^2 = 2n^2 \implies 2k^2 = n^2

Ambos números son pares, la fracción sigue siendo reducible.

Por lo que m2=2n2m^2 = 2n^2 es un absurdo y 2\sqrt{2} es irracional.

ConteoAritmética Modular