APOSTILA-INTRODUÇÃO-A-TEORIA-DOS-NÚMEROS

Prévia do material em texto

<p>CENTRO UNIVERSITÁRIO FAVENI</p><p>INTRODUÇÃO A TEORIA DOS</p><p>NÚMEROS</p><p>GUARULHOS – SP</p><p>1</p><p>SUMÁRIO</p><p>1 INTRODUÇÃO ........................................................................................................ 3</p><p>2 HISTÓRIA DOS NÚMEROS ................................................................................... 4</p><p>2.1 Origens primitivas ............................................................................................... 4</p><p>2.2 Sistema de numeração Babilônico ...................................................................... 5</p><p>2.3 Sistema de numeração Egípcio .......................................................................... 6</p><p>2.4 O Sistema Romano ............................................................................................. 6</p><p>2.5 Sistema de numeração indo – arábico ................................................................ 7</p><p>3 NÚMEROS INTEIROS E INDUÇÃO MATEMÁTICA ............................................... 8</p><p>3.1 Conjunto dos números inteiros ℤ ........................................................................ 8</p><p>3.1.1 Propriedades do operador adição (+) sobre o conjunto dos números inteiros ℤ..9</p><p>3.1.2 Propriedades do operador multiplicação (∙) sobre o conjunto dos números inteiros</p><p>ℤ.................................................................................................................................10</p><p>3.1.3 Divisibilidade no conjunto dos números inteiros ℤ ............................................ 11</p><p>3.2 Conectivos lógicos ............................................................................................ 11</p><p>3.2.1 Conjunção.... ..................................................................................................... 12</p><p>3.2.2 Disjunção..... ..................................................................................................... 12</p><p>3.2.3 Condicional...... ................................................................................................ .13</p><p>3.2.4 Bicondicional ..................................................................................................... 14</p><p>3.3 Princípio da indução matemática ...................................................................... 14</p><p>4 DIVISIBILIDADE ................................................................................................... 17</p><p>4.1 O algoritmo euclidiano ...................................................................................... 17</p><p>4.2 Teorema do algoritmo da divisão de Euclides .................................................. 18</p><p>4.2.1 Demonstração do teorema do algoritmo da divisão de Euclides ...................... 18</p><p>4.3 Sistema de numeração decimal ........................................................................ 21</p><p>5 NÚMEROS PRIMOS ............................................................................................. 23</p><p>5.1 Teorema fundamental da aritmética ................................................................. 25</p><p>6 MÚLTIPLOS E DIVISORES DE UM NÚMERO ..................................................... 30</p><p>6.1 MMC e MDC ..................................................................................................... 31</p><p>7 DIVISIBILIDADE E O USO DA CONGRUÊNCIA E DOS TEOREMAS DE FERMAT</p><p>E DE WILSON ........................................................................................................... 35</p><p>7.1 Critérios de divisibilidade aplicando congruência.............................................. 35</p><p>2</p><p>7.2 Critérios de divisibilidade .................................................................................. 36</p><p>7.2.1 Critério de divisibilidade por 2 ........................................................................... 37</p><p>7.2.2 Critério de divisibilidade por 3 ........................................................................... 37</p><p>7.2.3 Critério de divisibilidade por 4 ........................................................................... 37</p><p>7.2.4 Critério de divisibilidade por 8 ........................................................................... 38</p><p>7.2.5 Critério de divisibilidade por 11 ......................................................................... 38</p><p>7.3 Estruturação dos teoremas de Wilson e de Fermat .......................................... 40</p><p>7.3.1 Teorema de Wilson ........................................................................................... 42</p><p>7.3.2 Teorema de Euler ............................................................................................. 44</p><p>7.3.3 Teorema de Fermat .......................................................................................... 45</p><p>7.4 Aplicações dos teoremas de Wilson e de Fermat ............................................. 46</p><p>8 EQUAÇÕES DIOFANTINAS E O TEOREMA CHINÊS DO RESTO ..................... 47</p><p>8.1 Equações diofantinas ........................................................................................ 47</p><p>8.2 Teorema chinês do resto .................................................................................. 51</p><p>9 O PRINCÍPIO DA CASA DOS POMBOS .............................................................. 54</p><p>10 FUNÇÃO DE MÖBIUS .......................................................................................... 58</p><p>11 PRIMOS DE FERMAT E DE MERSENNE ............................................................ 60</p><p>11.1 Números Perfeitos ............................................................................................ 62</p><p>12 SEQUÊNCIA DE FIBONACCI ............................................................................... 64</p><p>13 CONGRUÊNCIAS QUADRÁTICAS ...................................................................... 68</p><p>13.1 Resíduos Quadráticos ...................................................................................... 68</p><p>13.2 Símbolo de Legendre e o Critério de Euler ....................................................... 70</p><p>14 A LEI DA RECIPROCIDADE QUADRATICA ........................................................ 72</p><p>14.1 As Leis suplementares ...................................................................................... 73</p><p>14.2 O Lema de Gaus ............................................................................................... 73</p><p>REFERÊNCIAS ......................................................................................................... 76</p><p>3</p><p>1 INTRODUÇÃO</p><p>Prezado aluno!</p><p>O Grupo Educacional FAVENI, esclarece que o material virtual é semelhante</p><p>ao da sala de aula presencial. Em uma sala de aula, é raro – quase improvável - um</p><p>aluno se levantar, interromper a exposição, dirigir-se ao professor e fazer uma</p><p>pergunta, para que seja esclarecida uma dúvida sobre o tema tratado. O comum é</p><p>que esse aluno faça a pergunta em voz alta para todos ouvirem e todos ouvirão a</p><p>resposta. No espaço virtual, é a mesma coisa. Não hesite em perguntar, as perguntas</p><p>poderão ser direcionadas ao protocolo de atendimento que serão respondidas em</p><p>tempo hábil.</p><p>Os cursos à distância exigem do aluno tempo e organização. No caso da nossa</p><p>disciplina é preciso ter um horário destinado à leitura do texto base e à execução das</p><p>avaliações propostas. A vantagem é que poderá reservar o dia da semana e a hora</p><p>que lhe convier para isso.</p><p>A organização é o quesito indispensável, porque há uma sequência a ser</p><p>seguida e prazos definidos para as atividades.</p><p>Bons estudos!</p><p>4</p><p>2 HISTÓRIA DOS NÚMEROS</p><p>Os números estão em toda parte como em um calendário, na identificação de</p><p>um jogador (camiseta 10), no código do ônibus (637 – J), nos telefones (2643 – 0000),</p><p>na colocação de ganhadores com seu número ordinal (1° colocado, 2° colocado e</p><p>assim por diante), os números são utilizados em diversas situações por meio</p><p>6 × 7 × 8 × 9 módulo 5</p><p>utilizando o teorema de Wilson.</p><p>Observamos que os resíduos menores de cada número da multiplicação acima</p><p>são 6 ≡ 1 (mod 5), 7 ≡ 2 (mod 5), 8 ≡ 3 (mod 5) e 9 ≡ 4 (mod 5). Então, pelas</p><p>propriedades aritméticas de congruência, obtemos 6 × 7 × 8 × 9 ≡ 1 × 2 × 3 × 4 (mod</p><p>5). Também, sabemos pelo teorema de Wilson que 4! ≡ –1 (mod 5). Pela</p><p>transitividade, 6 × 7 × 8 × 9 ≡ –1 ≡ 4 (mod 5). Logo, o menor resíduo positivo é 4.</p><p>47</p><p>8 EQUAÇÕES DIOFANTINAS E O TEOREMA CHINÊS DO RESTO</p><p>O teorema chinês do resto é um tópico da teoria dos números e um teorema de</p><p>grande importância e aplicabilidade. Acredita-se que ele tenha surgido em decorrência</p><p>de algum problema prático da Antiguidade, uma vez que uma das suas grandes</p><p>aplicações é na partilha de senha. As equações diofantinas, termo advindo do</p><p>matemático Diofanto de Alexandria, foram extremamente relevantes para o</p><p>desenvolvimento da álgebra e começaram a ser usadas no século III d.C.</p><p>As equações diofantinas são equações polinomiais que permitem a duas ou</p><p>mais variáveis assumirem apenas valores inteiros. Para resolver esse tipo de</p><p>equação, deve-se buscar as soluções para as variáveis que sejam números inteiros.</p><p>Assim, alguns passos devem ser realizados para solucioná-las.</p><p>Nesta seção, você vai estudar as equações diofantinas, compreendendo a sua</p><p>definição, o seu método de resolução e a sua teoria, além de exemplos detalhados e</p><p>aplicações práticas. Você também vai aprender sobre o teorema chinês do resto, mais</p><p>especificamente a sua prova, os seus métodos de resolução e as suas aplicações</p><p>práticas. Você vai verificar sugestões de caminhos que se pode percorrer para a</p><p>aplicação dos conteúdos que são estudados em álgebra.</p><p>8.1 Equações diofantinas</p><p>As equações diofantinas são todas as equações polinomiais com coeficientes</p><p>inteiros em que o universo das variáveis é o conjunto dos números inteiros. Aqui,</p><p>veremos as equações diofantinas lineares em duas incógnitas, ou seja, equações da</p><p>forma ax + by = c, em que a e b são inteiros não nulos. Uma solução para essa</p><p>equação será um par (x0 , y0 ) de inteiros tal que a sentença ax₀ + by₀ = c é verdadeira</p><p>(DOMINGUES; IEZZI, 2018).</p><p>Scheinerman (2016) apresenta o teorema: sejam a e b inteiros, não</p><p>simultaneamente nulos. O menor inteiro positivo da forma ax + by, em que x e y são</p><p>inteiros, é MDC (a, b), sendo MDC o máximo divisor comum. Sejam a e b inteiros,</p><p>uma combinação linear de inteiros de a e b é qualquer número com a forma ax + by,</p><p>onde x e y também sejam inteiros. O teorema garante que a combinação linear de</p><p>inteiros mínima de a e b é MDC (a, b).</p><p>48</p><p>Para verificar um exemplo, com base em Scheinerman (2016), considere a =</p><p>30 e b = 24. Podemos fazer uma tabela dos valores ax + by para os inteiros x e y entre</p><p>–4 e 4, conforme apresenta a Figura abaixo:</p><p>Tabela de valores ax + by para os inteiros x e y entre –4 e 4.</p><p>Fonte: Scheinerman (2016, p. 361).</p><p>Note que o menor valor positivo nessa tabela é o número 6 em x = –3, y = 4,</p><p>pois 30 × (–3) + 24 × 4 = –90 + 96 = 6, e novamente em x = 1, y = –1, pois 30 × 1 +</p><p>24 × (–1) = 30 – 24 = 6. Vimos uma parcela relativamente pequena de todos os valores</p><p>possíveis de ax + by. Se prolongássemos essa tabela, seria possível encontrarmos</p><p>um valor positivo menor para 30x + 24y? Não, pois tanto 30 como 24 são divisíveis</p><p>por 6. Portanto, qualquer inteiro da forma 30x + 24y é também divisível por 6. Dessa</p><p>forma, mesmo prolongando indefinidamente a tabela da Figura 1, 6 é o menor inteiro</p><p>positivo que pode ser encontrado.</p><p>Scheinerman (2016) também afirma que: sejam a e b inteiros arbitrários (não</p><p>simultaneamente nulos); é impossível acharmos inteiros x e y com 0 < ax + by < MDC</p><p>(a, b), porque ax + by é divisível por MDC (a, b). O ponto central é que podemos achar</p><p>inteiros x e y de modo que ax + by = MDC (a, b).</p><p>Para encontrar x e y em ax + by = MDC (a, b), é necessário estender o algoritmo</p><p>de Euclides. Vejamos como funciona esse método encontrando x e y de modo que</p><p>431x + 29y = MDC (431,29) = 1 (SCHEINERMAN, 2016). O cálculo de MDC (431,29)</p><p>pelo algoritmo de Euclides será:</p><p>431 = 14 × 29 + 25</p><p>29 = 1 × 25 + 4</p><p>25 = 6 × 4 + 1</p><p>4 = 4 × 1 + 0</p><p>49</p><p>Em todas essas equações, exceto a última, resolvemos em relação ao resto e</p><p>escrevemos o resto à esquerda.</p><p>25 = 431 – 14 × 29</p><p>4 = 29 – 1 × 25</p><p>1 = 25 – 6 × 4</p><p>Passamos a trabalhar a partir da base. Note que a última equação tem 1 na</p><p>forma 25x + 4y. Substituímos o 4 utilizando a equação anterior:</p><p>1 = 25 – 6 × 4</p><p>= 25 – 6 × (29 – 1 × 25)</p><p>= –6 × 29 + 7 × 25</p><p>Agora, tomamos 25 = 431 – 14 × 29 para substituir o 25 em 1 = –6 × 29 + 7 ×</p><p>25:</p><p>1 = –6 × 29 + 7 × 25</p><p>= –6 × 29 + 7 × (431 – 14 × 29)</p><p>= 7 × 431 + [–6 + 7 × (–14)] × 29</p><p>= 7 × 431 + (–104) × 29</p><p>Assim, encontramos x = 7 e y = –104, para obter 431x + 29y = MDC (431,19) =</p><p>1.</p><p>Domingues e Iezzi (2018, p. 48) apresentam a seguinte proposição: “Uma</p><p>equação diofantina linear ax + by = c tem solução se, e somente se, d = MDC (a, b) é</p><p>um divisor de c”. Vejamos um exemplo de resolução de uma equação diofantina, com</p><p>base em Domingues e Iezzi (2018). Vamos encontrar uma solução da equação</p><p>diofantina 26x + 31y = 2. Como MDC (26, 31) = 1, então a equação tem solução.</p><p>Usaremos o método das divisões sucessivas para exprimir o MDC de 26 e 31 por meio</p><p>de uma identidade de Bezout:</p><p>31 = 26 ∙ 1 + 5</p><p>26 = 5 ∙ 5 + 1</p><p>5 = 1 ∙ 5</p><p>Assim: 1 = 26 – 5 ∙ 5 = 26 – (31 – 26 ∙ 1) ∙ 5 = 26 ∙ 6 + 31 ∙ (–5)</p><p>50</p><p>Então (x₀, y₀) = (6, –5), e, portanto, o par (2 ∙ 6,2 ∙ (–5)) = (12, –10) é uma</p><p>solução da equação dada. Consequentemente (–12, –10), (12, 10) e (–12, 10) são</p><p>soluções, respectivamente, de (–26)x + 31y =2, 26x – 31y = 2 e (–26)x + (–31y) = 2.</p><p>Outra proposição importante apresentada por Domingues e Iezzi (2018) se</p><p>refere à equação diofantina ax + by = c, que tem uma solução (x0 , y0 ). Nesse caso,</p><p>ela tem infinitas soluções, e o conjunto das soluções é S = {(x0 + (b|d)t, y0 – (a|d)t|t ∈</p><p>Z}, em que d = MDC (a, b). Geometricamente, essa proposição evidencia que a reta</p><p>de equação ax + by = c possui uma infinidade de pontos de coordenadas inteiras no</p><p>plano cartesiano.</p><p>Vejamos outro exemplo de resolução de equação diofantina, também com base</p><p>em Domingues e Iezzi (2018). Dessa vez, vamos encontrar todas as soluções da</p><p>equação diofantina 43x + 5y = 250. Como MDC (43, 5) = 1, que divide 250, a equação</p><p>tem soluções.</p><p>É importante lembrar que, se (x₀, y₀) é uma solução de 43x + 5y = 1, então</p><p>(250x₀, 250y₀) é solução da equação dada. A solução de 43x + 5y = 1 por divisões</p><p>sucessivas será:</p><p>43 = 5 ∙ 8 + 3</p><p>5 = 3 ∙ 1 + 2</p><p>3 = 2 ∙ 1 + 1</p><p>Assim:</p><p>1 = 3 – 2 ∙ 1 = 3 – (5 – 3 ∙ 1) ∙ 1 = 3 ∙ 2 + 5 ∙ (–1)</p><p>= (43 – 5 ∙ 8) ∙ 2 + 5 ∙ (–1) = 43 ∙ 2 + 5 ∙ (–17)</p><p>Então, uma solução de 43x + 5y = 1 é (2, –17). Logo, uma solução de 43x + 5y</p><p>= 250 é (500, –4.250). De onde a solução geral da equação pode ser expressa por:</p><p>(500 + 5t, –4250 – 43t)</p><p>Em que t é uma variável no conjunto dos inteiros. A reta de equação 43x + 5y</p><p>= 250 possui uma infinidade de pontos de coordenadas inteiras do plano cartesiano.</p><p>51</p><p>8.2 Teorema chinês do resto</p><p>Nesta seção, será abordado o teorema chinês do resto. Para tanto, partiremos</p><p>de uma indagação apresentada por Lipschutz e Lipson (2013, p. 281): existe um inteiro</p><p>positivo x que dividido por 3 tem resto 2, dividido por 5 tem resto 4 e dividido por 7 tem</p><p>resto 6? Ou seja, busca-se uma solução para as três equações de congruência:</p><p>x ≡ 2 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7)</p><p>Note que os módulos 3, 5 e 7 são primos entre si se tomados dois a dois. Então,</p><p>o teorema a seguir, conhecido por teorema chinês do resto, se aplica. Ele diz que</p><p>existe uma única solução módulo M = 3 ∙ 5 ∙ 7 = 105 (LIPSCHUTZ; LIPSON, 2013).</p><p>Prazeres (2014, p. 36) enuncia o teorema chinês do resto da seguinte forma:</p><p>sejam a₁ , a₂ , …, ak números inteiros positivos, de tal forma que (ai , aj ) = 1, ∀i, j =0,</p><p>1, 2, ..., k e i ≠ j. Dados inteiros quaisquer b₁, b₂, …, bᵏ , o sistema de congruências</p><p>lineares dado por:</p><p>52</p><p>O teorema chinês do resto pode ser expresso em diferentes notações a</p><p>depender do autor em estudo. A seguir, vemos como Lipschutz e Lipson (2013) o</p><p>apresentam. Considere o sistema x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), …, x ≡ rₖ (mod mₖ),</p><p>onde os mi são primos entre si, tomados dois a dois. Então, o sistema tem uma única</p><p>solução módulo M = m₁ m₂ … mₖ. Uma fórmula explícita para a solução desse sistema</p><p>pode ser apresentada por meio da proposição a seguir (LIPSCHUTZ; LIPSON, 2013).</p><p>Lipschutz e Lipson (2013) apresentam a solução ao problema original de duas</p><p>formas, apresentadas a seguir.</p><p>Método 1: aplicando o teorema chinês do resto às duas primeiras equações.</p><p>x ≡ 2 (mod 3) e x ≡ 4 (mod 5)</p><p>O teorema chinês do resto diz que existe uma única solução módulo M = 3 ∙ 5</p><p>= 15. Adicionando múltiplos do módulo m = 5 à solução dada x = 4 da equação x ≡ 4</p><p>(mod 5), obtêm-se as três soluções a seguir, que são menores do que 15: 4,9,14.</p><p>Testando cada uma das soluções na equação x ≡ 2 (mod 3), temos que 14 é a</p><p>única solução de ambas as equações. Agora aplicando o mesmo processo às duas</p><p>equações:</p><p>x ≡ 14 (mod 15) e x ≡ 6 (mod 7)</p><p>53</p><p>O teorema chinês do resto diz que existe uma única solução módulo M = 15 ∙ 7</p><p>= 105. Adicionando múltiplos do módulo m = 15 à solução dada x = 14 da primeira</p><p>equação x ≡ 14 (mod 15), conseguimos as sete soluções a seguir de x ≡ 4 (mod 5),</p><p>as quais são menores do que 105:</p><p>14, 29, 44, 59, 74, 89, 104</p><p>Testando cada uma dessas soluções de x ≡ 14 (mod 15) na segunda equação</p><p>x ≡ 6 (mod 7), descobrimos que 104 é a única solução de ambas as equações.</p><p>Portanto, o menor inteiro positivo que satisfaz as três equações é x = 104. Essa é a</p><p>solução do problema chinês.</p><p>Método 2: usando a notação anterior, obtêm-se:</p><p>Dividindo essa solução pelo módulo M = 105, conseguimos o resto x = 104, que</p><p>é a solução única do problema entre 0 e 105. As soluções s₁ = 2, s₂ = 1 e s₃ = 1 foram</p><p>obtidas por inspeção. Se os módulos forem grandes, sempre podemos utilizar o</p><p>algoritmo euclidiano para encontrar tais soluções.</p><p>54</p><p>9 O PRINCÍPIO DA CASA DOS POMBOS</p><p>A Análise Combinatória é considerada, por muitos, um dos temas mais difíceis</p><p>da Matemática, porém existem alguns recursos que podem facilitar a resolução de</p><p>vários problemas e o Princípio da Casa dos Pombos é um deles. Esse princípio,</p><p>muitas vezes usado por nós de forma intuitiva, é formalmente pouco conhecido, mas</p><p>pode ser uma ferramenta importante na hora de resolver exercícios. (FERREIRA,</p><p>2011).</p><p>O Princípio da Casa dos Pombos foi utilizado pela primeira vez por G. Lejeune</p><p>Dirichlet em 1834 com o nome de Schubfachprinzip ("princípio das gavetas"), por esse</p><p>motivo esse princípio também é conhecido como Princípio das Gavetas de Dirichlet.</p><p>Descendente de família francesa, Dirichlet nasceu em 1805 na Alemanha, estudou na</p><p>Universidade de Paris e ocupou cargos na Universidade de Breslau e na Universidade</p><p>de Berlim. Em 1855, ele foi escolhido para ser sucessor de Gauss na Universidade de</p><p>Göttingen. Dirichlet morreu em 1859 deixando importantes contribuições em diversas</p><p>áreas da matemática com destaque para o estudo da Teoria dos Números.</p><p>O Princípio da Casa dos Pombos pode ser anunciado em sua versão mais</p><p>simples da seguinte forma: “Se tivermos n+1 pombos para serem colocados em n</p><p>casas, então pelo menos uma casa deverá conter, pelo menos, dois pombos”. Essa</p><p>afirmação parece óbvia uma vez que se tivermos um grupo de n+1 pombos voando</p><p>para dentro de n casas, então, na pior das hipóteses, se todas as casas contiverem</p><p>no máximo um pombo, no máximo n pombos (um por casa) poderão ser acomodados,</p><p>assim fica claro que pelo menos uma casa deverá conter pelo menos dois pombos.</p><p>Segue abaixo a versão mais simples do teorema principal deste trabalho.</p><p>Teorema 1.1 (Princípio da Casa dos Pombos): Se tivermos n+1 pombos para</p><p>serem colocados em n casas, então pelo menos uma casa deverá conter, pelo menos,</p><p>dois pombos.</p><p>Demonstração: Se temos n casas para n+1 pombos, é obvio que, na pior das</p><p>hipóteses, se distribuirmos exatamente um pombo para cada casa, sobrará um pombo</p><p>para ser colocado em qualquer casa. Logo uma das casas deverá conter pelo menos</p><p>dois pombos.</p><p>55</p><p>Esse teorema também é conhecido como Princípio das Gavetas e pode ser</p><p>reenunciado da seguinte forma: “Temos n objetos para serem guardados em m</p><p>gavetas. Se n > m, então pelo menos uma gaveta deverá conter mais de um objeto”.</p><p>Veremos a seguir alguns exemplos de aplicações do Princípio da Casa dos</p><p>Pombos. Em cada um deles, procuramos identificar quem são as “casas”, quem são</p><p>os “pombos” e a relação existente entre ambos.</p><p>Exemplo 1.2: Mostre que, em um ano não bissexto, em qualquer conjunto com</p><p>366 pessoas há pelo menos duas que farão aniversário no mesmo dia.</p><p>Demonstração: Neste caso temos:</p><p> Casas: dias do ano (365);</p><p> Pombos: pessoas (366);</p><p> Relação: Cada pessoa está associada ao dia do seu aniversário.</p><p>Pelo Princípio da Casa dos pombos, para n = 365, temos que pelo menos uma</p><p>“casa” deverá conter pelo menos dois “pombos”, isto é, pelo menos duas pessoas</p><p>farão aniversário no mesmo dia. (FERREIRA, 2011).</p><p>Generalização 1.3: Mostre que em um calendário qualquer com dias e um</p><p>conjunto contendo n + 1 pessoas, há pelo menos duas pessoas deste conjunto que</p><p>farão aniversário no mesmo dia.</p><p>Demonstração: Neste caso temos:</p><p> Casas: dias do ano;</p><p> Pombos: pessoas;</p><p> Relação: Cada pessoa está associada ao dia do seu aniversário.</p><p>Pelo Princípio da Casa dos pombos, “pombos” para serem distribuídos em</p><p>“casas”, logo uma casa deverá conter pelo menos dois “pombos”, isto é, pelo menos</p><p>duas pessoas farão aniversário no mesmo dia. (FERREIRA, 2011).</p><p>56</p><p>No Exemplo 1.4 e na Generalização 1.5 a seguir, usaremos como ideia</p><p>fundamental o fato de que qualquer número inteiro a se escreve sob a forma a= 2ᵏb,</p><p>onde k é um número inteiro não negativo e um inteiro ímpar.</p><p>Exemplo 1.4: Escolha dentre os inteiros {1, 2, 3, 4, 5, 6}, quatro números</p><p>quaisquer. Mostre que, entre os números escolhidos, há dois números tais que um</p><p>deles é divisível pelo outro.</p><p>Demonstração: Escrevendo todos os inteiros do conjunto na forma a = 2ᵏb,</p><p>temos:</p><p>Note que b é um dos números inteiros ímpares 1, 3, 5. A importância de tal</p><p>número fica evidente ao listarmos todas as possibilidades de escolha dos</p><p>quatro números e destacarmos, em cada caso, aqueles que possuem a mesma parte</p><p>ímpar. (FERREIRA, 2011). Vejamos:</p><p>Podemos observar que, em todas as opções listadas acima, existem pelo</p><p>menos dois números que ao serem escritos na forma , possuem suas partes</p><p>ímpares iguais e, consequentemente, um deles é divisível pelo outro e assim é natural</p><p>associar cada situação acima com uma configuração de “pombos” em “casas” da</p><p>seguinte forma:</p><p> Casas: valores para b quando</p><p> Pombos: quatro números escolhidos em {1, 2,..., 6};</p><p> Relação: Cada número está associado a sua parte ímpar.</p><p>57</p><p>Por exemplo, para as três primeiras possibilidades de escolha citadas acima,</p><p>temos:</p><p>Logo, temos quatro pombos para serem distribuídos em três casas, o que nos</p><p>garante que pelo menos uma casa deverá conter pelo menos dois pombos. Em outras</p><p>palavras, quando escolhemos quatro números do conjunto {1, 2, 3, 4, 5, 6} pelo menos</p><p>dois deles terão suas partes ímpares iguais e, portanto, um deles será divisível pelo</p><p>outro. (FERREIRA, 2011). Para mais detalhes, veja a generalização logo abaixo.</p><p>Generalização 1.5: Mostre que se do conjunto {1, 2, ...2n} retiramos (n+1)</p><p>números ao acaso, então um deles dividirá um outro.</p><p>Demonstração: Analogamente ao exemplo anterior,</p><p>chamamos de a qualquer</p><p>número inteiro pertencente ao conjunto {1, 2, ...2n}. Sabemos que a pode ser escrito</p><p>na forma a =2ᵏb e que b é um dos números ímpares 1, 3, ... 2n -1. Podemos aplicar o</p><p>Princípio da Casa dos Pombos da seguinte forma:</p><p> Casas: valores para b quando a =2ᵏb (note que temos n valores para , já</p><p>que b { 1, 3, ... 2n -1}).</p><p> Pombos: (n+1) números escolhidos em {1, 2, ...2n};</p><p> Relação: Cada número está associado a sua parte ímpar.</p><p>Logo, pelo Princípio da Casa dos Pombos, ao escolhermos, ao acaso, (n+1)</p><p>números deste conjunto, dois destes números, digamos a₁ e a₂, terão suas partes</p><p>ímpares (b) iguais.</p><p>58</p><p>10 FUNÇÃO DE MÖBIUS</p><p>A clássica função de Möbius μ(n) é uma função multiplicativa na Teoria dos</p><p>Números e Análise Combinatória. Tem esse nome em homenagem ao matemático</p><p>alemão August Ferdinand Möbius, que foi o primeiro a defini-la em 1831.</p><p>Denotada por μ(n), a função de Möbius possui em seu domínio de definição</p><p>todos os números naturais e sua imagem possui três elementos: -1, 0, e 1.</p><p>(RODRIGUES, 2019). Uma maneira simples de regrar a relação entre os elementos</p><p>do domínio e da imagem é a seguinte:</p><p> μ(n) = 0 se n tem como divisor um outro número natural ao quadrado;</p><p> μ(n) = 1 se n não tem como divisor um outro número natural ao quadrado e</p><p>é decomposto em uma quantidade par de números primos;</p><p> μ(n) = -1 se n não tem como divisor um outro número natural ao quadrado e</p><p>é decomposto em uma quantidade ímpar de números primos.</p><p>A função µ de Möbius é definida como:</p><p>Observação 1. Em outras palavras, a Definição afirma que se µ(n) = 0, então</p><p>n é divisível pelo quadrado de algum p-primo.</p><p>Teorema 2.9. A função µ de Möbius é multiplicativa.</p><p>Demonstração. Sejam m e n ∈ Z ∗ + tais que (m, n) = 1.</p><p>Primeiro, se n = 1 ou m = 1, então é óbvio que µ(m · n) = µ(m) · µ(n).</p><p>Segundo, suponhamos que existe p-primo tal que p 2 |(m · n), então</p><p>pois (m, n) = 1. Logo,</p><p>i) Se p 2 |m, então µ(m) = 0 e µ(m · n) = 0 e, portanto, µ(m) · µ(n) = 0, ou seja,</p><p>µ(m · n) = µ(m) · µ(n);</p><p>59</p><p>ii) Se p 2 |n, então µ(n) = 0 e µ(m · n) = 0 e, assim, µ(m) · µ(n) = 0, isto é,</p><p>µ(m · n) = µ(m) · µ(n).</p><p>E terceiro, se não existir p-primo tal que p 2 |m ou p 2 |n, então para m e n ∈ Z ∗ + −</p><p>{1}, o Teorema Fundamental da Aritmética (TFA), nos garante que:</p><p>m = p₁ · p₂ · · · pr e n = q₁ · q₂ · · · qs</p><p>Portanto, a função µ de Möbius é multiplicativa. (RODRIGUES, 2019).</p><p>Teorema 2.10. Seja n ∈ Z ∗ +. Então, é verdade que</p><p>Demonstração. Note que, pela definição de µ(n), se n = 1, então:</p><p>Entretanto, na soma</p><p>os únicos termos que não são nulos resultam de d = 1, ou dos divisores que são</p><p>produto de primos diferentes, ou seja,</p><p>60</p><p>Logo, como para n = 1 se tem F(n) = 1, e para todo n > 1 se tem F(n) = 0, então</p><p>11 PRIMOS DE FERMAT E DE MERSENNE</p><p>Nesta seção, estudaremos alguns tipos de números primos especiais e</p><p>famosos. O primeiro resultado relaciona-se com os números conhecidos como</p><p>números de Fermat em homenagem a Pierre de Fermat (1601-1665), jurista francês</p><p>e matemático amador. Após Euclides e Eratóstenes, Fermat considerado o primeiro</p><p>matemático a contribuir para o desenvolvimento da Teoria dos Números do ponto vista</p><p>teórico. Muitos dos resultados e problemas deixados por Fermat motivaram o</p><p>extraordinário avanço da Matemática. (ARAÚJO, 2017).</p><p>Proposição 2.1. Sejam a, b, n ∈ N, com a+b ≠ 0. temos que a+b divide</p><p>a2n+1+b2n+1.</p><p>Demonstração: Usando indução sobre n.</p><p>A armação é, obviamente verdade para n = 0, pois a + b divide a1 + b1.</p><p>Suponhamos agora, que a + b | a2n+1 + b2n+1. Escrevemos</p><p>a2(n+1)+1 + b2(n+1)+1 = a2a2n+1 + b2b2n+1 = (a2 − b2)a2n+1 + b2(a2n+1 + b2n+1)</p><p>Como a + b | a2 − b2e, por hipótese, a + b | a2n+1 + b2n+1, decorre das igualdades</p><p>acima e pela Proposição 1.5 que a + b | a2(n+1)+1 + b2(n+1)+1. Estabelecendo, assim, o</p><p>resultado para todo n ∈ N.</p><p>61</p><p>Proposição 2.2. Sejam a e n números naturais maiores do que 1. Se an + 1 é</p><p>primo, então a é par e n = 2m, com m ∈ N.</p><p>Demonstração: Suponhamos que an + 1 seja primo, onde a > 1 e n > 1. Logo,</p><p>a tem que ser par, pois, caso contrário, an + 1 seria par e maior do que dois, o que</p><p>contraria o fato de ser primo.</p><p>Se n tivesse um divisor primo p diferente de 2, teríamos n = n0p com n0 ∈ N∗.</p><p>Portanto, pela Proposição 2.1, an0+ 1 dividiria (an0)p + 1 = an + 1, contradizendo</p><p>o fato desse último número ser primo. Isto implica que n é da forma 2m.</p><p>Os números de Fermat são os números da forma Fn = 22n+ 1.</p><p>Em 1640, Fermat escreveu em uma de suas cartas que achava que esses</p><p>números eram todos primos, baseado na observação de que F1 = 5, F2 = 17, F3 = 257,</p><p>F4 = 65537 são primos.</p><p>Em 1732, Leonhard Euler mostrou que</p><p>F5 = 225+ 1 = 4.294.967.297 = 641 × 6700417,</p><p>e, portanto, composto, desmentindo assim a afirmação de Fermat. Os números</p><p>de Fermat primos são chamados de primos de Fermat. Até hoje, não se sabe se</p><p>existem outros primos de Fermat além dos quatro primeiros. Conjecturou-se (Hardy e</p><p>Wright) que os primos de Fermat são em número finito. Um resultado acerca desses</p><p>números, é o seguinte</p><p>(Fn, Fm) = 1, se n ≠ m.</p><p>Note que esse resultado nos fornece uma outra prova de que existem infinitos</p><p>números primos, pois cada número de Fermat tem pelo menos um divisor primo e</p><p>esses divisores primos são todos distintos. (ARAÚJO, 2017).</p><p>O resultado que se segue relaciona-se com outros números primos também</p><p>famosos.</p><p>Proposição 2.3. Sejam a e n números naturais maiores do que 1. Se an − 1 é</p><p>primo, então a = 2 e n é primo.</p><p>Demonstração: Por hipótese an − 1 é primo, com a > 1 e n > 1. Suponhamos,</p><p>por absurdo, que a > 2. Logo a − 1 > 1 e (a − 1) | (an − 1). Logo an − 1 não é primo,</p><p>absurdo. Portanto, a = 2.</p><p>62</p><p>Por outro lado, suponha, por absurdo, que n não é primo. Logo n é composto,</p><p>isto é, n = r · s com r > 1 e s > 1. Como 2r − 1 divide (2r)s − 1 = 2r·s − 1 = 2n − 1. Logo 2r</p><p>− 1 | 2s − 1. Portanto 2n − 1 não seja primo, contradição. Logo n é primo.</p><p>Definição 2.1. Os números primos da forma 2p − 1, onde p é um número primo,</p><p>são chamados Primos de Mersenne.</p><p>Notação: Mp = 2p − 1.</p><p>Observação 2.1. No intervalo 2 ≤ p ≤ 5000, os números de Mersenne que são</p><p>primos, chamados primos de Mersenne, correspondem aos seguintes valores de p: 2,</p><p>3, 5, 7, 13, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253 e 4423.</p><p>Até dezembro de 2001, o maior primo de Mersenne era M13466917, que possui no</p><p>sistema decimal 4053946 dígitos, e é o trigésimo nono primo de Mersenne conhecido.</p><p>11.1 Números Perfeitos</p><p>Definição 2.3. Um número n é chamado de número perfeito se s(N) = 2n. Ou</p><p>ainda, se o número é igual à soma de seus divisores distintos dele mesmo. Na idade</p><p>média, conhecia-se apenas os números perfeitos: 6, 28, 496, 8128. Atualmente,</p><p>conhece-se mais alguns números perfeitos. Um fato curioso é que todos os números</p><p>perfeitos são pares. Não se sabe nada sobre a existência ou não de números perfeitos</p><p>ímpares. (EUDES, 2011).</p><p>Observação 2.3. Os resultados a seguir, principalmente o Teorema de</p><p>Euclides-Euler, caracterizarão os números perfeitos pares, relacionando-os com os</p><p>números primos de Mersenne.</p><p>Lema 2.3. Seja n ∈ N∗, tem-se que S(n) = n + 1 se, e somente se, n é um</p><p>número primo.</p><p>Demonstração: Se S(n) = n + 1, segue-se que n > 1 e que os únicos divisores</p><p>de n são 1 e n: Logo n é primo. Reciprocamente, Se n é primo</p><p>Sn =n2 − 1</p><p>n − 1=(n + 1)(n − 1)</p><p>n − 1= n + 1.</p><p>Os números perfeitos fascinam os matemáticos a séculos. Acredita-se que</p><p>Pitágoras esteja entre os primeiros a se deslumbrarem com tais n´úmeros. Mas quais</p><p>63</p><p>são e que mistérios cercam os números perfeitos? A definição, encontrada nos</p><p>Elementos de Euclides, diz que; ”Número perfeito é aquele que é igual à soma de suas</p><p>partes”, entendendo como parte</p><p>de um número seus divisores próprios. (EUDES,</p><p>2011). Os quatro primeiros números perfeitos são:</p><p>6 = 1 + 2 + 3;</p><p>28 = 1 + 2 + 4 + 7 + 14;</p><p>496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248;</p><p>8128 = 1+ 2+ 4+ 8+ 16+ 32+ 64+ 127+ 254+ 508+ 1016+ 2032+ 4064.</p><p>Que eram os números perfeitos conhecidos até o século XVI. Mas por que</p><p>chamar um número com tal propriedade de perfeito? A resposta a essa pergunta ´e</p><p>ainda mais curiosa, acredita-se que o nome esteja ligado ao fato de os antigos</p><p>escribas observarem que seis foram os dias necessários para a Criação do Mundo,</p><p>com toda sua perfeição.</p><p>Esse tipo de observação serviu para envolver esses números em uma espécie</p><p>de aura, motivando ainda mais seu estudo. Apesar desse lado meio místico, a</p><p>verificação de que um número é perfeito ou não é bastante simples, basta somar seus</p><p>divisores próprios. Conforme a definição, se tal soma for igual ao próprio número ele</p><p>será perfeito. Diz-se ainda que um número é abundante se a soma dos divisores</p><p>próprios for maior que o próprio número e que é deficiente se for menor. (EUDES,</p><p>2011).</p><p>Fonte: https://rce.casadasciencias.org/rceapp/art/2020/056/</p><p>64</p><p>12 SEQUÊNCIA DE FIBONACCI</p><p>Quando se trata de sequências recursivas, um dos exemplos mais famosos e</p><p>conhecidos entre os professores de Matemática é a sequência de Fibonacci. Nascido</p><p>em Pisa, na Itália, Leonardo Fibonacci (1170-1240), também conhecido como</p><p>Leonardo Pisano ou Leonardo de Pisa, de acordo com ([3], p. 186) “foi sem dúvida o</p><p>matemático mais original e capaz do mundo cristão medieval. ” Ainda segundo [3],</p><p>seu pai foi um importante mercador de Pisa e representava os interesses comerciais</p><p>de sua cidade em Bugia, na atual Argélia, norte da África. Devido às viagens do pai,</p><p>Leonardo percorreu todo o Mediterrâneo, conhecendo nestes lugares diversas</p><p>culturas e familiarizando-se com a Matemática árabe, que era então mais</p><p>desenvolvida do que a Matemática da Europa.</p><p>Conhecendo a cultura árabe, Leonardo impressionou-se com os algarismos</p><p>indo-arábicos, e considerava mais vantajoso utilizá-los em comparação aos sistemas</p><p>numéricos então usados na Europa para registrar os números e operar com eles.</p><p>Tornou-se um dos responsáveis pela divulgação do sistema de numeração decimal</p><p>na Europa, por meio de seu livro Liber Abaci escrito em 1202. Neste livro, Fibonacci</p><p>apresentou um tratamento da Aritmética e da Álgebra Elementar. Entre os problemas</p><p>deste livro está o dos coelhos: “Quantos pares de coelhos serão produzidos num ano,</p><p>à partir de um único casal, se cada casal procria a cada mês um novo casal que se</p><p>torna produtivo depois de dois meses? ” Podemos visualizar na tabela a seguir como</p><p>a sequência do problema em questão se forma.</p><p>65</p><p>Consideremos que os coelhos não morrem, tal problema dá a origem à</p><p>mundialmente famosa “sequência de Fibonacci”, que indica a quantidade de casais</p><p>existentes em cada mês: (Fn) = (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...). Ao longo</p><p>dos séculos verificou-se que essa sequência possui propriedades belas e</p><p>significativas. Fibonacci ([3], p. 186) relata que “a sequência se aplica também a</p><p>questões de filotaxia e crescimento orgânico. ”</p><p>Observemos a sequência (Fn) = (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...). É</p><p>fácil ver que a relação de recorrência é dada, a partir do terceiro mês, pela soma do</p><p>número de casais dos dois meses anteriores. Ou seja, Fn+₂ = Fn+₁ + Fn, com F₁ =</p><p>F₂ = 1.</p><p>Fonte: https://atitudereflexiva.wordpress.com/</p><p>Podemos definir a sequência de Fibonacci por uma recorrência linear</p><p>homogênea de segunda ordem tal que: Fn+₂ = Fn+₁+ Fn, com F₁ = F₂ = 1. Vamos</p><p>resolver a equação de recorrência a fim de encontrar uma fórmula fechada que</p><p>possibilite determinar qualquer termo da sequência.</p><p>Solução: A equação da recorrência pode ser reescrita como Fn+₂ − Fn+₁ −Fn=</p><p>0, cuja equação característica é x²− x − 1 = 0, que por sua vez tem como raízes:</p><p>As soluções de uma recorrência com tal expressão são da forma:</p><p>66</p><p>Além disso, a sequência de Fibonacci tem F₁ = F₂ = 1. E assim podemos montar</p><p>o sistema:</p><p>Resolvendo o sistema chegamos às constantes</p><p>Portanto, a solução da recorrência é dada por:</p><p>Esta fórmula é conhecida por fórmula de Binet, que a descobriu em 1843.</p><p>Observemos que o resultado obtido é uma solução para um caso particular da</p><p>recorrência xn+₂ = xn+₁+xn. Caso esse, que nessa seção chamamos de sequência</p><p>de Fibonacci.</p><p>Os números de Fibonacci têm muitas propriedades que são temas de estudos</p><p>desde a Idade Média até os dias atuais. (SILVA, 2015). Nesta seção vamos analisar</p><p>algumas dessas propriedades.</p><p>Proposição 3.4.1. A soma dos n primeiros números de Fibonacci é igual ao</p><p>(n+2)-ésimo número de Fibonacci menos uma unidade.</p><p>Prova: Vamos provar por indução em n o que queremos demonstrar:</p><p>Primeiro vejamos o caso base da indução. Para n = 1 a propriedade é</p><p>verdadeira pois: F₁ = F₃ − 1 = 2 − 1 = 1.</p><p>67</p><p>Supondo que a propriedade seja válida até um certo n, vamos provar que é</p><p>verdadeira para n + 1, ou seja, que P(n) implica P(n + 1), que provará o que queremos.</p><p>Temos que:</p><p>F₁ + F₂ + F₃ + ... + Fn = Fn+₂ − 1</p><p>Mas, pela própria relação de recorrência: Fn+₂+Fn+₁ = Fn+₃. Assim, podemos</p><p>verificar que:</p><p>F₁ + F₂ + F₃ + ... + Fn + Fn+₁= Fn+₃ − 1</p><p>Portanto, P(n) implica P(n + 1) e pelo Princípio da Indução Finita podemos</p><p>afirmar que é verdadeira a proposição:</p><p>A seguir apresentaremos uma proposição que generaliza esse resultado para</p><p>toda sequência que tem como relação de recorrência a equação xn+₂ = xn+₁+ xn.</p><p>Proposição 3.4.2. Seja (xn) uma sequência tal que xn+₂ = xn+₁+ xn., para todo</p><p>n ∈ N. A soma dos n primeiros termos de (xn) é igual ao (n+2)-ésimo termo menos o</p><p>segundo termo. (FIBONACCI, 1202).</p><p>Prova: Vamos provar por indução em n o que queremos demonstrar:</p><p>Verificando o caso base da indução, para n = 1 a propriedade é verdadeira pois:</p><p>x₁ + x₂ = x₃ =⇒ x₁ = x₃− x₂</p><p>Supondo que a propriedade seja válida até um certo n, vamos provar que é</p><p>verdadeira para n + 1, ou seja, que P(n) ⇒ P(n + 1), que provará o que queremos.</p><p>Temos que: x₁ + x₂ + x₃ + ... + xn = xn+₂ − x₂.</p><p>68</p><p>Se somarmos xn+1 aos dois lados da igualdade, obteremos:</p><p>x₁ + x₂ + x₃ + ... + xn + xn+₁ = xn+₂ + xn+₁ − x₂.</p><p>Mas, pela própria relação de recorrência: xn+₂+xn+₁ = xn+₃. Assim, podemos</p><p>verificar que: x₁ + x₂ + x₃+ ... + xn + xn+₁ = xn+₃ − x₂.</p><p>Como P(n) ⇒ P(n + 1) podemos afirmar que é verdadeira a proposição:</p><p>13 CONGRUÊNCIAS QUADRÁTICAS</p><p>Nesta seção, vamos examinar se um inteiro é ou não um resíduo quadrático</p><p>módulo p primo a partir das congruências quadráticas x² ≡ a (mod p). Além disso,</p><p>exploraremos procedimentos e eficazes para alcançar esta finalidade, tais como o</p><p>Critério de Euler, o Símbolo de Legendre com suas propriedades e o Lema de Gauss.</p><p>(ARAUJO; RIBEIRO, 2013).</p><p>13.1 Resíduos Quadráticos</p><p>No conjunto Z∗p, onde p é um número primo maior que 2, alguns elementos</p><p>possuem uma característica especial: são equivalentes ao quadrado de algum outro</p><p>elemento de Z∗p, como o que acontece com 4 em Z∗₅, pois 4 ≡ 3² (mod 5).</p><p>Tais elementos são denominados resíduos quadráticos. Apresentaremos a</p><p>definição geral deste conceito e enunciaremos de forma breve algumas de suas</p><p>propriedades fundamentais.</p><p>Definição 1.1 Seja p > 2 um número primo e a ∈ Z∗p. Dizemos que a é um</p><p>resíduo quadrático módulo p se a ≡ b 2 (mod p)</p><p>para algum b ∈ Z∗p.</p><p>69</p><p>Por exemplo, em Z∗₇ temos os seguintes quadrados:</p><p>1² ≡ 1 (mod 7)</p><p>2² ≡ 4 (mod 7)</p><p>3² ≡ 9 ≡ 2 (mod 7)</p><p>Dizemos assim que 1, 2 e 4 são resíduos quadráticos em Z∗₇. Os demais</p><p>elementos, 3, 5 e 6, são resíduos não quadráticos módulo 7.</p><p>Observe que, para calcular os resíduos quadráticos módulo 7, tomamos os</p><p>quadrados apenas dos três primeiros elementos de Z∗₇. Por</p><p>que ignoramos os demais</p><p>elementos? Ora, é fácil verificar o seguinte:</p><p>4²≡ 16 ≡ 2 (mod 7)</p><p>5² ≡ 25 ≡ 4 (mod 7)</p><p>6²≡ 36 ≡ 1 (mod 7)</p><p>Obtivemos os mesmos resultados! Isto não é mera coincidência. Vejamos mais</p><p>um exemplo, em Z∗₁₁, tomando apenas os quadrados dos cinco primeiros elementos:</p><p>1² ≡ 1 (mod 11)</p><p>2² ≡ 4 (mod 11)</p><p>3² ≡ 9 (mod 11)</p><p>4²≡ 16 ≡ 5 (mod 11)</p><p>5²≡ 25 ≡ 3 (mod 11)</p><p>E agora, elevando ao quadrado os demais elementos:</p><p>6² ≡ 36 ≡ 3 (mod 11)</p><p>7² ≡ 49 ≡ 5 (mod 11)</p><p>8² ≡ 64 ≡ 9 (mod 11)</p><p>9² ≡ 81 ≡ 4 (mod 11)</p><p>10² ≡ 100 ≡ 1 (mod 11)</p><p>Mais uma vez, obtivemos os mesmos resíduos quadráticos: 1, 3, 4, 5 e 9.</p><p>Estamos vendo que, em Z∗₇, que possui seis elementos, temos exatamente três</p><p>resíduos quadráticos, e em Z∗₁₁, que possui dez elementos, são cinco resíduos</p><p>quadráticos. (ARAUJO; RIBEIRO, 2013). Podemos generalizar este fato, enunciando</p><p>o seguinte:</p><p>70</p><p>Ou seja, elevando ao quadrado dois elementos equidistantes dos extremos, o</p><p>resultado módulo p será o mesmo. Como Z∗p tem exatamente p − 1 elementos,</p><p>teremos (p − 1)/2 resíduos quadráticos, e a mesma quantidade de resíduos não</p><p>quadráticos. Assim, para determinar os quadrados em Z∗p, basta calcular a forma</p><p>reduzida de b² (mod p) para b = 1, 2, ...,(p − 1)/2. (ARAUJO; RIBEIRO, 2013).</p><p>13.2 Símbolo de Legendre e o Critério de Euler</p><p>Adrien−Marie Legendre (1752−1833) desenvolveu um símbolo para verificar se</p><p>uma congruência do tipo x2 ≡ a (mod p), com p primo possui solução simplificando os</p><p>cálculos e sendo uma possibilidade de os termos resíduos quadráticos e não-resíduos</p><p>possam ser denotados de modo muito conveniente, bem como útil.</p><p>Definição 1.3 Seja p um inteiro primo ímpar. Para um inteiro a define−se o</p><p>Símbolo de Legendre de a módulo p e denotamos por como sendo</p><p>71</p><p>É possível observar que na definição acima considera−se p ímpar uma vez que</p><p>qualquer número inteiro é um quadrado módulo 2. O próximo resultado, descoberto</p><p>por Euler possibilita o cálculo do Símbolo de Legendre. (ARAUJO; RIBEIRO, 2013).</p><p>Teorema 1.4 (Critério de Euler) Seja p > 2 um primo e a um inteiro. Então</p><p>Demonstração: Para a ≡ 0 (mod p) o resultado é evidente, de modo que</p><p>devemos supor p - a. Com isso, ao considerarmos primeiramente que a = 1 verifica−se</p><p>que a congruência x2 ≡ a (mod p) apresenta solução, pelo Teorema 1.1, e</p><p>consequentemente teremos y2 ≡ a (mod p) para algum y ∈ Z resultando em p divide</p><p>(y2−a). Mas, p não divide a, p não divide y2 e portanto, p não divide y. Concluímos</p><p>assim que (y, p) = 1 e assim, pelo Pequeno Teorema de Fermat, (Anexo B), yp−1 ≡ 1</p><p>(mod p), podemos escrever que</p><p>o que comprova o teorema para o caso em que = 1</p><p>Agora, mostremos para o caso em que = -1 ou seja, a não é um resíduo</p><p>quadrático de p e se s é um dos inteiros de {1,2,3,· · ·,p − 1} podemos admitir que,</p><p>pela Teoria das Congruências Lineares, existe uma solução s0 de sx ≡ a (mod p), com</p><p>s0também no conjunto {1,2,3, · · ·,p − 1}. Mas, s e s0 devem ser distintos</p><p>para evitarmos que s2 ≡ a (mod p), já que = -1. Então, os inteiros entre a e p</p><p>– 1 podem ser divididos em pares, s e s’, onde ss’≡ a (mod p) nos levará às</p><p>congruências</p><p>72</p><p>14 A LEI DA RECIPROCIDADE QUADRATICA</p><p>Sejam p e q primos ımpares distintos, de modo que ambos os símbolos de</p><p>Legendre e estão definidos. A questão que surge é, se conhecido o valor de</p><p>será que podemos determinar o valor de ? Ou mais geral, será que existe</p><p>alguma relação entre os valores destes símbolos? Uma relação básica entre estes</p><p>dois símbolos foi conjecturada experimentalmente por Euler em 1783 e</p><p>imperfeitamente provada por Legendre dois anos mais tarde. Usando estes símbolos,</p><p>Legendre enunciou esta relação através de uma elegante forma, a chamada Lei da</p><p>Reciprocidade Quadrática (ROCHA, 2015):</p><p>Para um número ímpar m temos que é par se m ≡ 1 (mod 4) e ímpar</p><p>se m ≡ 3 (mod 4). Assim o produto e ímpar se e só se p ≡ q ≡ 3 (mod 4) e</p><p>73</p><p>par se pelo menos um dentre p e q pertencer a classe 1 + 4Z. Logo, a lei da</p><p>reciprocidade nos diz que podemos trocar as posições p e q no símbolo de Legendre</p><p>se pelo menos um for da classe 1 + 4Z e mantemos a igualdade em relação ao símbolo</p><p>original. Mas caso ambos p e q pertençam à classe 3 + 4Z, o símbolo invertido troca</p><p>de sinal.</p><p>14.1 As Leis suplementares</p><p>Seja p um primo ímpar e n 6= ±1 um inteiro não divisível por p. Suponha ainda</p><p>que n tem a seguinte fatorização:</p><p>onde pi é um primo ímpar. Pelo corolário (1.1), para determinarmos o caráter</p><p>quadrático de n, precisamos conhecer apenas o caráter quadrático de cada um dos</p><p>fatores. Pela Lei da reciprocidade quadrática, conseguimos determinar facilmente o</p><p>símbolo de Legendre de cada pi. Mas a Lei não abrange o caso do primo ser par, ou</p><p>seja p = 2 e nem nos dá informação sobre o caráter da unidade −1. Para isso, as</p><p>próximas Leis, chamadas de suplementares, nos ajudarão a encontrar para quais</p><p>primos p os inteiros −1 e 2 são resíduos quadráticos, ficando completamente</p><p>conhecido o caráter quadrático de qualquer inteiro n em relação a um primo p.</p><p>14.2 O Lema de Gauss</p><p>Muitas provas da Lei da Reciprocidade Quadrática, estão sustentadas por um</p><p>importante resultado conhecido por Lema de Gauss, apresentado primeiramente para</p><p>a demonstração da famosa 3ª prova de Gauss. Embora este lema nos dê o caráter</p><p>quadrático de um inteiro n qualquer, ele é muito mais útil do ponto de vista teórico do</p><p>que como um algoritmo computacional. Antes de enunciá-lo e prová-lo, precisamos</p><p>estabelecer mais uma definição. (ROCHA, 2015).</p><p>74</p><p>Primeiramente, notemos que, no conjunto dos menores restos em valor</p><p>absoluto de S, nenhum número 1, 2, . . . aparece mais do que uma vez e nem com</p><p>outra escolha de sinal, pois, se isto ocorresse, ou dois elementos de S seriam</p><p>congruentes módulo p ou 0 seria, módulo p, a soma de dois elementos de S, e ambos</p><p>os eventos são impossíveis. O primeiro caso não pode ocorrer devido a propriedade</p><p>do cancelamento da aritmética modular e por sabemos que os números 1, 2, . . .</p><p>são incongruentes módulo p, e, no segundo caso, teríamos rk + jk ≡ 0 (mod p) para 1</p><p>≤ r, j ≤ donde r + j ≡ 0 (mod p), uma contradição. (ROCHA, 2015). Logo, o conjunto</p><p>dos menores restos em valor absoluto de S deverá ser da forma:</p><p>onde cada εi assume um dos valores 1 ou -1. Multiplicando juntos os elementos de S</p><p>e os elementos de T, nós temos que</p><p>75</p><p>De modo geral, em matemática, dentro da teoria dos números, a lei da</p><p>reciprocidade quadrática designa o teorema que relaciona a possibilidade de serem</p><p>solucionadas duas congruências de segundo grau relacionadas onde p e q são</p><p>números primos ímpares.</p><p>É importante salientar, que sem os números, não aprenderíamos a fazer contas</p><p>e não progrediríamos, os números são a ponte que une o conceito quantificador do</p><p>abstrato à sua respectiva correspondência com o concreto, estão presentes em</p><p>cálculos complexos ou no simples aprendizado da vida escolar, regem a economia</p><p>mundial e influenciam diretamente o comportamento humano, seja nos ponteiros do</p><p>relógio ou na contagem dos dias e anos que permitem as experiências de</p><p>amadurecimento e progresso, ainda que enquadrados no referencial de vida na Terra.</p><p>(SILVA, 2018).</p><p>Os números são símbolos que expressam valores, quantidades e auxiliam na</p><p>demonstração de cálculos matemáticos, sendo fundamentais no desenvolvimento dos</p><p>números para as realizações de contas, fechamento de negócios, entre outros</p><p>fatores. Números não estão presentes apenas nas ciências exatas, onde ao</p><p>analisarmos minuciosamente, veremos que os utilizaremos para todas as tarefas</p><p>cotidianas. (SILVA, 2018).</p><p>76</p><p>REFERÊNCIAS</p><p>BIBLIOGRAFIA BÁSICA</p><p>SANTOS, J. P. O. Introdução à Teoria dos Números, CMU, IMPA, Rio de</p><p>Janeiro,1998. Silva, Jhone Caldeira, Gomes,</p><p>Olímpio Ribeiro. Estruturas Algébricas</p><p>para Licenciatura: Introdução à Teoria dos Números. Brasília: Ed. Do Autor, 2008.</p><p>SHOKRANIAN, S.; SOARES, M.; GODINHO, H. Teoria dos Números, Brasília:</p><p>EdUnB, 1994.</p><p>BIBLIOGRAFIA COMPLEMENTAR</p><p>ANDRÉ, T. C. O sistema de numeração decimal no ensino inicial de matemática:</p><p>contribuições do ábaco e do material dourado. Revista Ideação, v. 11, n. 1, p. 99–110,</p><p>2009. Disponível em: http://e-revista.unioeste.br/index.php/ideacao/article/view/4941.</p><p>Acesso em: 30 set. 2020.</p><p>CAIXETA, S. B. Algoritmo da divisão de Euclides. 2016. 80 f. Dissertação (Meste</p><p>em Matemática) - Universidade de Brasília, Brasília, 2016. Disponível em:</p><p>https://repositorio.unb.</p><p>br/bitstream/10482/21158/1/2016_SusianeBezerraCaixeta.pdf. Acesso em: 30 set.</p><p>2020.</p><p>CAMPOS, E. de. A noção de congruência algébrica no curso de Matemática: uma</p><p>análise das respostas dos estudantes. 2009. Tese (Doutorado em Educação) -</p><p>Universidade Federal do Paraná, Curitiba, 2009. Disponível em:</p><p>http://www.ppge.ufpr.br/teses/ D09_campos.pdf. Acesso em: 8 out. 2020</p><p>CARDOSO, V. C. Materiais didáticos para as quatro operações. São Paulo: IME–</p><p>USP, 1992.</p><p>DOMINGUES, H. H.; IEZZI, G. Álgebra Moderna. 4. ed. São Paulo: Atual, 2003.</p><p>GONÇALVES, A. Introdução à álgebra. Rio de Janeiro: Impa, 2017.</p><p>77</p><p>HARDY, G. H. et al. An Introduction to the Theory of Numbers. 6th ed. Oxford:</p><p>Oxford University Press, 2009.</p><p>HEFEZ, A. Indução Matemática. OBMEP, Rio de Janeiro, 2009. Disponível em http://</p><p>www.obmep.org.br/docs/apostila4.pdf. Acesso em: 11 set. 2020.</p><p>HEFEZ, A. Curso de álgebra. Rio de Janeiro: Instituto de Matemática Pura e</p><p>Aplicada, 2016. v. 1.</p><p>IEZZI, G.; MURAKAMI, C. Conjunto-elemento-persistência. In: IEZZI, G.;</p><p>MURAKAMI, C. Fundamentos de matemática elementar. 9. ed. São Paulo: Saraiva</p><p>Didáticos, 2019. v. 1, cap. II, p. 18–38.</p><p>LIPSCHUTZ, S.; LIPSON, M. Matemática Discreta. 3 ed. Porto Alegre: Bookman,</p><p>2013.</p><p>MOTA, M. C.; CARVALHO, M. P. de. Os diferentes tipos de demonstrações: uma</p><p>reflexão para os cursos de licenciatura em matemática. Revista da Educação</p><p>Matemática da UFOP, v. I, 2011. Disponível em:</p><p>https://wdz.eng.br/WDK/MetodosDemonstracao.pdf. Acesso em: 24 set. 2020.</p><p>PREST, M. Y.; HUMPHREYS, J. F. Numbers Groups & Codes. 2th ed. Cambridge:</p><p>Cambridge University Press, 2004.</p><p>ROCHA, Laiz Valim da. A Lei da Reciprocidade Quadrática. Documento online,</p><p>2015. Acesso em 20 abril. 2021.</p><p>SALOMÃO, Crislaine Aparecida Ribeiro. História dos números. Documento online,</p><p>2019. Acesso em 20 abril. 2021.</p><p>SANTIAGO, Fábio. Números inteiros e indução matemática. SAGAH – Soluções</p><p>Educacionais Integradas, 2018.</p><p>SILVA, Cristiane da. Equações diofantinas e o teorema chinês do resto. SAGAH –</p><p>Soluções Educacionais Integradas, 2018.</p><p>78</p><p>SILVERMAN, J. H. A Friendly Introduction to Number Theory. 4th ed. New Jersey:</p><p>Pearson Education, 2011. WELLS, D. Prime Numbers – The Most Mysterious Figures</p><p>in Math. New Jersey: John Wiley & Sons, 2005.</p><p>STEFANI, Rafael. Múltiplos e divisores: MDC e MMC. SAGAH – Soluções</p><p>Educacionais Integradas, 2018.</p><p>de</p><p>representações gráficas ou tabelas, por meio de medidas e grandezas. Dessa maneira</p><p>percebemos que não podemos viver sem eles. Mas vem a curiosidade desde quando</p><p>os números existem?</p><p>A história dos números faz parte da história da humanidade na qual</p><p>encontramos extraordinárias realizações, ligadas diretamente a noção de número e</p><p>sistemas de numerações. Em todas as épocas da evolução humana, mesmo nas mais</p><p>atrasadas, encontra-se no homem, o sentido do número. Os números são tão</p><p>familiares que raramente pensamos como é que eles apareceram, mas não podemos</p><p>deixar-nos conduzir pelo pensamento de que uma Matemática simples tem</p><p>necessariamente uma história simples. (SALOMÃO, 2019).</p><p>2.1 Origens primitivas</p><p>A ideia de número pode ser representada pelos dedos de uma mão para indicar</p><p>um conjunto de um a cinco objetos e para representar duas mãos para contar até o</p><p>dez e se combinar os dedos dos pés para contar até vinte. Quando faltavam elementos</p><p>para contar nos dedos humanos, usava monte de pedras para representar um</p><p>conjunto, no início grupos de cinco pedras. “[...] Homem pré-histórico às vezes</p><p>registrava um número fazendo marcas num bastão ou pedaço de osso [...]” (BOYER,</p><p>1974, p. 3). Para compreendermos a complexidade de nosso sistema de numeração,</p><p>devemos analisar os sistemas de numerações já existentes. “Umas das mais antigas</p><p>é a dos egípcios, datada de 5500 anos. Quase na mesma época e próximo ao Egito,</p><p>desenvolveu-se uma civilização na Mesopotâmia, região que corresponde atualmente</p><p>ao Iraque [...]” (IMENES, 1999, p. 17).</p><p>Segundo Imenes (1999) como tínhamos civilizações, e como as pessoas</p><p>tinham que se alimentar, o comércio começou a progredir com barcos de mercadorias,</p><p>tecidos na qual navegam pelo mar Vermelho e Mediterrâneo e para ter as negociações</p><p>5</p><p>precisavam de produtos, pagamentos e como fazer isso sem os números, com isso e</p><p>outros itens necessários os números como na contagem de soldados, pagar impostos</p><p>cobrados da população, observou – se que os números era essenciais por esse motivo</p><p>cada civilização inventou um sistema de numeração.</p><p>2.2 Sistema de numeração Babilônico</p><p>Segundo Almeida (2007), foi na Mesopotâmia, (do grego, mesos e potamos</p><p>que significa “terra entre rios” - nome que os gregos deram ao território situado entre</p><p>as bacias dos rios Tigre e Eufrates), que as primeiras sociedades urbanas surgiram e</p><p>onde, um pouco antes do fim do IV milênio a.C., apareceu a primeira escrita. Esta</p><p>grande mudança na organização social teve consequências importantes na história</p><p>da Matemática.</p><p>Na cidade da Mesopotâmia, encontraram-se milhares de placas de barro que</p><p>havia registros na qual foi possível decifrar o sistema de numeração mesopotâmico.</p><p>Os babilônios recorreram a um sistema de numeração cuja base era 60 (sexagesimal),</p><p>utilizando-se apenas de dois símbolos, devendo esse sistema ser também posicional.</p><p>Os símbolos numéricos eram esculpidos em pequenas placas de argila, que serviam</p><p>de base de “impressão” da escrita cuneiforme.</p><p>Fonte: História dos Números, (SALOMÃO, 2018).</p><p>6</p><p>2.3 Sistema de numeração Egípcio</p><p>Os egípcios criaram um elaborado sistema de escrita, que incluía também uma</p><p>forma de registro numérico por volta de 3000 a.C, ou seja, mais ou menos ao mesmo</p><p>tempo que na Mesopotâmia.</p><p>O sistema egípcio de numeração utilizava a base dez, mas, tal como visto</p><p>para as culturas mesopotâmicas, eles não tinham nenhum símbolo para o</p><p>zero. Os números de 1 a 9 eram representados por uma respectiva</p><p>quantidade de traços verticais, sendo que cada símbolo poderia se repetir até</p><p>nove vezes. O valor de cada símbolo é sempre o mesmo, independente de</p><p>seu posicionamento. Para que se entendesse a quantidade ali representada,</p><p>utilizava-se a adição dos valores socialmente atribuídos a esses símbolos.</p><p>(SILVA, 2016, p. 30)</p><p>Segundo Silva (2016), a base do sistema de numeração hieroglífico é 10,</p><p>existindo símbolos para 1, 10, 100, 1 000, 10 000 e 1 000 000, como se poderá</p><p>observar na figura que se segue.</p><p>Fonte: GULLBERG,Jan. Mathematics, from the birth of numbers. Nova Iorque: W.W. Norton &</p><p>Company,1997</p><p>2.4 O Sistema Romano</p><p>Segundo Silva (2016) com o cenário mundial de Roma, os numerais ficaram</p><p>conhecidos por toda parte, pois sua escrita e seus monumentos utilizavam seu</p><p>sistema de numeração. Esse sistema estendeu a todo o império romano.</p><p>O sistema de numeração romano sofreu um longo processo de evolução.</p><p>Inicialmente, utilizavam apenas o princípio aditivo, sendo que um mesmo símbolo</p><p>podia ser repetido até, no máximo, 4 vezes, como os outros sistemas já utilizam do</p><p>princípio aditivo. Após estudos passaram a utilizar o princípio subtrativo, além de</p><p>permitir a repetição de um mesmo símbolo, no máximo, três vezes.</p><p>7</p><p>Esse sistema de numeração foi edificado como um sistema de agrupamento</p><p>simples de base dez, utilizando-se do princípio posicional subtrativo, para representar</p><p>algumas quantidades. Segundo Eves (1997), os símbolos gráficos a que este sistema</p><p>recorre, tal como os conhecemos hoje.</p><p>Os romanos desconheciam o zero, introduzido posteriormente pelos árabes de</p><p>forma que não existia nenhuma forma de representação deste valor pelo fato de terem</p><p>apenas como base o início do numeral o um. Usavam um sistema interessante para</p><p>representar os números. Utilizavam sete letras do alfabeto e a cada uma delas</p><p>atribuíam valores.</p><p>Segue tabela com os principais algarismos romanos:</p><p>2.5 Sistema de numeração indo – arábico</p><p>O sistema de numeração indo arábico, também conhecido como decimal, é o</p><p>mais utilizado no nosso dia a dia, foi criado aproximadamente 1500 anos pelos povos</p><p>hindus e foi divulgado na Europa pelos árabes, e passou por muitas modificações para</p><p>chegar no sistema que temos hoje. Existe dez símbolos para representar os números</p><p>que são: 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. Ele é utilizado no valor posicional.</p><p>8</p><p>3 NÚMEROS INTEIROS E INDUÇÃO MATEMÁTICA</p><p>Nesta seção, você vai aprender importantes conceitos matemáticos que vão</p><p>acompanhar você ao longo de sua formação. Inicialmente, você vai estudar a ideia</p><p>intuitiva de conjuntos e do pertencimento ou não de um elemento a um determinado</p><p>conjunto. Ainda no tema dos conjuntos, você vai estudar o conjunto dos números</p><p>inteiros, quais operações estão definidas sobre eles e quais são as propriedades</p><p>dessas operações.</p><p>Você também vai compreender um dos alicerces da matemática, que são as</p><p>demonstrações e seus tipos. Toda a matemática se fundamenta nesse tipo de</p><p>estratégia.</p><p>Por fim, você vai estudar um dos princípios da matemática mais simples, que é</p><p>o princípio da indução finita, que mostra propriedades que são verdadeiras para uma</p><p>sequência de objetos, sem a necessidade de provar cada uma delas.</p><p>3.1 Conjunto dos números inteiros ℤ</p><p>Para compreender o conjunto dos números inteiros ℤ, faz-se necessário</p><p>conhecer alguns conceitos iniciais que auxiliam na construção do pensamento</p><p>matemático. Como observam Iezzi e Murakami (2019), quando se considera a teoria</p><p>dos conjuntos, há três noções que são aceitas sem definição, a saber: conjunto,</p><p>elemento e pertinência entre um elemento e um conjunto.</p><p>Ainda segundo esses autores, na matemática, a noção de conjunto é</p><p>praticamente a mesma que se utiliza na linguagem comum, ou seja, tem-se o sentido</p><p>de agrupamento, classe; por exemplo: conjuntos dos meses de um ano, dos dias de</p><p>um mês, de vogais, entre tantos outros. Assim, considerando-se que A é um conjunto</p><p>e x é um elemento, se x pertence ao conjunto A, então se denota x ∈ A. Por sua vez,</p><p>se x não pertence ao conjunto A, então se escreve x ∉ A. A Figura abaixo também</p><p>demonstra essa notação de pertencimento</p><p>Na matemática, o conjunto numérico matemático mais elementar é o conjunto</p><p>dos números naturais, o qual é denotado por ℕ e possui como elementos {1,2,3,4…}.</p><p>Sobre esse conjunto, podem ser definidas</p><p>as operações de soma e multiplicação.</p><p>9</p><p>Representação do conjunto A e a notação de pertencimento do elemento a ao conjunto A</p><p>Fonte: SANTIAGO, 2018</p><p>Uma extensão do conjunto dos números naturais é o conjunto dos números</p><p>inteiros, o qual é denotado por ℤ. (SANTIAGO, 2018).</p><p>Os seguintes elementos compõem esse conjunto: ℤ = {… –3,–2,–1,0,1,2,3, …}.</p><p>Sobre esse conjunto, é possível distinguir três subconjuntos notáveis, a saber:</p><p> Conjunto dos números inteiros não negativos, denotado por ℤ+ = {0,1,2,3,…}</p><p>= N; portanto, o conjunto dos números naturais é um subconjunto de ℤ.</p><p> Conjunto dos números inteiros não positivos, denotados por ℤ– = {…,–3,–</p><p>2,–1,0}.</p><p> Conjunto dos inteiros não nulos, denotados por ℤ* = {…–3,–2,–1,1,2,3,…}.</p><p>Sobre o conjunto dos números inteiros ℤ, podem ser definidas operações de</p><p>adição e multiplicação, sendo para cada uma delas válidas as propriedades</p><p>apresentadas a seguir.</p><p>3.1.1 Propriedades do operador adição (+) sobre o conjunto dos números</p><p>inteiros ℤ</p><p>Dados quaisquer elementos a, b, c ∈ ℤ e o operador de adição (+), são válidas</p><p>as propriedades descritas a seguir.</p><p>Associação em relação à adição: para quaisquer elementos a, b, c</p><p>pertencentes ao conjunto dos números inteiros, matematicamente descrito por ∀ a, b,</p><p>c ∈ ℤ, é válida a seguinte igualdade:</p><p>(a + b) + c = a + (b + c), ∀ a, b, c ∈ ℤ</p><p>10</p><p>Comutativa em relação à adição: para quaisquer elementos a e b</p><p>pertencentes ao conjunto dos números inteiros, sendo matematicamente descrito por</p><p>∀ a, b ∈ ℤ, é válida a seguinte igualdade:</p><p>a + b = b + a, ∀ a, b ∈ ℤ</p><p>Elemento neutro da adição: existe e é único o elemento neutro da adição em</p><p>ℤ, de modo a se obter a igualdade a seguir:</p><p>a + 0 = 0 + a = a, ∀ a ∈ Z, ∃!0 ∈ ℤ</p><p>Simétrico da adição: para todo a ∈ ℤ, existe –a ∈ ℤ, tal que a igualdade a</p><p>seguir é mantida:</p><p>a + (–a) = (–a) + a = 0, ∀ a ∈ ℤ</p><p>3.1.2 Propriedades do operador multiplicação (∙) sobre o conjunto dos números</p><p>inteiros ℤ</p><p>Dados quaisquer elementos a, b, c ∈ ℤ e o operador de multiplicação (∙), são</p><p>válidas as propriedades descritas a seguir. (SANTIAGO, 2018).</p><p>Associativa da multiplicação: dados quaisquer a, b, c ∈ ℤ, é válida a</p><p>associatividade da multiplicação para esses elementos. Portanto, é válida a igualdade</p><p>a seguir:</p><p>(ab)c = a(bc), ∀ a, b, c ∈ ℤ</p><p>Comutativa da multiplicação: dados quaisquer a, b ∈ ℤ, é válida a</p><p>comutatividade da multiplicação para esses elementos. Portanto, é válida a igualdade</p><p>a seguir:</p><p>ab = ba, ∀ a, b ∈ ℤ</p><p>11</p><p>Elemento neutro da multiplicação: existe e é único o elemento neutro da</p><p>multiplicação em ℤ, para ∀ a ∈ ℤ, sendo válida a igualdade a seguir:</p><p>a ∙ 1 = 1 ∙ a = a, ∀ a ∈ Z, ∃!1 ∈ ℤ</p><p>Distributiva da adição em relação à multiplicação: dados quaisquer a, b, c</p><p>∈ ℤ, bem como os operadores de adição (+) e de multiplicação (∙), é válida a</p><p>distribuição da multiplicação em relação à adição à esquerda e à direita. Portanto, é</p><p>válida a igualdade a seguir:</p><p>a ∙ (b + c) = a ∙ b + a ∙ c = b ∙ a + c ∙ a = (b + c) ∙ a, ∀ a, b, c ∈ ℤ</p><p>3.1.3 Divisibilidade no conjunto dos números inteiros ℤ</p><p>Sobre o conjunto dos números inteiros ℤ, é possível definir o conceito de divisor.</p><p>Nesse sentido, diz-se que a ∈ ℤ é divisor inteiro de b ∈ ℤ, e se denota por a|b quando</p><p>existe c ∈ ℤ tal que seja válida a seguinte igualdade: ca = b. (SANTIAGO, 2018).</p><p>Portanto, matematicamente, tem-se:</p><p>a|b ⇔ (∃ c ∈ ℤ|c ∙ a = b)</p><p>Por exemplo:</p><p>–2|–14 ⇔ 7(–2) = –14</p><p>3.2 Conectivos lógicos</p><p>Na matemática, você vai encontrar essencialmente quatro tipos de conectivos,</p><p>a saber:</p><p>12</p><p> o conectivo “e”, denotado por “∧”;</p><p> o conectivo “ou”, denotado por “∨”;</p><p> o conectivo “se”, matematicamente denotado por “→”; e</p><p> o conectivo “se e somente se”, denotado por “↔”.</p><p>A partir dos conectivos apresentados, e considerando-se as proposições “p” e</p><p>“q”, obtêm-se a conjunção “p ∧ q", a disjunção “p ∨ q”, a condicional “p → q” e a</p><p>bicondicional “p ↔ q”. A seguir, você vai estudar cada uma delas.</p><p>3.2.1 Conjunção</p><p>Sejam “p” e “q” duas proposições; ao se colocar o conectivo “e” denotado por</p><p>“∧” entre elas, obtém-se uma nova proposição denominada conjunção entre “p” e “q”,</p><p>a qual é denotada por “p ∧ q”. Por exemplo:</p><p>p: 3 > 0, q: 3 ≠ 1, p ∧ q: 3 > 0 e 3 ≠ 1</p><p>A conjunção “p ∧ q” será verdadeira apenas se ambas as proposições “p” e “q”</p><p>são verdadeiras. Se uma delas for falsa, isso implica que “p ∧ q” é falso. (SANTIAGO,</p><p>2018). A partir do exposto, obtém-se a tabela verdade expressa no Quadro a seguir:</p><p>Fonte: SANTIAGO, 2018.</p><p>3.2.2 Disjunção</p><p>Assim como para a conjunção, considere “p” e “q” duas proposições. Ao se</p><p>colocar o conectivo “ou”, denotado por “∨”, entre elas, obtém-se uma nova proposição</p><p>denominada disjunção entre “p” ou “q”, a qual é denotada por “p ∨ q”. (SANTIAGO,</p><p>2018). Por exemplo:</p><p>13</p><p>p: 4 > 0, q: 4 > 2, p ∨ q: 4 > 0 ou 4 > 2</p><p>A disjunção “p ∧ q” será verdadeira se ao menos uma das proposições “p” e “q”</p><p>forem verdadeiras, e “p ∧ q” será falsa apenas se as duas proposições “p” e “q” forem</p><p>falsas. A partir do exposto, obtém-se a tabela verdade apresentada no Quadro abaixo:</p><p>Fonte: SANTIAGO, 2018.</p><p>3.2.3 Condicional</p><p>Considere as proposições “p” e “q”. Ao se colocar o condicional “→” entre elas,</p><p>é obtida uma nova proposição, dada por “p → q”, que se lê: se “p”, então “q”; portanto,</p><p>“p é condição necessária para q” ou “q é uma condição suficiente para p”. (SANTIAGO,</p><p>2018). Por exemplo:</p><p> p: quatro é divisor de oito (4|8);</p><p> q: oito é divisor de quarenta (8|40);</p><p> p → q: se quatro é divisor de oito, então quatro é divisor de quarenta.</p><p>O condicional “p → q” assume o valor de falso apenas quando “p” é verdadeira</p><p>e “q” é falsa; caso contrário, “p → q” é verdadeiro. A partir do exposto, obtém-se a</p><p>tabela verdade apresentada no Quadro abaixo:</p><p>Fonte: SANTIAGO, 2018.</p><p>14</p><p>3.2.4 Bicondicional</p><p>Considere “p” e “q” duas proposições. Ao se colocar o conectivo “↔” entre elas,</p><p>obtém-se uma nova proposição dada por “p ↔ q”, a qual se lê: “p” se e somente se</p><p>“q”; ou “p” é uma condição necessária e suficiente para “q”; ou, ainda, se “p”, então “q”</p><p>é reciprocamente. (SANTIAGO, 2018). Por exemplo:</p><p>p: 2|12, q: 27|127, p ⇔ q: 2|12 ⇔ 27|127</p><p>O bicondicional “↔” assume valor verdadeiro apenas quando ambas as</p><p>proposições “p” e “q” são verdadeiras, ou quando ambas simultaneamente são falsas.</p><p>Caso contrário, o condicional “↔” é falso. A partir do exposto, obtém-se a tabela</p><p>verdade mostrada no Quadro a seguir:</p><p>Fonte: SANTIAGO, 2018.</p><p>3.3 Princípio da indução matemática</p><p>Neste tópico, você vai aprender um dos princípios mais importantes da</p><p>matemática, conhecido como princípio da indução finita. Este é empregado para</p><p>demostrar que uma sequência de proposições P(1), P(2), …, P(n) é verdadeira sem</p><p>que seja necessário realizar a prova para cada uma delas.</p><p>De acordo com Mota e Carvalho (2011), ao fazer uso do princípio da indução</p><p>matemática, basta mostrar que P(1) é verdadeira; em seguida, deve-se supor que P(k)</p><p>é verdadeira e, por fim, mostrar que P(k + 1) é verdadeira. Nesse tipo de</p><p>demonstração, P(k) é denominada hipótese de indução.</p><p>Para compreender como funciona o princípio da indução, suponha que você</p><p>queira demonstrar que a sequência:</p><p>15</p><p>é verdadeira para todo n ∈ ℕ. Assim, inicialmente, você deve mostrar que P(1) é</p><p>verdadeira; assim:</p><p>portanto, a igualdade é válida. Como segundo passo, você deve supor que a</p><p>propriedade é válida para uma quantidade, assumindo assim a hipótese de indução:</p><p>No terceiro e último passo, você deve mostrar que ela é válida para P(k + 1). Assim,</p><p>tem-se:</p><p>Dessa forma, ao assumir P(k) como verdadeira, foi possível provar que P(K + 1) é</p><p>verdadeira, concluindo assim a demonstração.</p><p>De acordo</p><p>com Hefez (2009), a demonstração mostrada no exemplo anterior</p><p>foi feita pela primeira vez por Francesco Maurolycos no ano de 1575. É importante</p><p>compreender que a indução matemática é diferente da indução empírica. Como</p><p>observa Hefez (2009), essa última, após um número necessariamente finito de</p><p>experimentos, permite formular leis gerais que regem o movimento. Tais leis são</p><p>válidas até que seja provado o contrário. Já uma demonstração por indução</p><p>matemática consiste em determinar que certa sentença aberta sobre os naturais é</p><p>sempre verdadeira.</p><p>16</p><p>O primeiro uso conhecido da indução matemática é o trabalho do matemático</p><p>Francesco Maurolico (1494–1575), no século XVI. Maurolico escreveu</p><p>exaustivamente sobre os trabalhos de matemáticos clássicos e fez muitas</p><p>contribuições em geometria e ótica. Em seu livro, Arithmeticorum Libri Duo, Maurolico</p><p>apresentou várias propriedades de números inteiros juntamente com as</p><p>demonstrações dessas propriedades. Para demonstrar algumas dessas</p><p>propriedades, ele desenvolveu o método de indução matemática. Seu primeiro uso da</p><p>indução matemática em seu livro foi para demonstrar que a soma dos primeiros n</p><p>números inteiros positivos e ímpares é igual a n² . (ROSEN, 2009).</p><p>17</p><p>4 DIVISIBILIDADE</p><p>Nesta seção, você vai aprender conceitos fundamentais da álgebra elementar</p><p>que constituem um poderoso conjunto de ferramentas matemáticas empregadas na</p><p>obtenção de teorias mais sofisticadas. Em um primeiro momento, você vai aprender o</p><p>algoritmo euclidiano da divisão, verificando como este amplia o conceito de divisão</p><p>sobre o conjunto dos números inteiros.</p><p>Em um segundo momento, você vai estudar as propriedades do sistema de</p><p>numeração decimal, este que é um dos mais importantes sistemas de numeração</p><p>adotados atualmente.</p><p>4.1 O algoritmo euclidiano</p><p>Para estudar o algoritmo da divisão euclidiana, é importante recordar os</p><p>conceitos referentes à divisão no conjunto de números inteiros ℤ, o que será feito</p><p>neste primeiro momento.</p><p>Dado um número inteiro qualquer, matematicamente denotado por ∀a ∈ ℤ, diz-</p><p>se que esse inteiro a é divisor do número inteiro b, ou, de forma análoga, que o inteiro</p><p>b é divisível por a se existe outro número inteiro c, tal que b = a ∙ c. (SANTIAGO,</p><p>2018).</p><p>Se a|b e a ≠ 0, o número c ∈ ℤ da igualdade b = ac é denominado quociente de</p><p>a por b e é denotado por b/a.</p><p>Exemplo:</p><p>O número inteiro 2 divide o inteiro 10, pois existe um c ∈ ℤ tal que b = a ∙ c, em</p><p>que se tem a = 2, b = 10 e c = 5; portanto, 10 = 2 ∙ 5.</p><p>18</p><p>Segundo Domingues e Iezzi (2003), no conjunto Z, a relação x|y, como</p><p>apresentada anteriormente, tem as propriedades a seguir, cujas demonstrações</p><p>podem ser encontradas nos referidos autores.</p><p>1. Seja a ∈ ℤ, então a|a (reflexividade).</p><p>2. Dados a, b ∈ ℤ tal que a, b ≥ 0, se a|b e b|a, então a = b.</p><p>3. Dados ∀a, b, c ∈ ℤ, se a|b e b|c, então a|c (transitividade).</p><p>4. Dados ∀a, b, c ∈ ℤ, se a|b e a|c, então a|(bx + cy) ∀x, y ∈ ℤ.</p><p>5. Dados ∀a, b, c, d ∈ ℤ, se a|b e c|d, então ac|bd.</p><p>Como observado por Domingues e Iezzi (2003), existe uma infinidade de pares</p><p>de números inteiros tais que nenhum deles é divisor um do outro — por exemplo, 2</p><p>não é divisor de 5, nem 5 é divisor de 3. Assim, o algoritmo da divisão euclidiano que</p><p>você vai estudar a seguir estabelece uma divisão com resto. Porém, antes da</p><p>apresentação desse teorema, considere o lema a seguir.</p><p>Lema: dados a, b ∈ ℤ, sendo a ≥ 0 e b > 0, então existem q, r ∈ ℤ, tais que a =</p><p>bq + r, sendo 0 ≤ r < b.</p><p>A demonstração do lema apresentado pode ser encontrada em Caixeta (2016).</p><p>Como você verá a seguir, o teorema da divisão de Euclides amplia os resultados</p><p>apresentados por esse lema.</p><p>4.2 Teorema do algoritmo da divisão de Euclides</p><p>Dados a, b ∈ ℤ, sendo b ≠ 0, então existem q, r ∈ ℤ únicos, tais que a = bq + r,</p><p>sendo 0 ≤ r < |b|. Sendo a matemática uma ciência formal, ela requer que todo teorema</p><p>seja demostrado. Assim, a seguir, você vai verificar a demonstração desse teorema,</p><p>como feita por Caixeta (2016).</p><p>4.2.1 Demonstração do teorema do algoritmo da divisão de Euclides</p><p>A demonstração do teorema da divisão de Euclides é feita considerando-se</p><p>dois casos separados. Uma vez que o teorema afirma que 0 ≤ r < |b|, deve-se</p><p>considerar o caso em que b > 0 e aquele em que b < 0. Assim, tem-se as condições</p><p>descritas a seguir.</p><p>19</p><p> Para b > 0:</p><p>■ se a > 0, o lema anteriormente apresentado garante a ocorrência do</p><p>teorema.</p><p>■ se a < 0, é possível determinar por meio do lema anteriormente</p><p>apresentado q₁ e r₁, tais que |a| = b ∙ q₁+ r₁ , 0 ≤ r₁ < b. No caso em que r₁ =</p><p>0, tem-se –|a| = a = b(q₁) + 0. Portanto, q = –q₁ e r = 0 satisfazem a condição</p><p>do teorema. Considerando-se agora r₁ > 0, tem-se:</p><p>■ Uma vez que 0 < b – r₁ < b, então q = –q₁ – 1 e r = b – r₁, o que satisfaz</p><p>as condições do teorema.</p><p> Para b < 0:</p><p>■ Para ∀a ∈ ℤ, é possível determinar q₁ e r₁, tais que a = |b| ∙ q₁ + r₁, 0</p><p>≤ r₁ < |b|. No caso em que b < 0, então |b| = –b; logo, a = |b| ∙ q₁ + r₁ =</p><p>(–b) ∙ q₁+ r₁ = (b) ∙ (–q₁) + r₁. Portanto, q = –q₁ e r = r₁, que satisfazem</p><p>as condições do teorema.</p><p>Até este ponto, você aprendeu a demonstrar a existência de q e r; no entanto,</p><p>para que a demonstração esteja completa, faz-se necessário provar a unicidade de</p><p>ambos. De fato, a = b ∙ q + r = a = b ∙ q₁ + r₁. (SANTIAGO, 2018). Assumindo sem</p><p>perda de generalidade que r1 ≥ r, tem-se que (q – q₁)b = r₁ – r; uma vez que |b| > r₁,</p><p>tem-se r₁ – r < |b|. Por sua vez, (q – q₁)b = r₁ – r ⇒ 0 ≤ |q – q₁ ||b| < |b|. Como |b| > 0,</p><p>tem-se que 0 ≤ |q – q₁ | < 1. Como entre 0 e 1 não há outros números inteiros, tem-se</p><p>|q – q₁| = 0 ⇒ q = q₁. Assim,</p><p>O que demonstra a unicidade de q e r.</p><p>20</p><p>Exemplo 1</p><p>Determine o número natural que, quando dividido por 7, resulta em um quociente 4 e</p><p>resto o maior possível.</p><p>Solução</p><p>A fim de se determinar o maior resto possível, é necessário revisitar o teorema, que</p><p>diz: dados a, b ∈ ℤ, sendo b ≠ 0, então existem q, r ∈ ℤ únicos, tais que a = bq + r,</p><p>sendo 0 ≤ r < |b|. Considerando-se ℤ+, tem-se que 0 ≤ r < 7. Logo, os únicos valores</p><p>que podem ser assumidos por r são {0,1,2,3,4,5,6}. Voltando com as informações do</p><p>exemplo, tem-se: a = 7 ∙ 4 + 6 ⇒ a = 34.</p><p>Exemplo 2</p><p>Determine os valores de p e q de modo que, para A = 720 e B = 2ᴾ ∙ 5ɋ, MDC (A, B)</p><p>= 8.</p><p>Solução</p><p>Inicialmente, deve-se fatorar o número 720. Dessa forma, tem-se: A = 720 = 2⁴∙ 3² ∙</p><p>5. Além disso, você sabe que: MDC(A, B) = 8 = 2ᶟ . Considerando-se B = 2ᴾ ∙ 5ɋ, é</p><p>possível afirmar que p = 3. Dessa forma, 2ᶟ passa a ser comum entre os dois termos.</p><p>Como o 5 não aparece no MDC, a única alternativa para q é este ser zero, pois 5⁰ =</p><p>1.</p><p>Fonte: https://blog.faspec.edu.br/</p><p>21</p><p>4.3 Sistema de numeração decimal</p><p>Neste tópico, você vai aprender os principais conceitos envolvendo o sistema</p><p>de numeração decimal. No entanto, faz-se necessário incialmente compreender o</p><p>significado da palavra sistema. Como afirma André (2009), a palavra “sistema”</p><p>designa uma forma de organizar ou sistematizar algo a fim de se chegar a resultados</p><p>favoráveis. Ainda segundo o referido autor, ela também pode ser entendida como a</p><p>relação entre elementos que formam uma totalidade.</p><p>Segundo Domingues e Iezzi (2003), o primeiro sistema decimal posicional data</p><p>do século XV a.C., tendo origem na China. No entanto, esse sistema tinha</p><p>características diferentes do atual e, apesar de ter apresentado algumas evoluções</p><p>ao longo do tempo — como um símbolo para o zero, ele não prosperou.</p><p>Como observa Cardoso (1992), coube aos hindus o desenvolvimento do</p><p>sistema de numeração decimal na forma como o conhecemos, por volta do ano de</p><p>400 d.C. O povo hindu reuniu as características existentes nos sistemas numéricos</p><p>de outros povos em um único sistema; assim, foram eles os responsáveis</p><p>por reunir</p><p>os 10 símbolos utilizados para representar qualquer quantidade.</p><p>De acordo com André (2009), a partir da invasão da Europa e por meio do</p><p>comércio, os árabes espalharam pelo mundo os símbolos hindus, os quais evoluíram</p><p>até os dias atuais. Ainda segundo o referido autor, a estrutura do sistema de</p><p>numeração indo-arábico garante a realização de operações mais facilmente, uma vez</p><p>que permite representar qualquer quantidade de forma fácil. As características desse</p><p>sistema podem ser sintetizadas como apresentado a seguir.</p><p> No sistema decimal de numeração, são utilizados somente 10 símbolos, a</p><p>fim de representar toda e qualquer quantidade; esses símbolos são 0, 1, 2, 3, 4, 5, 6,</p><p>7, 8, 9.</p><p> O símbolo 0 indica a ausência de quantidade em uma determinada ordem.</p><p> O sistema de numeração decimal é multiplicativo, uma vez que o valor</p><p>posicional é obtido via multiplicação.</p><p> O sistema de numeração decimal é aditivo, pois o valor total de um número</p><p>é obtido por meio de uma adição.</p><p>22</p><p>Como observam Domingues e Iezzi (2003), o resultado apresentado</p><p>anteriormente é uma consequência do algoritmo euclidiano da divisão. Os autores</p><p>justificam essa afirmação supondo n ∈ ℕ, tal que n ≥ 10 — assim, n < 10 é imediato.</p><p>Partindo da suposição anterior, aplica-se o algoritmo de Euclides a esse número que</p><p>contém n como dividendo e 10 como divisor. Assim, tem-se: n = 10 ∙ q + r, sendo 0 ≤</p><p>r ≤ 9</p><p>Se 0 ≤ q ≤ 9, a justificativa está encerrada, uma vez que a igualdade dada por</p><p>n = 10 ∙ q + r está em conformidade com o enunciado, pois 0 ≤ q e r ≤ 9. Caso se tenha</p><p>q > 9, deve-se então aplicar novamente o algoritmo da divisão euclidiana, no entanto,</p><p>tendo agora q como dividendo e 10 como divisor, obtendo-se, assim, q = 10 ∙ q₁ + r₁,</p><p>sendo 0 ≤ r₁ ≤ 9. Então, n = 10 ∙ q + r é escrito com o auxílio do resultado obtido por n</p><p>= 10 ∙ (10 ∙ q₁ + r₁) + r. Caso se tenha 0 ≤ q₁ ≤ 9, a justificação está encerrada, uma</p><p>vez que 0 ≤ r, r₁ e q₁ ≤ 9. Caso contrário, aplica-se o algoritmo a q₁ e 10, e assim</p><p>sucessivamente.</p><p>23</p><p>5 NÚMEROS PRIMOS</p><p>Os números primos são números que podem ser divididos por apenas dois</p><p>divisores: o número um e ele mesmo.</p><p>Inicialmente, relembraremos um pouco sobre conjuntos numéricos,</p><p>especificamente o conjunto Z dos números inteiros, no qual estão todos os números,</p><p>inteiros, negativos e positivos.</p><p>ℤ = {... –3, –2, –1, 0, 1, 2, 3, 4, ...}</p><p>Entre os elementos dos números inteiros, assim como acontece em outros</p><p>conjuntos numéricos, podemos facilmente separar os números pares dos números</p><p>ímpares. O conjunto dos números pares e o conjunto dos números ímpares são</p><p>subconjuntos dos números inteiros. (STEFANI, 2018).</p><p>Por definição, um número par é aquele múltiplo de 2, inclusive o número 0</p><p>(zero), ou todo número par é divisível por 2. Contudo, todo número ímpar não é</p><p>múltiplo de 2. Assim, o subconjunto de Z formado pelos números pares é:</p><p>{... –6, –4, –2, 0, 2, 4, 6 ...}</p><p>Analogamente, o subconjunto de Z composto por números ímpares é:</p><p>{... –5, –3, –1, 1, 3, 5 ...}</p><p>Outra “classificação” dentro do conjunto dos números inteiros, Z, refere-se aos</p><p>números primos. Um número n inteiro, diferente de 1, é primo se seus divisores forem,</p><p>exclusivamente, ±1 e ± n (LIPSCHUTZ; LIPSON, 2014).</p><p>Por exemplo, o número 2 é um número primo, pois somente na divisão por ±1</p><p>e ± 2 temos uma divisão exata. Da mesma forma acontece com os números –2, 3,</p><p>–3, 5, –5, 7, –7, 11, –11, 13, –13.</p><p>Entretanto, diversos outros números no conjunto também são números primos,</p><p>como os exemplos descritos a seguir.</p><p>24</p><p>Da sequência dos seguintes números, determine qual, ou quais, é ou são</p><p>número(s) primo(s):</p><p>27, 32, 41, 73, 89, 109</p><p> 27 é um número divisível por ±1, ±3, ±9, ±27, portanto não é um número</p><p>primo;</p><p> 32 é divisível por ±1, ±2, ±4, ±8, ±16 e ±32, portanto não é um número primo;</p><p> 41 é divisível por ±1 e ±41, portanto é um número primo;</p><p> 73 é divisível por ±1 e ±73, portanto é um número primo;</p><p> 89 é divisível por ±1 e ±89, portanto é um número primo;</p><p> 109 é divisível por ±1 e ±109, portanto é um número primo.</p><p>Ainda, pode-se determinar diversos outros números em Z que são números</p><p>primos.</p><p>Em outras palavras, um número positivo p é primo se ele tem exatamente dois</p><p>divisores positivos — 1 e p (HARDY et al., 2009). Dessa definição, extrai-se que 1 não</p><p>é primo, uma vez que ele não tem dois divisores positivos distintos. Logo, o menor</p><p>número primo é 2, e ele é o único número primo par, já que qualquer outro número</p><p>inteiro par n tem pelo menos três divisores distintos: 1, 2 e n.</p><p>Para compreender as propriedades dos números primos com mais clareza e</p><p>precisão, é útil definir uma notação para expressar a relação de divisibilidade entre</p><p>números. Nesse sentido, sejam a e b números inteiros com a ≠ 0, suponha que ac =</p><p>b para algum inteiro c. A afirmação de que a divide b ou de que b é divisível por a será</p><p>denotada por a | b. Isso é equivalente a dizer que b é um múltiplo de a ou que a é um</p><p>fator ou divisor de b.</p><p>25</p><p>5.1 Teorema fundamental da aritmética</p><p>Não é incomum encontrar na literatura a noção de que os números primos</p><p>podem ser considerados como “blocos de construção” a partir dos quais os demais</p><p>números são gerados (isto é, números inteiros maiores que um). Indo mais além, eles</p><p>também são tratados como blocos elementares sobre os quais toda a teoria dos</p><p>números é fundamentada (SILVERMAN, 2011, tradução nossa). O próximo resultado,</p><p>comumente conhecido como teorema fundamental da aritmética e enunciado em</p><p>conformidade com Prest e Humphreys (2004, tradução nossa), traz essa noção dos</p><p>números primos como elementos geradores dos demais inteiros positivos.</p><p>Teorema fundamental da aritmética: Todo número inteiro positivo n maior ou</p><p>igual a 2 pode ser escrito na forma:</p><p>n = p₁ p₂ ... pr</p><p>onde os inteiros p₁, p₂ ... pr são números primos (os quais não são necessariamente</p><p>distintos) e r ≥ 1. Essa fatoração é única, no sentido de que se também existir:</p><p>n = q₁ q₂ ... qs</p><p>onde q₁, q₂ ... qs são números primos, então r = s, e é possível renumerar cada qi de</p><p>tal forma que qi = pi para i = 1, 2, ..., r. Em outras palavras, a menos que haja</p><p>rearranjos, há apenas uma maneira de se escrever um número inteiro positivo como</p><p>produto de números primos.</p><p>Outra maneira mais sucinta de apresentar o mesmo teorema foi indicada por</p><p>Lipschutz e Lipson (2013), a saber: todo número n > 1 pode ser unicamente expresso</p><p>(em termos de ordem) como um produto de primos distintos. Então, n pode ser</p><p>expresso de maneira única como:</p><p>n = p₁ᵐ ¹ p₂ᵐ ¹ ... pr ᵐ ʳ</p><p>onde cada mi é positivo, e p₁ < p₂ < ... < pr. Essa fatoração é conhecida como</p><p>decomposição canônica de n.</p><p>26</p><p>Demonstração (teorema fundamental da aritmética): A demonstração será feita</p><p>em duas partes, conforme apresentado por Domingues e Iezzi (2003). Primeiramente,</p><p>será mostrado que todo inteiro n positivo maior ou igual a 2 pode ser decomposto</p><p>como um produto de primos. Para n = 2, não há o que ser provado, já que 2 é primo.</p><p>Se n for maior que 2, então uma possibilidade é que n seja primo. Nesse caso, ele</p><p>tem uma fatoração, com apenas um fator, conforme requerido pelo teorema. Caso n</p><p>não seja primo (segunda possibilidade), pelo lema 2 ele possui um divisor primo</p><p>positivo p1 que é o menor dentre os seus divisores. Logo, n pode ser escrito como um</p><p>produto p1 q1 ∈ ℕ (como n e p1 são positivos, q1 também é positivo). Dessa</p><p>decomposição, dois casos podem surgir:</p><p>a) se q₁ = 1, então a demonstração está concluída, já que n = p₁;</p><p>b) se q₁ > 1, então uma mesma decomposição análoga à feita para n pode ser</p><p>conduzida para q₁.</p><p>De fato, pelo lema 2, q₁ pode ser fatorado em um produto p₂ q₂ ∈ ℕ, onde p₂ é</p><p>primo e q₂ < q₁ . Nesse caso, n já seria formado pela decomposição n = p₁ p₂ q₂.</p><p>Iterativamente,</p><p>sucessivas fatorações de qr podem ser obtidas até que qr seja igual a</p><p>1, o que põe fim às decomposições. Ao término desse processo, tem-se que n = n =</p><p>p₁ p₂ ... pr, conforme objetivado pela primeira parte da demonstração.</p><p>A segunda parte visa a demonstrar a unicidade da decomposição de n em</p><p>números primos. Suponha que existam duas fatorações de n em inteiros primos, ou</p><p>seja, n = p₁ p₂ ... pr = q₁ q₂ ... qs . Para simplificar a notação, ambas as decomposições</p><p>serão denotadas por Pr = p₁ p₂ ... pr e Qs = q₁ q₂ ... qs . Como p₁ divide Q₁, pelo lema</p><p>1 tem-se que p₁ divide pelo menos um de seus fatores. Suponha que p₁ | q₁ . Como</p><p>q₁ é primo e, portanto, seu único divisor primo positivo é ele mesmo, então p₁= q₁.</p><p>Nesse caso, o fator p₁ pode ser cancelado tanto de Pr como de Qs, resultando em</p><p>Pr‒₁ = p₂ p₃ ... pr e Qs‒₁ = q₂ q₃ ..., qs . De maneira análoga, o mesmo processo pode</p><p>ser feito para o fator p₂, o que resultará em Pr‒₂ = p₃ p₄ ... pr e Qs‒₂= q₃ q₄ ..., qs, e,</p><p>assim, de maneira iterativa, cada fator de Pr é cancelado com o respectivo valor de</p><p>Qs resultando em P₀ = 1 = Q₀ e cada fator de Pr sendo igual a um fator de Qs. Logo,</p><p>Pr = Qs.</p><p>27</p><p>É importante observar que a primeira parte da prova é feita de forma eficiente,</p><p>particularmente em função da aplicação do lema 2. Porém, é interessante dar atenção</p><p>à simplicidade da ideia subjacente, ainda que o lema 2 não seja empregado. De fato,</p><p>se um inteiro n não for primo, o processo de demonstração se inicia com sua fatoração</p><p>como ab. Se a não é primo, ele deve ser fatorado, assim como b. Esse passo deve</p><p>ser iterativamente repetido, isto é, deve-se continuar dividindo quaisquer fatores que</p><p>não sejam primos. (RODRIGUES, 2018).</p><p>Naturalmente, esse processo terá fim, tendo em vista que os inteiros</p><p>produzidos como resultado das fatorações estão diminuindo, e cada fatoração fornece</p><p>números estritamente menores. Então, eventualmente, o processo para com um</p><p>produto de primos. A Figura abaixo apresenta uma descrição gráfica desse processo,</p><p>tomando como exemplo a fatoração do número 588 = 4 × 147 = (2 × 2) × (7 × 21) = (2</p><p>× 2) × (7 × (3 × 7)).</p><p>Decomposição de 588 por fatorações sucessivas.</p><p>Fonte: Prest e Humphreys (2004, tradução nossa).</p><p>28</p><p>Já a segunda parte da prova é baseada na observação de que, se um primo</p><p>divide um lado da equação, ele divide o outro, então, podemos cancelá-lo de cada</p><p>lado. Esse processo continua e só pode parar com a equação 1 = 1. Portanto, deve</p><p>haver o mesmo número de primos e, de fato, os mesmos primos em cada lado da</p><p>equação original.</p><p>Uma importante conclusão que pode ser derivada do teorema fundamental da</p><p>aritmética é também conhecida como segundo teorema de Euclides — o lema de</p><p>Euclides apresentado previamente é conhecido como primeiro teorema de Euclides.</p><p>(RODRIGUES, 2018).</p><p>Segundo teorema de Euclides: Existem infinitos números primos.</p><p>Demonstração (segundo teorema de Euclides): Suponha, por absurdo, que</p><p>P = p₁, p₂, ..., pm corresponda à lista de todos os números primos existentes — ou</p><p>seja, não existe nenhum outro número primo que não esteja em P. Seja o número N</p><p>= (p₁ p₂ ... pm) + 1. É importante observar que N tem resto 1 quando dividido por</p><p>qualquer primo pertencente a P. Porém, decorre do teorema fundamental da</p><p>aritmética que N tem um primo divisor p. Como p divide N, p não pode ser igual a</p><p>nenhum primo de P., Porém, a existência de um primo p ∉ P contradiz a hipótese de</p><p>que P contém todos os primos existentes. Portanto, existem infinitos números primos.</p><p>Cabe ressaltar que essa prova do segundo teorema de Euclides busca mostrar</p><p>como, dado qualquer conjunto finito de primos, é possível construir um número (≥ 2)</p><p>que não é divisível por nenhum deles e que, portanto, deve ter um fator primo que não</p><p>está presente no conjunto original. Outro detalhe relevante é que o inteiro N definido</p><p>na demonstração não precisa ser primo. Simplesmente foi apresentado que ele tem</p><p>um divisor primo diferente de p₁, p₂, ..., pm. A princípio, pode-se encontrar um primo</p><p>'p' por meio da fatoração de N. Logo, a demonstração desse teorema pode ser vista</p><p>como uma “receita” que, dada qualquer lista finita de primos, produzirá um “novo”</p><p>primo, ou seja, um primo que não esteja na lista.</p><p>Diversas variações do segundo teorema de Euclides podem ser encontradas</p><p>na literatura. Uma delas corresponde à afirmação de que existem infinitos números</p><p>primos da forma 4n ‒ 1. A demonstração pode ser construída de forma análoga à feita</p><p>para o próprio teorema. De fato, suponha que exista um número finito de primos da</p><p>29</p><p>forma 4n ‒ 1, a saber, p₁, p₂, ..., pr . Considere o número N = 4p₁ p₂ ... pr ‒ 1. Como</p><p>N é ímpar, ele é o produto de fatores primos ímpares. Sabe-se que todo número ímpar</p><p>é da forma 4n + 1 ou 4n ‒ 1. Se todos os fatores primos de N fossem da forma 4n +</p><p>1, então o produto N de todos esses fatores também seria dessa forma.</p><p>Porém, como N não é da forma 4n + 1, é correto afirmar que N tem algum fator</p><p>p da forma 4n ‒ 1. Além disso, p é necessariamente diferente de p₁, p₂, ..., pr, já que</p><p>nenhum desses termos divide N. No entanto, a existência de um novo primo p da</p><p>forma 4n – 1 contradiz a hipótese de que p₁, p₂, ..., pr corresponde à lista de todos os</p><p>número primos dessa forma. Portanto, existem infinitos primos da forma 4n ‒ 1.</p><p>(RODRIGUES, 2018).</p><p>Exemplos:</p><p>1. Utilizando a forma 4n ‒ 1, para n = 1, qual o número primo gerador?</p><p>2.</p><p>4n ‒ 1</p><p>4. 1 ‒ 1</p><p>5 – 1 = 4</p><p>A demonstração acima mostra que nem todo número gerado pela fórmula é</p><p>primo, visto que 4 é um número divisível por 1, 2 e 4. Ou seja, a fórmula apresentada,</p><p>para n = 1, não apresenta um número primo em seu resultado.</p><p>2. Utilizando a forma 4n ‒ 1, para n = 2, qual o número primo gerador?</p><p>4n ‒ 1</p><p>4. 2 ‒ 1</p><p>8 – 1 = 7</p><p>A demonstração mostra que a fórmula é válida para n = 2, visto que 7 é um</p><p>número primo, divisível por 1 e ele mesmo.</p><p>30</p><p>6 MÚLTIPLOS E DIVISORES DE UM NÚMERO</p><p>Entender as relações numéricas é extremamente importante na Matemática,</p><p>podendo facilitar seu entendimento e a resolução de problemas mais complexos. A</p><p>partir de agora, você estudará um pouco a respeito dos múltiplos e divisores de um</p><p>número. (STEFANI, 2018).</p><p>Múltiplo de um número é aquele que resulta da multiplicação por um número</p><p>inteiro. Por exemplo, na multiplicação 2 × 5 que resulta em 10, podemos afirmar que</p><p>10 é múltiplo de 2 e é múltiplo de 5. Para encontrar um múltiplo entre dois ou mais</p><p>números inteiros, basta multiplicá-los, conforme os exemplos a seguir.</p><p>Encontre um múltiplo comum de 15 e 23.</p><p>15 × 23 = 345</p><p>Logo, 345 é múltiplo de 15 e, ao mesmo tempo, múltiplo de 23.</p><p>Determine um múltiplo comum de 2, 7, 18 e 31:</p><p>2 × 7 × 18 × 31 = 7.812</p><p>Assim, 7.812 é múltiplo de 2, 7, 18 e 31 ao mesmo tempo.</p><p>Para o número 7, se fizermos:</p><p>7 × 0 = 0</p><p>7 × 1 = 7</p><p>7 × 2 = 14</p><p>7 × 3 = 21</p><p>7 × 4 = 28</p><p>7 × 5 = 35</p><p>7 × 6 = 42</p><p>7 × 7 = 49</p><p>7 × 8 = 56</p><p>7 × 9 = 63</p><p>7 × 10 = 70 [...]</p><p>31</p><p>Afirmamos que 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70 ⋯ são múltiplos de 7.</p><p>Divisores de um número são aqueles que, ao dividirem números inteiros, deixam resto</p><p>igual a 0 (zero) na operação. Por exemplo, 3 é um divisor de 12; uma vez que a divisão</p><p>12 ÷ 3 = 4</p><p>é exata, ou seja, o resto é 0 (zero).</p><p>De maneira análoga, podemos garantir que 7 é divisor de 21, 28, 42, 49, 56,</p><p>63…, uma vez que todos esses números são múltiplos de 7 e sua divisão por 7 sempre</p><p>resultará em resto igual a 0 (zero).</p><p>Uma vez que 7 é um divisor de 42, podemos dizer que 42 é divisível por 7. E</p><p>que 12 é divisível por 3 e por 4.</p><p>É importante observar que os números primos terão somente dois divisores: o</p><p>número 1 e eles mesmos.</p><p>Você já sabe que 3 e 4 são divisores de 12. Existem outros divisores para 12?</p><p>Sim, 12 é divisível por 1, 2, 6 e 12.</p><p>6.1 MMC e MDC</p><p>O cálculo de múltiplos e divisores de um ou mais números tem,</p><p>simultaneamente, muitas aplicações práticas. Ao falarmos de múltiplos e divisores,</p><p>verificamos como podemos determiná-los para um número. Porém, na Matemática,</p><p>existem métodos para determinar múltiplos e divisores comuns entre dois ou mais</p><p>números de modo paralelo. (STEFANI, 2018).</p><p>Esses métodos determinam o mínimo múltiplo comum (MMC) entre dois ou</p><p>mais números e o máximo divisor comum (MDC) entre dois ou mais números.</p><p>Tanto para o cálculo do MMC quanto do MDC podemos utilizar o método de</p><p>fatoração numérica, que consiste em realizar sucessivas divisões do número, ou dos</p><p>números, por seus divisores. Na fatoração, os números devem ser divididos,</p><p>sucessivamente, pelos mesmos números naturais primos, quando possível,</p><p>colocando-se o quociente da divisão abaixo do dividendo. Isso deve ser repetido até</p><p>que o quociente de todos os números seja igual a 1.</p><p>Por exemplo, caso seja necessário fatorar o número 12, procederemos da</p><p>seguinte maneira, trabalhando com seus divisores:</p><p>32</p><p>Ao fatorar o número 12, você pode observar que é divisível por 2; como o 2 se</p><p>repetiu por duas vezes, é divisível por 4; na primeira divisão por 2, o resultado foi 6,</p><p>também divisor de 12; e, por fim, foi dividido por 3, também divisor de 12.</p><p>Quando você executar essa fatoração com dois ou mais números, conseguirá</p><p>determinar o MMC entre eles. Por exemplo, em uma soma de frações, cujos</p><p>denominadores são distintos, é necessário colocá-las sob um denominador comum</p><p>para a realização da soma. (STEFANI, 2018).</p><p>Assim, tomando todos os denominadores, é possível obter o MMC para realizar</p><p>a operação fatorando-os:</p><p>Resolva:</p><p>Devemos, então, proceder à fatoração dos denominadores:</p><p>Assim, ao multiplicar todos os elementos da sua direita, você obterá o MMC</p><p>entre os números fatorados:</p><p>2 × 2 × 2 × 2 × 2 × 3 × 3 × 5 = 1.440</p><p>33</p><p>Portanto, a soma de frações será resolvida como:</p><p>Determinando o resultado da operação:</p><p>Procedendo à fatoração:</p><p>Logo, o MMC entre 27,3 e 9 é igual a 3 × 3 × 3 = 27.</p><p>O MDC também pode ser obtido por meio do processo de fatoração. (STEFANI,</p><p>2018). Como exemplo, repetiremos a fatoração entre 27,3 e 9. Após finalizada a</p><p>fatoração, a multiplicação dos números que dividiram simultaneamente os três</p><p>números será o MDC.</p><p>Observe que somente a primeira divisão por 3 conseguiu, simultaneamente,</p><p>dividir os três números. Portanto, 3 é o MDC entre 27,3 e 9.</p><p>Determinando o MDC entre 72 e 84:</p><p>34</p><p>Observe que somente o número 2 dividiu os dois números, simultaneamente,</p><p>por duas vezes e o número 3 dividiu os dois números, simultaneamente, por uma vez.</p><p>Assim, 2 x 2 x 3 = 12 é o MDC entre 72 e 84.</p><p>Exemplos:</p><p>O MDC e o MMC podem ser úteis em aplicações práticas (STEFANI, 2018),</p><p>como nos exemplos a seguir.</p><p> Suponha que dois carros estejam em fase de teste para venda, ambos com</p><p>a mesma capacidade no tanque de combustíveis. O carro A conseguiu realizar 12</p><p>voltas com a mesma quantidade de combustível que o carro B utilizou para dar 8</p><p>voltas. Quantos litros de combustível, no mínimo, estavam no tanque de ambos antes</p><p>do início dos testes?</p><p>Este problema pode ser resolvido pelo MMC entre 12 e 8, que, se fatorados,</p><p>resultarão da solução de 24 litros em cada tanque.</p><p> Para uma festa junina, foram comprados papéis coloridos, com folhas</p><p>medindo 48 cm × 60 cm. Para cortar bandeirinhas de mesmo tamanho, quadradas, de</p><p>modo que a totalidade da folha seja aproveitada, qual deverá ser a sua medida lateral?</p><p>Este problema pode ser resolvido utilizando o MDC entre 48 e 60; assim:</p><p>Nas linhas destacadas, os divisores eram comuns entre os dois números,</p><p>portanto 2 × 2 × 3 = 12; as bandeirinhas deverão ser cortadas com a medida de 12</p><p>cm × 12 cm.</p><p>35</p><p>7 DIVISIBILIDADE E O USO DA CONGRUÊNCIA E DOS TEOREMAS DE FERMAT</p><p>E DE WILSON</p><p>Na teoria dos números, a divisibilidade é um conceito fundamental. Nesse</p><p>contexto, a definição de congruência é uma verificação da divisibilidade. Pierre de</p><p>Fermat (1601–1665) teve vários estudos consolidados no ramo da teoria dos</p><p>números. Entretanto, Carl Friedrich Gauss (1777–1855) foi o primeiro matemático a</p><p>tratar a teoria das congruências como uma área da matemática.</p><p>Nesta seção, você vai estudar quais características comuns a divisibilidade e a</p><p>congruência possuem e como resolver exemplos de congruência aplicando conceitos</p><p>de divisibilidade. Você também vai verificar como deduzir propriedades importantes</p><p>que utilizam as definições de congruência e de divisibilidade. Por fim, você vai</p><p>aprender a identificar e demonstrar os teoremas de Wilson e Fermat e a fazer uso</p><p>desses teoremas na resolução de problemas de congruência.</p><p>7.1 Critérios de divisibilidade aplicando congruência</p><p>Antes de interpretar a relação entre a divisibilidade e a congruência, vamos</p><p>relembrar alguns conceitos relevantes. Considerando o conjunto dos inteiros, dizemos</p><p>que um número b é divisível pelo número a se b é múltiplo de a (CAMPOS, 2009). A</p><p>recíproca também é válida. Conforme Santos (2018), a aritmética a seguir,</p><p>pertencente ao conjunto dos números inteiros, pode ser definida.</p><p> Definição 1: Se a e b são inteiros, dizemos que a divide b, denotando por</p><p>a|b se, e somente se, existir um inteiro c ∈ ℤ tal que b = ac.</p><p>■ Observação: caso um inteiro a não divida b, vamos denotar a∤b.</p><p>■ Ex.: o número divide 8 porque existe um inteiro c = –2, tal que 8 = (–4) (–2).</p><p>Fenômenos cíclicos ou periódicos possuem em seu comportamento a repetição</p><p>dos acontecimentos. Podemos exemplificar matematicamente o fenômeno das horas</p><p>(COUTINHO, 1997). Os dias mudam, mas as horas são mantidas equivalentes.</p><p>Diante disso, vamos considerar um número inteiro n, o qual será o módulo</p><p>(período). Mais especificamente, adotaremos dois inteiros a e b equivalentes de n em</p><p>n períodos. Podemos dizer que a e b são congruentes módulo n. Assim, definimos</p><p>formalmente a congruência dos elementos em ℤ, com base em Gonçalves (2017).</p><p>36</p><p> Definição 2: Se a e b são números inteiros, dizemos que a é congruente b</p><p>módulo n (n >0) se n|(a – b). Denotamos isso por a ≡ b (mod n). Se n∤(a – b), dizemos</p><p>que a é incongruente a b módulo n e denotamos a ≢ b (mod n).</p><p>Veja a seguir alguns exemplos da Definição 2.</p><p>1. 16 ≡ –4 (mod 10), pois 16 – (–4) = 20, sendo que 10|20.</p><p>2. 8 ≢ 3 (mod 2), pois 8 – 3 = 5, sendo que 2∤5 no conjunto ℤ.</p><p>3. 72 ≡ –5 (mod 7), pois 7|(72 – (–5)).</p><p>4. 27 ≢ 8 (mod 9), pois 9|(27 – 8).</p><p>O estudo do resto da divisão de dois inteiros diferentes por outro inteiro é</p><p>chamado de módulo. Ou seja, se dois números inteiros possuem o mesmo resto na</p><p>divisão pelo n, esses números são congruentes módulo n (LIPSCHUTZ; LIPSON,</p><p>2009).</p><p> Proposição 1: Se a e b são inteiros, temos que a ≡ b (mod n) se, e somente</p><p>se, existir um inteiro k tal que a = b + km.</p><p>■ Demonstração: se a ≡ b (mod n), então n|(a – b). O que implica na</p><p>existência de um número inteiro k tal que a – b = kn, isto é, a = b + kn. A recíproca é</p><p>trivial, pois, da existência de um k satisfazendo a = b + kn, temos kn = a – b, ou seja,</p><p>que n|(a – b), isto é, a ≡ b (mod n).</p><p>Agora que você relembrou a associação de números divisíveis e de números</p><p>congruentes, serão especificados os critérios de divisibilidade utilizando a</p><p>congruência.</p><p>7.2 Critérios de divisibilidade</p><p>Para manipular as congruências de forma mais simplificada, você precisa</p><p>construir os critérios de divisibilidade. Assim, poderá resolver problemas de</p><p>congruência com números muito elevados. Ao tratarmos os critérios de divisibilidade</p><p>de inteiros a = aₙ aₙ₋₁ ⋯ a₁ a₀, podemos representá-los pelo seguinte polinômio</p><p>(DOMINGUES; IEZZI, 2003):</p><p>37</p><p>onde a₀ é o algarismo das unidades, a₁ é o algarismo das dezenas e assim por diante.</p><p>Logo, o intuito</p><p>de usar as propriedades de congruência é para reduzir os</p><p>algarismos do numeral expressado em (1). (SANTIAGO, 2018). Assim, podemos</p><p>calcular a divisibilidade de números inteiros sem a necessidade de um sistema</p><p>computacional, como mostrado a seguir.</p><p>7.2.1 Critério de divisibilidade por 2</p><p>Iniciamos pela simples congruência 10 ≡ 0 (mod 2), verdadeira também para</p><p>potências de 10 — isto é, a congruência 10 ͭ ≡ 0 (mod 2) é válida para todo t ≥ 1. Como</p><p>o polinômio (1) possui potências de 10, podemos reescrever a congruência para o</p><p>inteiro a — assim, a – a₀≡ 0 (mod 2).</p><p>Então a ≡ a₀ (mod 2) e, pela definição 2, a divisão 2|(a – a₀ ) é válida. O que</p><p>implica 2|a se, e somente se, 2|a₀ . Logo, o algarismo da unidade a₀ deve ser par. Em</p><p>outras palavras, isso demonstra que todo inteiro com algarismo da unidade par é</p><p>divisível por 2.</p><p>7.2.2 Critério de divisibilidade por 3</p><p>Pela congruência verdadeira 10 ≡ 1 (mod 3), vamos começar a construir esse</p><p>critério de divisibilidade. Utilizando a propriedade de potência na congruência, isso</p><p>resulta em 10 ͭ ≡ 1 (mod 3) para todo t ≥ 1. Dessa forma, vamos multiplicar os</p><p>coeficientes at na congruência anterior.</p><p>Assim, at 10 ͭ ≡ at (mod 3), sendo 1 ≤ t ≤ n. Somando-se todas essas</p><p>congruências, fica a ≡ aₙ + aₙ–1 + ⋯ + a + ₀ (mod 3). Pela Definição 2, a é divisível</p><p>por 3 se, e somente se, o termo aₙ + aₙ₋₁ + ⋯ + a₁ + a₀ é divisível por 3. Portanto, isso</p><p>mostra que, para todo inteiro divisível por 3, a soma dos seus algarismos também é</p><p>divisível por 3.</p><p>7.2.3 Critério de divisibilidade por 4</p><p>Observamos que 10²≡ 0 (mod 4), 10ᶟ ≡ 0 (mod 4) e assim sucessivamente até</p><p>10ₙ ≡ 0 (mod 4) Se multiplicarmos os coeficientes do polinômio (1) nas congruências</p><p>38</p><p>respectivas, obtemos: a² 10² ≡ 0 (mod 4), aᴈ 10ᶟ ≡ 0 (mod 4), ⋯, aₙ 10ₙ ≡ 0 (mod 4).</p><p>Pelas propriedades aritméticas de números côngruos, podemos somar todas as</p><p>congruências e adicionar o termo a0 + a1 10 no resultado obtido. Isso implica a ≡ a₀</p><p>+ a₁ 10 (mod 4). É importante notar que a₀ + a₁ 10 = a₁ a₀ , ou seja, são os dois últimos</p><p>algarismos do número a. Então, o inteiro a e o termo a0a1 possuem o mesmo resto</p><p>na divisão por 4. Logo, a e a₁ a₀ são divisíveis por 4. Essa construção mostra que, se</p><p>o termo formado pelos dois últimos algarismos de um inteiro é divisível por 4, o inteiro</p><p>é divisível também.</p><p>7.2.4 Critério de divisibilidade por 8</p><p>Pela congruência simples 10 ≡ 2 (mod 8), podemos elevar na potência 3. Assim,</p><p>10ᶟ ≡ 2ᶟ ≡ 0 (mod 8) é verdadeira. Também segue que, para todo aⁱ, i ≥ 3, a</p><p>congruência ai10ⁱ ≡ 0 (mod 8) é válida. Isso mostra que a congruência a ≡ a₂ a₁ a₀</p><p>(mod 8) é satisfeita para qualquer inteiro a divisível por 8.</p><p>Portanto, o critério de divisibilidade por 8 mostra que, para qualquer número</p><p>inteiro com dígitos iguais ou maiores do que 3, um inteiro é divisível por 8 se, e</p><p>somente se, os três últimos algarismos desse inteiro formam um número divisível por</p><p>8. (SANTIAGO, 2018).</p><p>7.2.5 Critério de divisibilidade por 11</p><p>Sabemos que 10 ≡ –1 (mod 11). Assim, podemos elevar a potência k ∈ ℕ na</p><p>congruência anterior, tornando 10ᵏ ≡ (–1)ᵏ (mod 11). Considerando a de (1),</p><p>multiplicamos os coeficientes a₁, ⋯, aₙ em cada n congruências, somamos esses</p><p>termos e o a₀ e obtemos:</p><p>Mais especificamente, isso implica a congruência:</p><p>39</p><p>Logo, um número inteiro é divisível por 11 se, e somente se, a soma dos</p><p>algarismos de ordem par subtraída da soma dos algarismos de ordem ímpar resulta</p><p>em um número inteiro divisível por 11. (SANTIAGO, 2018).</p><p>Agora você terá a oportunidade de aprender a resolver problemas numéricos</p><p>que envolvem critérios de divisibilidade.</p><p>Exemplos</p><p>A seguir, serão apresentados cinco problemas.</p><p>1. Calcule o resto da divisão de 2 ᶟ⁰ por 17.</p><p>Como a congruência 2⁴ ≡ –1 (mod 17) é verdadeira, podemos elevar à potência</p><p>7. Isso resulta em 2²⁸ ≡ –1 (mod 17). Agora, multiplicamos na congruência o número</p><p>4 = 2² . Dessa forma, obtemos 2ᶟ⁰ ≡ –4 (mod 17). Sabendo que –4 ≡ 13 (mod 17) e</p><p>que a propriedade de transitividade é válida, então 2ᶟ⁰ ≡ 13 (mod 17). Logo, o resto</p><p>da divisão é 13.</p><p>2. Mostre que 10²⁰⁰ – 1 é divisível por 11. Iniciamos pela congruência 10 ≡ –1</p><p>(mod 11). Depois, utilizamos a propriedade de potência resultando em 10200 ≡ (–1)²⁰⁰</p><p>(mod 11). Assim, 10²⁰⁰ ≡ 1 (mod 11), e pela Definição 2, a expressão numérica 10²⁰⁰</p><p>– 1 é divisível por 11.</p><p>3. Mostre que 12.564.890 é divisível por 3. Pela congruência 10 ≡ 1 (mod 3)</p><p>válida, obtemos 10 ͭ ≡ 1 (mod 3), t ∈ ℕ. Então, pelo critério de divisibilidade por 3:</p><p>12.564.890 ≡ (1 + 2 + 5 + 6 + 4 + 8 + 9 + 0) (mod 3). Ou seja, 12.564.890 ≡ 45 (mod</p><p>3). Como 45 ≡ 0 (mod 3), pela propriedade de transitividade, isso resulta em</p><p>12.564.890 ≡ 0 (mod 3). Logo, 12.564.890 é divisível por 3.</p><p>4. Calcule o resto da divisão de 25.384 por 2. Fazendo a decomposição do</p><p>número inteiro 25.384 no polinômio de base 10, representado na equação (1), isso</p><p>implica 25.384 ≡ (2 ⋅ 104⁴+ 5 ⋅ 10ᶟ + 3 ⋅ 10² + 8 ⋅ 10¹ + 4) (mod 2). Assim, pelo critério</p><p>de divisibilidade 2, a congruência anterior é equivalente a 25.384 ≡ 4 (mod 2). Também</p><p>sabemos que 4 ≡ 0 (mod 2), então, pela transitividade, 25.384 ≡ 0 (mod 2). Portanto,</p><p>o resto da divisão buscada é zero.</p><p>40</p><p>5. Calcule o resto da divisão de 17²⁰⁰² por 13.</p><p>Pelas congruências 17 ≡ 4 (mod 13), 16 ≡ 3 (mod 13) e pelas propriedades de</p><p>potência em congruências, segue que 17²⁰⁰² ≡ 4²⁰⁰²≡ 16 ¹⁰⁰¹ ≡ 3 ¹⁰⁰¹ (mod 13).</p><p>Observamos que 33 ≡ 1 (mod 13); então:</p><p>3 ¹⁰⁰¹ = 3²⋅ 3⁹⁹⁹ = 9 ⋅ (3ᶟ) ᶟᶟᶟ ≡ 9 ⋅ 1ᶟᶟᶟ= 9 (mod 13).</p><p>Portanto, 17²⁰⁰² ≡ 9 (mod 13), isto é, 17²⁰⁰² possui resto 9 na divisão por 13.</p><p>Os teoremas de Wilson e Fermat são consequências de conceitos introdutórios de</p><p>congruência e de critérios de divisibilidade. Você aprenderá a construção desses</p><p>teoremas a seguir.</p><p>7.3 Estruturação dos teoremas de Wilson e de Fermat</p><p>Para interpretar os teoremas de Wilson e de Fermat, vamos apresentar</p><p>proposições, definições e corolários, os quais serão a base do conhecimento. Todo</p><p>inteiro com o mesmo resto em módulo pertence à mesma classe. Isto é, os números</p><p>que pertencem à mesma classe possuem o mesmo resto. Desse modo, podemos</p><p>definir uma classe residual a seguir (HEFEZ, 2016).</p><p> Definição 3: Dado um inteiro m > 1. A classe residual módulo m do elemento</p><p>a ∈ ℤ é definida como a classe de equivalência de a, conforme a seguinte relação de</p><p>equivalência dada pela congruência módulo m:</p><p>[a] = {x ∈ ℤ; x ≡ a (mod m)}</p><p> Exemplo: seja m = 2. Então:</p><p>[0] = {x ∈ ℤ; x ≡ 0 (mod 2)} = {x ∈ ℤ; x é par} e</p><p>[1] = {x ∈ ℤ; x ≡ 1 (mod 2)} = {x ∈ ℤ; x é ímpar}</p><p>Também podemos perceber que [a] = [0], se a é par, e [a] = [1], se a é ímpar.</p><p>Logo, as classes residuais, por serem classes de equivalência, possuem as seguintes</p><p>propriedades:</p><p>a) [a] = [b] se, e somente se, a ≡ b (mod m);</p><p>b) se [a] ∩ [b] ≠ ∅, então [a] = [b];</p><p>c) ⋃a∈ℤ[a] = ℤ.</p><p>41</p><p>O conjunto de todas as classes residuais módulo m pode ser denotado por ℤᵐ.</p><p> Proposição 2: Para cada a ∈ ℤ, existe um, e somente um, r ∈ ℤ, com 0 ≤ r</p><p>< m, tal que [a] = [r].</p><p> Demonstração: seja a ∈ ℤ, e considerando-se a divisão euclidiana, existem</p><p>dois únicos inteiros q e r, com 0 ≤ r < m, tais que a = m ⋅ q + r. Então, o inteiro r é</p><p>único, tal que 0 ≤ r < m e a ≡ r (mod m). Por consequência, o inteiro r é único tal que</p><p>0 ≤ r < m e [a] = [r].</p><p>Adicionalmente, todo resto de um número de uma classe residual é</p><p>considerado resíduo em módulo. Em Niven, Zuckerman e Montgomery (1991),</p><p>podemos encontrar a definição de resíduo em módulo, conforme apresentado a</p><p>seguir.</p><p> Definição 4: Se x ≡ y (mod m) para x e y sendo inteiros, então y é chamado</p><p>de resíduo de x módulo m.</p><p>Para definir uma característica em comum de um grupo de resíduos, foram</p><p>propostas as definições a seguir (ANDREWS, 1994).</p><p> Definição 5: O conjunto dos inteiros {r₁,</p><p>⋯, rs } é chamado de um sistema</p><p>completo de resíduo módulo m se ri ≢ rj (mod m) para i ≠ j; para cada inteiro n existe</p><p>um correspondente ri tal que n ≡ ri (mod m). Em outras palavras, o sistema é completo</p><p>de resíduos {r₁ , ⋯, rs } módulo m se, e somente se, [r₁ ], ⋯, [rᵐ] são as m classes</p><p>residuais módulo m.</p><p> Definição 6: Um sistema reduzido de resíduos módulo m é um conjunto ϕ(m)</p><p>inteiros r₁ , ⋯, rϕ (m), tais que cada elemento do conjunto é relativamente primo com</p><p>m, e se i ≠ j, então ri ≢ rj (mod m).</p><p> Teorema 1: Seja a um inteiro positivo tal que MDC(a, m) = 1, sendo MDC o</p><p>máximo denominador comum. Se r₁ , ⋯, rϕ(m) é um sistema reduzido de resíduos</p><p>módulo m, então ar₁ , ⋯, arϕ(m) é, também, um sistema reduzido de resíduos módulo</p><p>m.</p><p> Demonstração: Na sequência ar₁ , ⋯, arϕ(m) , temos ϕ(m) elementos.</p><p>Assim, devemos provar que todos os elementos são relativamente primos com m.</p><p>Como o MDC(a, m) = 1 e o MDC(ri , m) = 1, isso implica que MDC(ari , m) = 1. Basta</p><p>provar que ari ≢ arj (mod m) se i ≠ j. Porém, como MDC(a, m) = 1 de ari ≡ arj (mod</p><p>m), obtemos ri ≡ rj (mod m). Então, i = j, para r₁, ⋯, rϕ(m) ser um sistema reduzido de</p><p>resíduos módulo m.</p><p>42</p><p> Proposição 3: Um elemento [a] ∈ ℤ ᵐ é invertível se, e somente se, MDC(a,</p><p>m) = 1.</p><p> Demonstração: se [a] é invertível, então existe [b] ∈ ℤ ᵐ tal que [1] = [a] ⋅ [b]</p><p>= [a ⋅ b]. Isso implica a ⋅ b ≡ 1 (mod m). Ou seja, existe um t, tal que a ⋅ b + t ⋅ m = 1.</p><p>Logo, MDC(a, m) = 1. Se MDC(a, m) = 1, existem números inteiros b e t, sendo a ⋅ b</p><p>+ m ⋅ t = 1, implicando em [1] = [a ⋅ b + m ⋅ t] = [a ⋅ b] + [m ⋅ t] = [a] ⋅ [b] + [0] = [a] ⋅ [b].</p><p>Portanto, [a] é invertível.</p><p>Podemos concluir por essa proposição e pelo Teorema 1 que um conjunto {r₁ ,</p><p>⋯, rϕ(m) } ⊂ ℤ é um sistema reduzido de resíduos módulo m se [r₁ ], ⋯, [rϕ(m) ] são</p><p>elementos invertíveis de ℤᵐ. Então, podemos denotar o conjunto dos elementos</p><p>invertíveis como ℤ*m. Além disso, na bibliografia de Galdino (2014), você poderá</p><p>encontrar como uma solução de uma congruência é nomeada.</p><p> Definição 7: Para a e m números inteiros, a solução a̅ de x em ax ≡ 1 (mod</p><p>m) é chamada de um inverso de a módulo m.</p><p>Em Santos (2018), a proposição a seguir foi apresentada.</p><p> Proposição 4: Seja p um número primo. O inteiro positivo a é o seu próprio</p><p>inverso módulo p se, e somente se, a ≡ 1 (mod p) ou a ≡ –1 (mod p).</p><p>Agora vamos abordar os teoremas propostos no início deste estudo. O teorema</p><p>de Wilson possui diversas demonstrações, mas apresentaremos a demonstração de</p><p>Andrews (1994).</p><p>7.3.1 Teorema de Wilson</p><p>A congruência (m – 1)! ≡ –1 (mod m) é satisfeita se, e somente se, m for um</p><p>número primo.</p><p>Demonstração 1</p><p>Vamos supor m um número primo e 1, ⋯, m – 1 inteiros positivos. Pela</p><p>Definição 5, se a é um número inteiro, então existe um inverso ã de a módulo m tal</p><p>que aã ≡ 1 (mod m). Caso a seja seu próprio inverso, a² ≡ 1 (mod m). Assim, m|(a –</p><p>1)(a + 1), o que resulta em m|(a – 1) ou m|(a – 1). Pela Definição 2, a ≡ ±1 (mod m).</p><p>Como 1 e m - 1 são os únicos próprios inversos de módulo m, vamos agrupar os</p><p>números m – 2, ⋯, 2 em pares congruentes a 1 módulo m. Dessa forma, o produto</p><p>43</p><p>dessas congruências resulta em 2 × ⋯ × m – 2 ≡ 1 (mod m). Multiplicando-se pelo</p><p>termo m – 1, isso implica (m – 1)! ≡ (m – 1) (mod m). Pela congruência, m – 1 ≡ –1</p><p>(mod m), e, pela transitividade, obtemos (m – 1)! ≡ –1 (mod m).</p><p>Supondo que m não é primo, então existe um número a (1 < a < m) tal que a|m.</p><p>Também podemos observar que a|(m – 1)!. Se (m – 1)! ≡ –1 (mod m), então, pela</p><p>definição de congruência, existirá um inteiro k tal que (m – 1)! + 1 = km. Como a|m e</p><p>a|(m – 1)!, utilizando a equação anterior, obtemos a|1. Isso contradiz a hipótese a > 1.</p><p>Logo, se (m – 1)! ≡ –1 (mod m), o número m deve ser primo.</p><p>Demonstração 2</p><p>A expansão de Maclaurin da função ln</p><p>Pelas propriedades logarítmicas e exponenciais, isso resulta em:</p><p>Reescrevemos a equação em:</p><p>O que é equivalente a:</p><p>Sabemos que, pela função inicial, o termo xᴾ = 1. Esse coeficiente, pela</p><p>equação anterior, é da forma sendo r/s a soma de um número finito de</p><p>44</p><p>racionais que não possuem o fator p no denominador, caso MDC(r, s) = 1 e p∤s. Então,</p><p>para , obtemos:</p><p>Desse modo:</p><p>Como o termo (s – r)(p – 1)! é um inteiro e p∤s, então p|(1 + (p – 1)!). Também</p><p>será abordada a seguinte definição de função de Euler, a qual forma a base para um</p><p>importante teorema.</p><p> Definição 8: A função ϕ: ℤ+ → ℤ+, que associa a cada número inteiro</p><p>positivo m a quantidade de elementos do conjunto {k ∈ ℤ+|1 ≤ k ≤ m – 1 e MDC(k, n)</p><p>= 1}, é chamada função de Euler.</p><p>Pela Definição 6, podemos deduzir que a função ϕ(m) mostra quantos dos</p><p>números do conjunto {1, ⋯, m – 1} são primos entre si. Caso m seja um número primo</p><p>qualquer, todos os números 1, ⋯, m – 1 são coprimos de m. Logo, ϕ(m) = m – 1. Dessa</p><p>forma, Euler também teve sua contribuição na teoria das congruências. O teorema a</p><p>seguir mostra isso.</p><p>7.3.2 Teorema de Euler</p><p>Se m é um inteiro positivo e a um inteiro com MDC(m, a) = 1, então aϕ(m) ≡ 1</p><p>(mod m). Veja a seguir a demonstração.</p><p>Seja r1 , ⋯, rϕ(m) um sistema reduzido de resíduos módulo m. Observamos</p><p>que ar1 , ⋯, arϕ(m) são todos primos relativos a m e que também formam um sistema</p><p>de resíduos reduzidos módulo m. Então, para cada ri , i = 1, ⋯, ϕ(m), existe um e</p><p>somente um arj , j = 1, ⋯, ϕ(m), tal que ri ≡ arj (mod m). Notamos que diferentes ri</p><p>correspondem a diferentes ar. Isto é, os números ar₁ , ⋯, arϕ(m) são apenas resíduos</p><p>45</p><p>módulo m de r₁ , ⋯, rϕ(m) , mas não necessariamente na mesma ordem. Assim,</p><p>multiplicando todas as congruências, obtemos:</p><p>O que, pelas propriedades do produtório, implica:</p><p>Sabendo que MDC(rj , m) = 1 e os rj são primos relativos em m, concluímos</p><p>que</p><p>Com o resultado de Euler, podemos enunciar o teorema de Fermat (GARCIA;</p><p>LEQUAIN, 2006), cuja demonstração é apresentada em Monteiro (1978)</p><p>7.3.3 Teorema de Fermat</p><p>Se p é um número primo, a é um número inteiro e p∤a, então aᴾ-¹ ≡ 1 (mod p).</p><p>Veja a seguir a demonstração.</p><p>Demonstração</p><p>Como p∤a, o MDC entre p e a é 1. Pelo teorema de Euler, aϕ(p) ≡ 1 (mod p),</p><p>onde ϕ(p) é um número inteiro positivo menor ou igual a p. Assim, devemos buscar os</p><p>números de ϕ(p) primos entre si. Logo, sendo p primo, ϕ(p) = p – 1. Portanto, o teorema</p><p>de Euler é uma generalização do teorema de Fermat.</p><p>46</p><p>7.4 Aplicações dos teoremas de Wilson e de Fermat</p><p>Com os conhecimentos adquiridos para elaborar e demonstrar os teoremas de</p><p>Wilson e de Fermat, agora você vai aprender a aplicar esses conhecimentos por meio</p><p>de proposições lógicas e exemplos. Por consequência do teorema de Fermat, foi</p><p>construído o corolário descrito a seguir (LEMOS, 2001).</p><p>Corolário 1: Se p é um número primo e n um inteiro positivo, então np ≡ n (mod</p><p>p). Veja a seguir a demonstração.</p><p>Se p|n, então nᴾ ≡ 0 ≡ n (mod p). Se p∤n, então MDC(p, n) = 1. Assim, pelo</p><p>teorema de Euler:</p><p>nᴾ-¹ ≡ 1 (mod p)</p><p>onde ϕ(p) = p – 1. Agora, multiplicando ambos os lados da congruência por n,</p><p>concluímos que:</p><p>nᴾ ≡ n (mod p)</p><p>Também foi construída, a partir do teorema de Euler, a seguinte proposição: se</p><p>p é primo, então ϕ(pᶯ) = pᶯ – pᶯ–¹ = pᶯ–¹ (p – 1). Veja a demonstração a seguir. O</p><p>número p|a se, e somente se, MDC(pᶯ , a) ≠ 1. Assim, os únicos números entre 1 e</p><p>pn que não são primos relativos com pᶯ são os múltiplos de p, isto é, p, 2p, ⋯, pᶯ–¹</p><p>(p). Então, existem pᶯ–¹ múltiplos de p. O restante dos números são primos relativos</p><p>com pᶯ. Logo, a expressão ϕ(pᶯ ) = pᶯ – pᶯ–¹= pᶯ–¹ (p – 1) é verdadeira.</p><p>Agora vamos apresentar exemplos numéricos para que você possa aprender</p><p>como colocar em prática seus estudos na área de congruência com aplicações de</p><p>teoremas.</p><p>Exemplo:</p><p>Encontre o menor resíduo positivo da expressão</p>