Máximo divisor comum e números primos entre si.

Consideremos os números 28 e 42.

• Os divisores de 28 são 1, 2, 4, 7, 14, 28.
• Os divisores de 42 são 1, 2, 3, 6, 7, 14, 21, 42.

Desta forma, os divisores comuns entre 28 e 42 são 1, 2, 7, 14. O que significa que $m.d.c.(28, 42)=14$.

Nota: Para calcular o $m.d.c. (28, 42)$ também podíamos recorrer ao Algoritmo de Euclides.

Dividamos agora cada um dos números por $14$ ($m.d.c.$):

$$\frac{28}{14}=\frac{2\times14}{14}=2 \text{ porque } 28=2\times 14$$

$$\frac{42}{14}=\frac{3\times14}{14}=3 \text{ porque } 42=3\times 14.$$

Como $2$ e $3$ são números primos, o único divisor comum aos dois é $1$. O que significa que $m.d.c.(2,3)=1$. Logo, $2$ e $3$ são primos entres si.

Mas será que dividindo dois números pelo seu máximo divisor comum obtemos sempre dois números primos entre si?

Antes de respondermos a esta questão, olhemos para o exemplo acima. Tal como verificamos, os divisores comuns a $28$ e $42$ são $1$, $2$, $7$, e $14$. No entanto, ao dividirmos $28$ e $42$ por $14$ $(m.d.c(28, 42))$, porque $14=2\times7$, estamos a impedir que $\frac{28}{2 \times 7}$ e $\frac{42}{2 \times 7}$ sejam, simultaneamente, divisíveis por $2$, por $7$ e por $14$.

Note-se que, como $\frac{28}{14}=\color{red}{2}$ e $\frac{42}{14}=\color{blue}{3}$:

• $\color{red}{2}$ é divisível por $2$, mas $\color{blue}{3}$ não é divisível por $2$.
• $\color{red}{2}$ não é divisível por $7$ e $\color{blue}{3}$ não é divisível por $7$.
• $\color{red}{2}$ não é divisível por $14$ e $\color{blue}{3}$ não é divisível por $14$.

Assim, o único divisor comum entre $\frac{28}{m.d.c(28, 42)}$ e $\frac{42}{m.d.c.(28, 42)}$ é $1$, o que significa que o máximo divisor comum entre $\frac{28}{m.d.c.(28, 42)}$ e $\frac{42}{m.d.c(28, 42)}$ é $1$.

Logo, $\frac{28}{m.d.c(28, 42)}$ e $\frac{42}{m.d.c(28, 42)}$, são primos entre si.

Resultado: Sejam $a$ e $b$ números naturais quaisquer, $\frac{a}{m.d.c.(a, b)}$ e $\frac{b}{m.d.c.(a, b)}$ são primos entre si.

Há uma infinidade de números primos (intuição) - 2

Comecemos por considerar uma lista com os dois primeiros números primos: o 2 e o 3. Consideremos o número que é formado pela soma da multiplicação destes dois números primos com 1, ou seja, 2×3+1=7. Será este número primo? Sim, porque 7 só é divisível por ele próprio e por 1.

Adicionemos agora 7 à lista de primos. Ou seja, a nossa lista de primos é agora constituída pelos números 2, 3 e 7. De seguida, voltemos a pensar da mesma forma. Será 2×3×7+1=43 primo? Sim, porque 43 só é divisível por ele próprio e por 1.

Adicionemos 43 à lista de primos. Ou seja, a nossa lista de primos é agora constituída pelos números 2, 3, 7 e 43. De seguida, voltemos a pensar da mesma forma. Será 2×3×7×43+1=1807 primo? Ora bem, de facto, como sabemos que 1807 não é divisível por nenhum número primo da nossa lista (porque se efectuarmos a divisão de 1807 por qualquer um dos números primos da nossa lista, obtemos sempre resto 1), só existem duas possibilidades, ou 1807 é primo, ou é um número composto divisível por um primo que está fora da nossa lista. No entanto, 1807 não é primo porque é divisível por 13, que é um número primo que não está na nossa lista. O que significa que encontramos um novo número primo que podemos acrescentar à nossa lista de primos. Desta forma, a nossa a lista passa a ser constituída pelos números, 2, 3, 7, 43 e 13 e podemos repetir o processo estudando se 2x3x7x43x13+1 é primo, e assim encontrar um novo primo para adicionar à nossa lista.

Como posso repetir este processo tantas vezes quantas eu queira, é muito fácil criar uma lista números primos tão grande quanto eu queira, e portanto, não podem existir um número finito de números primos.

Logo, há uma infinidade de números primos.

Há uma Infinidade de números primos (intuição)

Suponhamos que os únicos primos que existiam eram apenas dois: o $2$ e o $3$.

Consideremos o número que é formado pela soma da multiplicação destes dois  números primos com $1$, ou seja, $2\times 3+1=7$. Será este número primo? Sim, porque nem o $2$, nem o $3$, dividem $7$ já que após efectuarmos a divisão de $7$ por qualquer um destes primos obtemos sempre resto $1$, e não $0$.

Adicionemos agora $7$ à lista de primos. Ou seja, a nossa lista de primos é agora constituída pelos números $2$, $3$ e $7$. De seguida, voltemos a pensar da mesma forma. Será $2 \times 3 \times 7+1=43$ primo? Sim, porque $43$ não é divisível por nenhum dos primos da nossa lista. Ao efectuarmos a divisão, obtemos sempre resto $1$.

Adicionemos $43$ à lista de primos. Ou seja, a nossa lista de primos é agora constituída pelos números $2$, $3$, $7$ e  $43$. De seguida, voltemos a pensar da mesma forma. Será $2 \times 3 \times 7\times 43+1=1807$ primo? Sim, porque $1807$ não é divisível por nenhum dos primos da nossa lista. Ao efectuarmos a divisão, obtemos sempre resto $1$.

Como posso repetir este processo tantas vezes quanto eu queira é muito fácil criar uma lista infinita de números primos, e portanto, não podem existir um número finito de números primos.

Conclusão: Há uma infinidade de números primos.

Algoritmo de Euclides (descrição detalhada)

O Algoritmo de Euclides consiste num conjunto de procedimento que permitem de uma forma simples e eficaz de calcular o máximo divisor comum entre dois números naturais, recorrendo ao algoritmo da divisão.

Intuição: Após a aplicação do algoritmo da divisão de dois números naturais, qualquer número que divida o Dividendo ($D$) e o divisor ($d$) também divide o resto ($r$).

Exemplo: Após efectuarmos a divisão de $26$ por $10$ concluímos que $26=10\times 2+6$. Ou seja, neste caso:

• $D=16$
• $d=10$
• $r=6$. 

Como, $1$, $2$, $13$, $26$ dividem $26$ ($D$), e $1$, $2$, $5$, $10$ dividem $10$ ($d$), os divisores comuns a $26$ e $10$ são $1$ e $2$. Mas como facilmente podemos observar, todos os divisores comuns a $26$ e $10$ são também divisores de $6$ ($r$).

Nota: Contudo, o inverso nem sempre é verdade. No exemplo anterior, podemos constatar que $3$ divide $6$ ($r$), e $3$ não divide $10$ ($d$) nem $26$ ($D$).

Mais geralmente, qualquer divisor comum a $D$ e $d$, é divisor comum a $D$, $d$ e $r$, e em particular, é divisor comum apenas de $d$ e $r$.

E é neste último princípio que se baseia o algoritmo de Euclides.

Dados dois números naturais, um maior do que o outro:

1. Aplicamos o algoritmo da divisão considerando $D$ o maior e $d$ o menor para obter $r$.
2. Como os divisores comuns a $D$ e $d$ são os mesmos de $d$ e $r$, voltamos a efectuar o primeiro passo, mas agora aplicando o algoritmo da divisão a $d$ e $r$.
3. Repetimos o passo 2  sucessivamente até obtermos resto 0. Quando isso acontecer, o máximo divisor comum que procuramos é exactamente o último número que consideramos para $d$.

Exemplo: Para ilustrar o que vem sendo referido, calculemos o máximo divisor comum entre $40$ e $30$.

Aplicando o algoritmo da divisão concluímos que $$40=30\times1+10.$$

De seguida, por forma continuarmos o procedimento descrito pelo algoritmo de Euclides, como não obtivemos resto 0, aplicamos ao algoritmo da divisão, mas desta vez, a 30 e 10 concluindo que $$30=10\times 3+\underline{0}.$$  

Como obtivemos resto $0$ o processo está terminado porque, pelo procedimento que utilizamos, os divisores comuns entre $40$ e $30$, são divisores comuns entre $30$ e $10$, que por sua vez são divisores comuns entre $10$ e $0$. Ora, como qualquer número divide $0$, os divisores comuns entre $40$ e $30$ vão ser, na prática, apenas de os divisores de $10$, que são $1$,$2$,$5$,e $10$. O que significa que o máximo divisor comum entre $40$ e $30$ é $10$ (o último número que consideramos para $d$ na aplicação do algoritmo). Ou seja, em linguagem matemática $m.d.c.(40,30)=10$.

Também pode ver uma ilustração geométrica do algoritmo de Euclides nesta publicação.

Critério de divisibilidade por 9

Nesta publicação vou tentar explorar o critério de divisibilidade por $9$ verificando se $234$ é divisível por $9$ recorrendo a uma possível interpretação geométrica deste critério.

Primeiramente, comecemos por notar que

$$234=200+30+4.$$

O que significa que as $234$ unidade podem corresponder a $234$ quadrículas distribuídas como ilustra a figura abaixo:

Assim, fazendo corresponder a cor das quadrículas à cor com que aparecem escritas na igualdade abaixo, obtemos o seguinte:

$$234=200+30+4=(\color{blue}{9\times2\times11}+\color{red}{2})+(\color{blue}{9\times3}+\color{red}{3})+\color{red}{4}.$$

Ou seja,
$$234=\color{blue}{9\times2\times11}+\color{blue}{9\times3}+\color{red}{2}+\color{red}{3}+\color{red}{4}.$$ Ora, como as parcelas a azul são divisíveis por $9$, então $234$ será divisível por $9$ se $\color{red}{2}+\color{red}{3}+\color{red}{4}$ for divisível por $9$. Isto é, se a soma dos algarismo que compõe o número $234$ for divisível por $9$.

Desta forma, como $\color{red}{2}+\color{red}{3}+\color{red}{4}=9$, e $9$ divisível por $9$, podemos concluir que $\underline{234 \text{ é divisível por } 9}$.

Critério: Um número $N$ é divisível por $9$ se e apenas se a soma dos algarismos que o compõe for divisível por $9$.

Algoritmo de Euclides

Recorrendo ao Algoritmo de Euclides, calcula o máximo divisor comum entre 24 e 10.

Resolução:

Utilizando o algoritmo da divisão inteira repetidamente facilmente podemos concluir que:

Logo, o máximo divisor comum entre  $24$ e $10$ é $2$.

Critério de divisibilidade por 4 - Critério 2

Na publicação anterior explorei critério 1 de divisibilidade por 4, onde concluímos que:

Critério 1: Um número $N$ é divisível por $4$ se e apenas se o número formado pelos dois últimos algarismos de for divisível por $4$.

Ou seja, um número ser divisível por $4$ depende apenas de o número formado pelos dois últimos algarismos o ser.
Neste aspecto, o critério $2$ não é diferente e apenas nos descreve uma forma diferente de analisar se o número formado pelos dois últimos algarismos é divisível por $4$.

Então consideremos o número $732$. Será múltiplo de $4$? Como já sabemos, $732$ será múltiplo de $4$ se $32$ o for. No entanto, para este caso, facilmente concluímos que $32$ é múltiplo de $4$ porque $32=4\times8$. Logo, 732 também é múltiplo de 4.

Mas verifiquemos se o $32$ é múltiplo de $4$ observando o caso de outro ângulo.

Como sabemos, $32=30+2=3\times10+2$ isto significa que podemos pensar em 32 unidades distribuídas por $3$ rectângulos de $10$ quadriculas e um rectângulo mais pequeno com apenas duas quadrículas, tal como ilustra a figura abaixo:

Assim, tentando dividir as $32$ quadrículas em rectângulos mais pequenos de $4$ quadrículas, o que obtemos é, por exemplo, o seguinte:

O que significa que, o número $32$ pode ser reescrito como

$$32=4\times 6+ 2\times3+2.$$

Desta forma, para que $32$ seja múltiplo de $4$ basta verificar se a soma do dobro de $3$ (algarismo das dezenas) com $2$ (algarismo das unidades) é múltiplo de $4$. Assim, como $2\times3+2=8$ e $8$ é múltiplo de 4, então 32 é múltiplo de 4. Logo, $732$ também é múltiplo de $4$, assim como por exemplo, $1032$, $7032$, $1232$, $332$, $22222232$, etc.

Critério 2: Um número $N$ é divisível por $4$ se e apenas se o dobro do valor do algarismo das dezenas adicionado ao valor do algarismo das unidades for divisível por $4$.

Critério de divisibilidade por 4 - Critério 1

Ao longo desta publicação vou explorar um dos critérios de divisibilidade por $4$.

Comecemos por explorar o caso em que os algarismos das dezenas e das unidades são simultaneamente zero.

Por exemplo, $100$ é divisível por $4$? Sim, porque $100=4\times25+0$. O que intuitivamente poderá significar que podemos dividir um quadrado constituído por $100$ quadrículas ($10$ quadrículas de lado), em $25$ quadrados mais pequenos de $4$ quadrículas, sem que reste qualquer quadrícula, como por exemplo, mostra a figura abaixo:

E $200$ é divisível por $4$? Sim, porque $200= 2\times100$ e porque se pensarmos em duzentas quadrículas repartidas por $2$ quadrados de $100$ quadrículas cada um, como mostra a figura abaixo, facilmente concluímos que, como que $100$ é divisível por $4$, $200$, também o será. Basta observar que conseguimos dividir as $200$ quadrículas, de forma semelhante ao que foi efectuado no exemplo anterior, em $50$ quadrados mais pequenos de 4 quadrículas cada um, sem que reste nenhuma quadrícula. Ou seja, $200=4\times 50+0$.

E $500$, será divisível por $4$? Sim, porque se $500=5 \times 100$ para justificarmos que $500$ é múltiplo de $4$ podemos utilizar um raciocínio semelhante ao caso anterior, utilizando $5$ quadrados de $100$ quadrículas para concluir que $500=4\times125$.
Ou então podemos efectuar simplesmente, $500=5\times100=5\times4\times25$, porque $100=4\times 25$. Ou seja, $500=4\times (5\times 25)=4\times125$.

E $3000$ é múltiplo de $4$? Claro que sim, porque $3000=30 \times 100$, o que significa que através raciocínios semelhantes aos efectuados anteriormente podemos concluir que $3000=4\times 750$.
Ou então também podemos efectuar simplesmente, $3000=30 \times100=30\times4\times25$, porque $100=4\times 25$. Ou seja, $3000=4 \times (30\times 25)=4\times750$.

Regra: Sempre que um número tenha o algarismo das dezenas e o algarismo das unidades iguais a $0$, o número é divisível por $4$.

A partir daqui, vou-me concentrar em estender a análise a casos em que o algarismos das dezenas e das unidades não são simultaneamente zero.

$216$ será múltiplo de $4$?
Primeiro, observemos que  $216=200+16$. Como já verificamos, $200$ é múltiplo de $4$, $216$ será múltiplo de $4$ se $16$ o for. Mas como $16=4\times 4$, 16 é múltiplo de 4, e então $216$, também o é.

$5077$, será múltiplo de $4$?
Primeiro, observemos que $5077=5000+77$. Como $5000$ é múltiplo de $4$ (porque os algarismos das dezenas e das unidade são simultaneamente zero), $5077$ será múltiplo de $4$ se $77$ o for. No entanto, $77=4\times19+1$. Logo, $77$ não é múltiplo de $4$, o que significa que $5077$ também não o é.

Critério: Um número $N$ é divisível por $4$ se e apenas se o número formado pelos dois últimos algarismos de for divisível por $4$.