Divisibilidade e Algoritmo de Euclides

 

➗ Divisibilidade e Algoritmo de Euclides – A Base da Aritmética

Esses dois conceitos são fundamentais na Teoria dos Números e aparecem em diversas áreas da matemática, especialmente quando lidamos com frações, MDC, criptografia e congruências.

---

✅ Divisibilidade

Dizemos que um número inteiro a é divisível por outro inteiro b (com $b \ne 0$) quando existe um inteiro q tal que:

$$a = b \cdot q$$

🔹 Notação:
Se b divide a, escrevemos:

$$b \mid a$$

Caso contrário:

$$b \nmid a$$

📌 Exemplo:
12 é divisível por 4, pois $12 = 4 \cdot 3$, logo $4 \mid 12$.

---

🔍 Critérios de Divisibilidade (resumidos)

Número	Regra
2	Termina em número par
3	Soma dos dígitos é múltiplo de 3
4	Últimos dois dígitos formam número divisível por 4
5	Termina em 0 ou 5
6	Divisível por 2 e por 3
9	Soma dos dígitos é múltiplo de 9
10	Termina em 0

---

🔁 Máximo Divisor Comum (MDC)

É o maior número que divide dois inteiros ao mesmo tempo.

📌 Exemplo:
MDC(18, 24) = 6

---

⚙️ Algoritmo de Euclides

O Algoritmo de Euclides é uma maneira eficiente e simples de calcular o MDC de dois números.

🧮 Como funciona:

Dado dois números $a$ e $b$ com $a > b$:

1. Divida $a$ por $b$ e obtenha o resto r

2. Substitua: $a \leftarrow b$, $b \leftarrow r$

3. Repita até o resto ser 0. O último divisor diferente de zero será o MDC

---

🔧 Exemplo: MDC(252, 105)

1. $252 \div 105 = 2$ → resto 42

2. $105 \div 42 = 2$ → resto 21

3. $42 \div 21 = 2$ → resto 0

✅ MDC = 21

---

✳️ Propriedades úteis

• Se $a \mid b$ e $a \mid c$, então $a \mid (b + c)$

• $MDC(a, b) \cdot MMC(a, b) = a \cdot b$

---

🔐 Aplicações

• Redução de frações

• Resolução de equações diofantinas

• Criptografia (RSA)

• Cálculo do MMC

• Algoritmos de computador