El conjunt dels nombres naturals $\mathbb{N}$ és suficient per comptar i ordenar, però presenta una limitació fonamental: la subtracció no és una operació interna. Per exemple, l'equació $x + 5 = 2$ no té solució a $\mathbb{N}$. Per resoldre aquesta deficiència, construïm el conjunt dels **nombres enters** $\mathbb{Z}$.
## 2. Construcció del Conjunt dels Nombres Enters
### 2.1 Construcció formal
Es construeix a partir del producte cartesià $\mathbb{N} \times \mathbb{N}$. Considerem parells ordenats $(a, b)$ on la idea intuïtiva és que representen la "resta" $a - b$.
Definim una relació d'equivalència $\sim$ sobre $\mathbb{N} \times \mathbb{N}$:
$$(a, b) \sim (c, d) \iff a + d = b + c$$
El conjunt dels nombres enters és el conjunt quocient:
**Exemples de classes d'equivalència:**
- Classe del zero: $[(0,0)] = \{(a,a) \mid a \in \mathbb{N}\}$
- Classe del $-3$: $[(0,3)] = \{(0,3), (1,4), (2,5), \ldots\}$
- Classe del $+2$: $[(2,0)] = \{(2,0), (3,1), (4,2), \ldots\}$
Amb aquestes operacions, $(\mathbb{Z}, +, \cdot)$ té estructura d'**anell commutatiu unitari**.
## 3. Ordre i Valor Absolut
### 3.1 Relació d'ordre
Donats $x = [(a,b)]$ i $y = [(c,d)]$:
$$x \leq y \iff a+d \leq b+c$$
L'ordre és compatible amb les operacions:
- Si $a \leq b$, aleshores $a+c \leq b+c$
- Si $a \leq b$ i $c > 0$, aleshores $ac \leq bc$
- Si $a \leq b$ i $c < 0$, aleshores $ac \geq bc$ (**canvi de signe!**)
### 3.2 Valor absolut
El valor absolut $|x|$ representa la distància al zero:
$$|x| = \begin{cases} x & \text{si } x \geq 0 \\ -x & \text{si } x < 0 \end{cases}$$
Donats $a, b \in \mathbb{Z}$ amb $a \neq 0$, diem que **$a$ divideix $b$**, i ho escrivim $a \mid b$, si existeix $k \in \mathbb{Z}$ tal que $b = a \cdot k$.
En aquest cas: $b$ és **múltiple** de $a$, i $a$ és **divisor** de $b$.
### 4.2 Algorisme de la Divisió Euclidiana
Per a qualsevol parell d'enters $a, b$ amb $b > 0$, existeixen **únics** enters $q$ (quocient) i $r$ (residu) tals que:
$$a = b \cdot q + r \quad \text{on} \quad 0 \leq r < b$$
### 4.3 Criteris de Divisibilitat
| Divisor | Criteri |
|---------|---------|
| **2** | Última xifra parella (0, 2, 4, 6, 8) |
| **3** | Suma de xifres múltiple de 3 |
| **4** | Dues últimes xifres formen múltiple de 4 |
| **5** | Última xifra 0 o 5 |
| **6** | Divisible per 2 i per 3 |
| **9** | Suma de xifres múltiple de 9 |
| **10** | Última xifra 0 |
| **11** | Diferència (xifres senars) - (xifres parells) múltiple de 11 |
**Exemple:** $N = 2376$
- Per 2: ✓ (6 és parell)
- Per 3: $2+3+7+6=18$, múltiple de 3 ✓
- Per 9: $18$ múltiple de 9 ✓
- Per 11: $(2+7)-(3+6) = 9-9 = 0$ ✓
## 5. MCD i mcm
### 5.1 Definicions
- **MCD** (Màxim Comú Divisor): El major enter positiu que divideix tant $a$ com $b$: $\text{mcd}(a, b)$
- **mcm** (mínim comú múltiple): El menor enter positiu múltiple de $a$ i $b$: $\text{mcm}(a, b)$
Dos nombres són **coprimers** (o primers entre si) si $\text{mcd}(a, b) = 1$.
### 5.2 Algorisme d'Euclides
Mètode eficient per calcular el MCD basat en: $\text{mcd}(a, b) = \text{mcd}(b, r)$
**Procediment:**
1. Dividim $a$ entre $b$, obtenim residu $r_1$
2. Si $r_1 = 0$, MCD $= b$
3. Si no, dividim $b$ entre $r_1$, obtenim $r_2$
4. Repetim fins residu 0
5. L'últim residu no nul és el MCD
- **MCD:** Producte dels factors primers comuns elevats al **menor** exponent
- **mcm:** Producte de tots els factors primers elevats al **major** exponent
1. Llista de nombres de 2 a $N$
2. El primer no marcat (2) és primer; marcar tots els seus múltiples
3. Següent no marcat (3) és primer; marcar múltiples
4. Continuar fins que $p^2 > N$
5. Els no marcats són primers
### 6.5 Teorema d'Euclides
Hi ha **infinits** nombres primers.
**Demostració:** Suposem que només hi ha un nombre finit de primers $p_1, p_2, \ldots, p_n$. Considerem $N = p_1 \cdot p_2 \cdots p_n + 1$. Aquest $N$ no és divisible per cap $p_i$ (deixa residu 1). Per tant, o $N$ és primer, o té un divisor primer no a la llista. Contradicció.
## 7. Congruències Mòdul $n$
### 7.1 Definició
Donats $a, b, n \in \mathbb{Z}$ amb $n \neq 0$, diem que **$a$ és congruent amb $b$ mòdul $n$**:
$$a \equiv b \pmod{n} \iff n \mid (a-b)$$
Equivalentment: $a$ i $b$ deixen el **mateix residu** en dividir-los per $n$.
La congruència mòdul $n$ és una **relació d'equivalència**:
- **Reflexiva:** $a \equiv a \pmod{n}$
- **Simètrica:** Si $a \equiv b$, aleshores $b \equiv a$
- **Transitiva:** Si $a \equiv b$ i $b \equiv c$, aleshores $a \equiv c$
Parteix $\mathbb{Z}$ en $n$ **classes de residus**: $\mathbb{Z}_n = \{[0], [1], \ldots, [n-1]\}$
### 7.3 Aritmètica Modular
Si $a \equiv b \pmod{n}$ i $c \equiv d \pmod{n}$:
1. $a + c \equiv b + d \pmod{n}$
2. $a - c \equiv b - d \pmod{n}$
3. $a \cdot c \equiv b \cdot d \pmod{n}$
4. $a^k \equiv b^k \pmod{n}$ per a $k \in \mathbb{N}$
**Atenció:** La divisió NO sempre és possible!
### 7.4 Invers multiplicatiu
Si $\text{mcd}(a, n) = 1$, existeix un únic $a^{-1}$ tal que:
$$a \cdot a^{-1} \equiv 1 \pmod{n}$$
**Exemple:** Trobar $3^{-1} \pmod{7}$
Busquem $x$ tal que $3x \equiv 1 \pmod{7}$. Provant: $3 \cdot 5 = 15 = 2 \cdot 7 + 1$, per tant $3^{-1} \equiv 5 \pmod{7}$.
## 8. Aplicacions
### 8.1 Criptografia (RSA)
El criptosistema RSA es basa en:
- La dificultat de factoritzar nombres grans $n = p \cdot q$
- Exponenciació modular per xifrar/desxifrar
### 8.2 Calendari
**Dia de la setmana:** Si avui és dimarts, quin dia serà d'aquí a 100 dies?
$100 = 14 \cdot 7 + 2$, per tant $100 \equiv 2 \pmod{7}$
Serà dijous (dimarts + 2 dies).
### 8.3 Verificació de dígits
- **ISBN:** Utilitza mòdul 10 o 11 per detectar errors
- **Targetes de crèdit:** Algorisme de Luhn (mòdul 10)
- **DNI:** Lletra calculada mòdul 23
## 9. Conclusions
La teoria dels nombres enters, amb la divisibilitat, els nombres primers i les congruències, forma la base de gran part de la matemàtica i té aplicacions sorprenents en tecnologia moderna com la criptografia i la verificació de dades.
Estudia este tema con OPOSGRATIS
Has leído el desarrollo del tema. Para consolidar tu aprendizaje, estudia las flashcards asociadas con repetición espaciada (algoritmo SM-2), realiza simulacros de examen, y practica el supuesto práctico. Todo gratis y sin registro previo.
