Matematica Discreta

NOTAS
´
Algebra
I-Matem´atica Discreta I
N. Patricia Kisbye y Roberto J. Miatello
Fa.M.A.F
Facultad de Matem´atica, Astronom´ıa y F´ısica
Universidad Nacional de C´ordoba

´
Indice
general
´
Parte 1. Notas de Algebra
I - Matem´atica Discreta I

5

Introducci´on

7

Cap´ıtulo 1. Los n´umeros naturales

9

1. Introducci´on

9

2. Los n´umeros reales

11

3. El Principio de Inducci´on

17

4.Definiciones recursivas

23

Cap´ıtulo 2. Conteo

33

1. T´ecnicas de Conteo

33

2. F´ormula del binomio

51

Cap´ıtulo 3. Divisibilidad

55

1. Los n´umeros enteros

55

2. Algoritmo de la divisi´on

57

3. Desarrollos en base b, (b ≥ 2)

59

4. M´aximo com´un divisor

60

5. N´umeros primos

64

Cap´ıtulo 4. Congruencias

71

1. La relaci´on de congruencia

71

2. Ecuaciones en congruencias

74

3.Sistemas de ecuaciones en congruencias

79

Cap´ıtulo 5. Grafos

87

1. Introducci´on

87

2. Algoritmo greedy

100

´ DE EJERCICIOS
Parte 2. GUIA

103
3

Parte 1

´
Notas de Algebra
I - Matem´atica Discreta I

Introducci´on
´
Estas notas tienen la intenci´on de ofrecer al estudiante un curso introductorio de Algebra.
Las mismas han sido utilizadas en los u´ ltimos a˜nos para el dictado delas materias de primer
´
a˜no Algebra
I y Matem´atica Discreta I de la Facultad de Matem´atica, Astronom´ıa y F´ısica de la
UNC. Comprenden los siguientes temas: axiomas de los n´umeros reales, los n´umeros naturales
y el Principio de Inducci´on, t´ecnicas de conteo, los n´umeros enteros, divisibilidad, n´umeros
primos, congruencias y grafos.
La gu´ıa de ejercicios que se encuentra en la segundaparte ha sido elaborada en base a la
recopilaci´on de los trabajos pr´acticos de los u´ ltimos a˜nos.
Esperamos que estas notas les sean u´ tiles y accesibles para entender las primeras herra´
mientas del Algebra
y al mismo tiempo agradecemos sus sugerencias y comentarios a fin de
mejorarlas.
Los autores.

7

CAP´ITULO 1

´
Los numeros
naturales
1. Introducci´on
En esta secci´on y la siguientedaremos una breve introducci o´ n a los n´umeros reales, desde
un punto de vista intuitivo y luego formalmente a partir de los axiomas de n´umeros reales.
Acordamos denotar con N, Z y Q al conjunto de los n´umeros naturales, enteros y racionales
respectivamente, y con R al conjunto de los n´umeros reales. En las secciones §3 y §4 daremos

la definici´on y propiedades de conjunto inductivo eintroduciremos el conjunto N de los n´umeros
naturales.
Al igual que los n´umeros naturales y enteros, los n´umeros racionales se representan en la
recta de la manera usual. Por ejemplo:

-1 -1/2

0

2/3 1

3/2

2

5/2 . . . . . .

Si bien existen infinitos n´umeros racionales, los puntos correspondientes a los n´umeros ra√
cionales no llenan la recta. Como es bien sabido, un segmento de longitud 2 no secorresponde
con ning´un n´umero racional, ya que los n´umeros racionales no bastan para medir la diagonal de
un cuadrado cuyo lado sea de longitud igual a 1. La introducci´on de los n´umeros irracionales
remedia este problema, de tal modo que los n´umeros racionales y los irracionales conforman
el sistema de los n´umeros reales, con lo cual se tiene una correspondencia biun´ıvoca entre los
n´umerosreales y los puntos de la recta.
Si nos referimos a la representaci´on de los n´umeros reales en el sistema decimal, los n´umeros racionales se pueden caracterizar por ser aquellos que admiten una expresi´on decimal peri´odica, por ejemplo:
35
7
=
= 3,5
2
10
4
= 1,333 . . . ,
3
0, 234234234 . . . = 234 × (0,001001001 . . . ) = 234 ×
9

1
234
=
999
999

´
1. LOS NUMEROS
NATURALES

10

Lasexpresiones decimales no peri´odicas, en cambio, se corresponden con los n´umeros irracionales. Por ejemplo, el n´umero
α = 2, 101001000100001000001 . . .
no posee ning´un per´ıodo, luego es irracional. Es f´acil construir una infinidad de n´umeros irracionales, por ejemplo, basta tomar α + q donde q es cualquier n´umero racional. As´ıvemos que
2, 201001000100001000001 . . . ,

2, 401001000100001000001...