T3. Nombres enters. Divisibilitat. Nombres primers. Congruències

Desarrollo del tema

# NOMBRES ENTERS. DIVISIBILITAT. NOMBRES PRIMERS. CONGRUÈNCIES

## 1. Introducció

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:

$$\mathbb{Z} = (\mathbb{N} \times \mathbb{N}) / \sim$$

**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\}$

### 2.2 Operacions a $\mathbb{Z}$

**Suma:** $[(a, b)] + [(c, d)] = [(a+c, b+d)]$

**Producte:** $[(a, b)] \cdot [(c, d)] = [(ac+bd, ad+bc)]$

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}$$

**Propietats:** - $|x| \geq 0$ i $|x| = 0 \iff x = 0$ - $|x \cdot y| = |x| \cdot |y|$ - **Desigualtat triangular:** $|x + y| \leq |x| + |y|$

## 4. Divisibilitat

### 4.1 Definició

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

**Exemple:** $\text{mcd}(252, 198)$ - $252 = 1 \cdot 198 + 54$ - $198 = 3 \cdot 54 + 36$ - $54 = 1 \cdot 36 + 18$ - $36 = 2 \cdot 18 + 0$

Per tant, $\text{mcd}(252, 198) = 18$

### 5.3 Identitat de Bézout

Per a dos enters $a$ i $b$, existeixen enters $x$ i $y$ tals que:

$$\text{mcd}(a, b) = ax + by$$

### 5.4 Propietats

1. $\text{mcd}(a, b) \cdot \text{mcm}(a, b) = |a \cdot b|$ 2. **Lema d'Euclides:** Si $n \mid ab$ i $\text{mcd}(n, a) = 1$, aleshores $n \mid b$ 3. $\text{mcd}(ka, kb) = |k| \cdot \text{mcd}(a, b)$

## 6. Nombres Primers

### 6.1 Definició

Un nombre enter $p > 1$ és **primer** si els seus únics divisors positius són 1 i ell mateix.

Un nombre $n > 1$ que no és primer és **compost**.

**Primers:** 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

**Nota:** El 2 és l'únic primer parell.

### 6.2 Teorema Fonamental de l'Aritmètica

Tot nombre enter $n > 1$ es pot expressar de manera **única** (llevat de l'ordre) com a producte de nombres primers:

$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$$

**Exemple:** $360 = 2^3 \cdot 3^2 \cdot 5$

### 6.3 Càlcul de MCD i mcm per factorització

- **MCD:** Producte dels factors primers comuns elevats al **menor** exponent - **mcm:** Producte de tots els factors primers elevats al **major** exponent

**Exemple:** $a = 2^3 \cdot 3^2 \cdot 5$, $b = 2^2 \cdot 3^4 \cdot 7$ - $\text{mcd}(a,b) = 2^2 \cdot 3^2 = 36$ - $\text{mcm}(a,b) = 2^3 \cdot 3^4 \cdot 5 \cdot 7 = 22680$

### 6.4 Criba d'Eratòstenes

Algorisme per trobar tots els primers fins a $N$:

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$.

**Exemple:** $17 \equiv 5 \pmod{12}$ perquè $12 \mid (17-5) = 12$

### 7.2 Propietats

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.