Dados Internacionais de Catalogação na Publicação (CIP) (Câmara Brasileira do Livro, SP, Brasil) Rodrigues, A. P. A fórmula do número de algarismos no falso período dizimal / A. P. Rodrigues. --2. ed. Passo de Torres, SC Ed. do Autor, 2025. ISBN 978-65-01-64010-5 1. Matemática 2. Números Estudo e ensino 3. Números Teoria I. Título. 25-293846.1 CDD-510 Índices para catálogo sistemático: 1. Matemática 510 Aline Graziele Benitez Bibliotecária CRB-1/3129
Ao Inventor dos números.
Ao servo de Deus Marcelo Henrique Câmara†, in memoriam.
Prefácio
Quando dividimos um número por outro, o resultado é expresso em uma sequência de algarismos. Esta sequência de algarismos tem uma parte fracionária, que são aqueles algarismos que vêm depois da vírgula. Esta parte fracionária tem, ela própria, duas porções que não ficam especialmente destacadas uma da outra: uma que sempre está ali e outra que só às vezes aparece.
É possível calcular o número de algarismos que há na dízima de qualquer número racional. Sempre há uma sequência de algarismos que se repetem e, às vezes, aparece uma outra sequência que ocorre uma única vez. Podemos calcular o número de algarismos de ambas!
Por exemplo, a dízima de \( \frac{1}{7}=0,142857...\) tem 6 algarismos que se repetem indefinidamente, na mesma ordem, \(142857\), e formam assim a dízima infinita do número \( \frac{1}{7}\).
Um outro exemplo é o da fração \( \frac{8}{65}=0,123076923...\). A sequência inicial, \( 123\), de três algarismos, ocorre uma única vez. Após este período inicial, a dízima do \( \frac{8}{65}\) compõe-se apenas da sequência \( 076923\).
Foi observando números assim, que, muitos anos atrás, eu quis encontrar a fórmula que dava a exata quantidade de algarismos no período de qualquer número que tivesse a forma \( \frac{1}{n}\).
Os primeiros insights sobre como chegar em tal fórmula ocorreram aos poucos, demoradamente.
No meio-tempo, eu calculei, calculei e calculei… Hoje em dia, percebo que, naquela época, eu passava longos períodos em uma atitude de extrema concentração que não era completamente palatável para familiares, amigos e pessoas mais próximas. Mas, embora o aspecto social da minha vida naquele tempo tenha ficado abaixo das minhas próprias expectativas, este fato foi, eventualmente, compensado por pequenas descobertas e pela beleza e verdade de certas equações, fruto de um trabalho que nunca me negou gozos e satisfações de tempos em tempos.
Eu realmente passava, muitas vezes, horas, dias e noites tentando conjurar verdades matemáticas a partir de pensamentos e esquemas mentais que, à época, ainda estavam pouco ou nada equipados com os instrumentos próprios da arte. Não que hoje em dia eu esteja muito melhor do que naquela época, mas, saber que a Realidade existe em Deus, que abstrações matemáticas vão daquela em direção a Este e que não passam de abstrações se restritas a formalismos lógico-analíticos excessivos, sem o batismo nas águas profundas da poesia até os mares abertos da dialética, repito, saber disto robustece a inteligência, pois enche o pensamento daqueles extratos da realidade que vão desde o mais material e grosseiro até às intangibilidades abissais do Verbo e, para além, no Espírito.
Eu eventualmente cheguei às tais fórmulas que eu procurava. Obtive, primeiro, a fórmula para o período que se repete, ou, período verdadeiro, e a chamei de \( \alpha\) (letra grega alfa). Quando, finalmente, cheguei à fórmula daquele primeiro período, aquele que nem sempre ocorre, o falso período, chamei-o de \( \widetilde{\alpha}\) (lê-se alfa til). Eu, pessoalmente, chamo todo este trabalho de Teoria Alfa. O desenvolvimento da teoria está longe de ser acabado, muito mais longe do que o seu início até o momento em que escrevo! Mas, cada vez que a retomo, a retomo porque uma nova intuição se deixa perceber e, normalmente, traz consigo a ponta de linha de um novelo muito longo.
Posteriormente, avancei ainda um pouco mais e cheguei a uma fórmula para \( \alpha(b,m,n)\) e \( \widetilde{\alpha}(b,m,n)\), que dão o número de algarismos no período e no falso período dizimais de um racional qualquer, \( \frac{m}{n}\), e em uma base \( b\) qualquer. Mas, o tema deste primeiro livro é a fórmula do número de algarismos do período falso e o caminho que leva até ela.
O leitor verá que a teoria se desenvolve a partir de uma formalização inicial do procedimento simples que realiza a divisão de \( m\) por \( n\) para, a partir do segundo volume, uma algebrização que relaciona \( \alpha\) com outras quantidades e entes que surgem naturalmente durante este processo de contagem de algarismos, e, de repente, saltaremos para um campo aberto em que os próprios números inteiros serão dados em forma algébrica em termos dos \( \alpha\)`s envolvidos em sua fatoração prima. É um caminho longo em que beleza e admiração vão se intensificando e mais que compensando o esforço da caminhada.
O leitor verá também que os números \( \alpha\) ou \( \widetilde{\alpha}\) não são tão importantes em si mesmos. É que eles mudam de base para base. Explicarei isto em grande detalhe, neste presente volume e no próximo. Mas, a tentativa de enquadrá-los em fórmulas é tão frutífera, bela e nutritiva, pois que leva à matematização da própria maneira de se escrever um número racional, em uma base qualquer, e a fortalecer a evidência que nos leva a definir os números reais como sendo, ao mesmo tempo, a característica gregária e unitária do todo e de suas partes, que é, de fato, um aspecto de tudo o que é objeto de experiência.
A matemática usada na apresentação desta teoria, lida com conceitos simples e fáceis de serem apreendidos e qualquer pessoa com muito boa vontade para com eles pode entender perfeitamente bem o assunto. Logo, logo, iniciarei a publicação de vídeos em meu canal de YouTube (@aprodriguesOficial) para dar maiores explicações sobre alguns pontos apresentados neste livro e para apresentar alguns dos conceitos-chave que servem de base à teoria alfa.
Este volume apresenta os rudimentos da teoria alfa e termina com a exposição da fórmula de \( \widetilde{\alpha}\) e, pelo menos, uma de suas aplicações interessantes. Tudo o que virmos aqui, servirá de base ao conteúdo do próximo livro que, na opinião deste autor, é a parte principal e mais interessante da teoria alfa.
Como uma palavra final deste prefácio, eu gostaria de dizer que o assunto apresentado, aqui, decorre de um interesse que jamais dependeu de notas, de salário, ou de compensações financeiras, embora estes últimos dois tenham feito falta e teriam sido muito bem-vindos. Eu apenas tentei resolver um problema tal como ele se apresentou a mim e tenho sido bem-sucedido nisto. Certamente, não sou o primeiro a falar sobre estas coisas, nem serei o último. Não tenho a intenção de estar afinado com o que estão dizendo ou fazendo na academia, embora não despreze nada daquilo.
Deste modo, não tenho mais a pressa em buscar os limites do conhecimento atual, os quais se dilatam constantemente. Este autor dá mais valor à profundidade do que à largueza e, mesmo assim, aprofunda-se em passos de formiga, despreocupado com o aumento inflacionado da ciência do nosso tempo em que o aumento do conhecimento reflete também o aumento de contradições e fraudes, verdadeiramente científicas.
Em se tratando de vida de estudos, tento seguir as indicações dadas pelos meus interesses mais pessoais ou as dadas pelas necessidades apontadas por aquilo que eu esteja estudando em dado momento. Com certeza, isto não é uma receita que valha para todos. Cada indivíduo com vocação para a vida de estudos deve entender-se, em primeiro lugar, e saber dispor os recursos e oportunidades para este fim de modo que seja o melhor para si. Este autor encara a vida de estudos no tempo presente como uma preparação para a Eternidade na qual, em verdade, já estamos. Então, não há pressa alguma em chegar a algum destino, apenas o compromisso sério em conduzir-me para fora em direção a domínios cada vez maiores da Realidade.
1. A Divisão de Um Número por Outro
Considere a divisão que está realizada na continha 1 dividido por 7, abaixo. É assim que aprendemos a fazê-la desde as primeiras séries escolares. Este é o procedimento simples com o qual dividimos qualquer número \( n\) por um outro número \( d\). Ele é o nosso ponto de partida.
1 | 7 |
---|---|
-0 |
0,142857 |
10 |
|
-7 |
|
30 |
|
-28 |
|
20 |
|
-14 |
|
60 |
|
-56 |
|
40 |
|
-35 |
|
50 |
|
-49 |
|
1 |
Por ora, vamos apenas observar que, em 1 dividido por 7, paramos de calcular quando obtivemos o número \( 1\), que é o numerador com o qual iniciamos a conta.
Agora, é preciso que reconheçamos que, na continha acima, fizemos os seguintes cálculos
Se for preciso, o leitor deve fazer à mão a divisão de 1 por 7, ou de quaisquer pares de números, para se convencer (e relembrar) do que acabamos de ver.
Vamos agora, fazer uma pequena manipulação em cada uma das equações acima, trocando de lado o segundo termo do membro esquerdo com o número do membro direito.
Agora, daremos um "pulo de gato" e traduziremos as 8 equações acima em congruências matemáticas. Esta transposição de linguagem simples nos dotará das possibilidades algébricas operativas e expressivas que usaremos em todo este trabalho. Esta tradução deixa as 8 equações acima com o seguinte aspecto:
Bem, agora, vamos mostrar a forma geral da continha usada para dividir um número \( n\) por outro número \( d\). A continha 1 dividido por 7 acima é um caso particular do que vamos expor abaixo.
n | d |
---|---|
\(-d\cdot a_0\) |
\(a_0,a_1a_2a_3\dots a_{\alpha}\) |
\(10\cdot r_0\) |
|
\(-d\cdot a_1\) |
|
\(10\cdot r_1\) |
|
\(-d\cdot a_2\) |
|
\(10\cdot r_2\) |
|
\(-d\cdot a_3\) |
|
\(10\cdot r_3\) |
|
\(\vdots\) |
|
\(10\cdot r_{\alpha-1}\) |
|
\(-d\cdot a_{\alpha}\) |
|
\(r_{\alpha}\) |
Como antes, esta conta pode ser prontamente convertida em
para, então, trocarmos membros de lado e obtermos
e, finalmente, fazermos a conversão de (5) para o formato congruencial
É neste ponto que queríamos chegar! A partir daqui, a Teoria Alpha se desenrola!
Veremos, em seguida, que a expressão em 6 é prontamente generalizada para um base \( b\) qualquer, de modo que a sua aparência fica
Já quero adiantar que as expressões em 6 e em 7 permitem a contagem do número de algarismos periódicos da dízima de \( \frac{n}{d}\) e que isto acontece, basicamente, porque \( r_0=r_{\alpha}\). Há outros detalhes envolvidos nesta última e pequena equação. Veremos todos eles, por completo, no que se seguirá.
Por fim, observemos que 7 tem, em si, uma sequência finita, \( s\), de inteiros positivos. Estes inteiros positivos são os restos, \( r_i\), que aparecem na divisão de \( n\) por \( d\). Assim, \( s=\{r_i\}_{i=0}^{\alpha}\). A Teoria Alfa tem tudo a ver com a contagem dos elementos de \( s\) e com a tentativa de divisar as suas belas e frutuosas propriedades matemáticas.
2. A Periodicidade da Sequência s
A sequência \( s\) herda, naturalmente, a periodicidade dizimal de \( \frac{n}{d}\). Sob este aspecto, não seria preciso provar que \( s\) é periódica, pois ela não poderia não ser, já que ela é apenas parte integrante da conta de n dividido por d que, como sabemos, é onde esta periodicidade se manifesta e de onde, para começar, sabemos que ela acontece.
Mas, empreender a tarefa de tal prova é, como veremos a seguir, tão sobejamente frutífera, que acabaremos por esquecer completamente a fadiga dos esforços de arar esta terra e plantar sobre ela.
2.1. O Período Falso e os Períodos Verdadeiros
Todo este trabalho nasce da observação de incontáveis cálculos de divisão. Quando páginas atrás, eu disse que eu calculei, calculei e calculei, era a isto que eu me referia. Na verdade, qualquer piá ou guria que acompanhe as primeiras lições escolares sobre o processo de divisão, provavelmente ouvirá que há números racionais com dízima finita e outros com dízima periódica infinita. Isto pode ser observado nas continhas de divisão. É comum escrevermos números com parte quebrada com reticências depois do último algarismo, seja para indicar que a conta continuaria, se quiséssemos, seja para indicar que o período se repetiria.
Na verdade, toda dízima é periódica! Este detalhe inócuo logo ficará claro como cristal. Quando dizemos que algumas dízimas são finitas é porque observamos uma primeira sequência de algarismos seguida por uma outra sequência de infinitos zeros. A primeira sequência de algarismos é o falso período (que nem sempre ocorre), enquanto que a sequência infinita de zeros é justamente a sequência periódica cujo período é exatamente o algarismo zero.
A forma geral da dízima de um número \( \frac{n}{d}\) é simplesmente
em que \( a_0\) é a parte inteira de \( \frac{n}{d}\), enquanto que \( a_1\dots a_{\tilde{\alpha}}\) é o possível falso período e \( a_{\tilde{\alpha} + 1}\dots a_{\tilde{\alpha} + \alpha}\) é o período de algarismos que se repetem.
O símbolo \( \widetilde{\alpha}\) designa o número de elementos no falso período. É um fato muito feliz o de termos sido capazes de dar a fórmula exata que calcula este número também. Chegaremos a esta fórmula grandiosa em uma abordagem detalhadíssima nos capítulos vindouros.
Os algarismos dizimais de \( \frac{n}{d}\) se fazem acompanhar pelos respectivos restos desta divisão, a saber, os elementos da sequência finita
Veja que se \( \tilde{\alpha}=0\), isto significa que nem \( \frac{n}{d}\), nem \( s\) têm um falso período e que tanto 8 como 9 terão, respectivamente, os seguintes aspectos
e
que são os períodos verdadeiros que se repetem indefinidamente.
2.2. O Teorema Fundamental da Periodicidade
A seguir afirmo e provo o Teorema Fundamental da Periodicidade de \( s\) generalizado para uma base \( b\) qualquer. Este é, de fato, o teorema fundamental da Teoria Alfa. Ele está na base, direta ou indiretamente, de quase tudo o que afirmaremos daqui em diante.
A partir deste ponto, nós sempre nos referiremos ao fenômeno da periodicidade observada nos algarismos dizimais de uma divisão, digamos, \( \frac{m}{n}\) através da sequência de congruências correspondente, ou, mais especificamente, através da sequencia \( s=s(b,m,n)\), em que os argumentos \( b\), \( m\) e \( n\) indicam, respectivamente, a base em que o número \( \frac{m}{n}\) estiver sendo expressa, o numerador - segundo argumento - e o denominador (terceiro argumento). Note que o numerador \( m\) pode não coincidir com \( r_0\) e, por esta razão, não aparece em \( s(b,m,n)=\{r_i\}_{i=0}^{\tilde{\alpha} + \alpha}\). Logo, mostraremos que se \( r_0\in s(b,m,n)\), então, \( s(b,m,n)=s(b,r_0,n)\). Veremos isto em muito maior detalhe nos capítulos que se seguirão.
Antes de enunciarmos o teorema da periodicidade, precisamos levar em conta mais um detalhe. Vimos, por exemplo, em 5, que a sequência dos algarismos envolvidos em \( \frac{m}{n}\) pode ser calculada a partir dos restos - os elementos de s - e do denominador. Sumarizamos este fato na Definição 1 , abaixo. Com ela, completamos os pedaços de informação fundamental que precisamos para dar continuidade ao desenvolvimento deste trabalho.
Com esta definição, expressamos de forma clara e direta o que já havíamos visto, como dissemos, no conjunto de equações em 5. A definição acima faz uso do fato de que os elementos \( s_i\) de \( s\) são os restos \( r_i\) da divisão. Passemos, agora, ao seguinte Teorema Fundamental:
2.3. Exercícios Resolvidos
- Exercício 1
-
Escreva um código em Python, ou em sua linguagem preferida, que modele o Teorema Fundamental da Periodicidade, principalmente, o cálculo dos restos. Explique o código.
- Solução
-
Código em Python que modela o Teorema Fundamental da Periodicidade. O método
n_over_d
calcula os restos e os algarismos periódicos e não-periódicos referentes à fração \( \frac{n}{d}\).1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
def n_over_d(n,d,b=10): ''' Calculates the basic periodic information about the rational n/d representation. Args: n: numerator. d: denominator. b: base. Returns: A dictionary with the 4 following key-value items, with the values as tuples: - All the args as above. - first non-repeating remainders. - the repeating remainders. - first non-repeating decimals. - the repeating decimals. ''' dic = {} dic['n'] = n dic['d'] = d dic['b'] = b dic['integer part'] = n // d alpha = None alpha_tilde = None first_remainder = n - dic['integer part'] * d repeating_period_end = False decimals = [] remainders = [first_remainder] repeating_period_first_remainder = None i = 0 while not repeating_period_end: remainder = (b * remainders[i]) % d decimals.append( int((b * remainders[i] - remainder) / d) ) if remainder in remainders: repeating_period_end = True repeating_period_first_remainder = remainder break remainders.append(remainder) i += 1 dic['alpha-tilde'] = remainders.index(repeating_period_first_remainder) dic['alpha'] = i + 1 - dic['alpha-tilde'] dic['non-repeating remainders'] = tuple(remainders[:dic['alpha-tilde']]) dic['repeating remainders'] = tuple(remainders[dic['alpha-tilde']:]) dic['non-repeating decimals'] = tuple(decimals[:dic['alpha-tilde']]) dic['repeating decimals'] = tuple(decimals[dic['alpha-tilde']:]) return dic
Nas linhas 16 até 20, eu defino ou inicializo um dicionário,
dic
, que já contém, de saída, os valores do numerador (n), do denominador (d), da base (b) e da parte inteira,dic['integer part']
, do resultado da fração \( \frac{n}{d}\).Nas linhas 22 até 30, variáveis e vetores com nomes sugestivos (em inglês) são também inicializados com valores adequados às operações que serão realizadas no interior do laço
while
que começa na linha 31.Note como a linha 24 do código Código que calcula as sequências s e a, em Python acima contém a operação equivalente à que está na segunda e terceira linhas de n dividido por d, na coluna de continhas, e que corresponde ao cálculo do \( r_0\) (que na 3ª linha já aparece multiplicado pela base 10).
O laço
while
é executado enquanto o último resto do período verdadeiro não for encontrado, o que, de acordo com o Teorema 1 , ocorre na primeira vez em que um resto que já esteja no conjunto de restos do vetorremainders
, seja novamente calculado. Veja o escopo doif
da linha 34. Se esteif
for verdadeiro, ou seja, se oremainder
da vez, já estiver no vetorremainders
, então, o laçowhile
é interrompido (break
).Quando o
while
é interrompido, o dicionáriodic
é atualizado com as informações colhidas: número de elementos no período verdadeiro (alpha: \( \alpha\)), número de elementos no período falso, se houver (alpha-tilde: \( \tilde{\alpha}\)), e os restos e algarismos do período falso e do verdadeiro, respectivamente, sob as chavesnon-repeating remainders
,non-repeating decimals
,repeating remainders
erepeating decimals
, os quais correspondem aos elementos de \( s\) e aos elementos de \( a\) (equação 12).
Uma tradução para Javascript do Código que calcula as sequências s e a, em Python está rodando neste livro e é responsável pela geração automática de valores nas Seções de Exercícios!
- 2: Utilize, mais uma vez, os campos abaixo para informar numeradores (n) e denominadores (d) para calcular e exibir, automaticamente, os restos e os algarismos da divisão \( \frac{n}{d}\). Utilize diferentes combinações de \( n\), \( d\) e \( b\) para tentar encontrar combinações que geram períodos falsos e as que não geram. Testando números cada vez maiores para o denominador, você provavelmente verá que o seu navegador começará a demorar para responder e eventualmente poderá travar ou deixar de responder para números realmente muito grandes!
Denominador:
Base:
3. Uma Fórmula para o Cálculo Direto dos Restos de s
A sequência \( s(b,m,n)\) é uma sequência infinita que é composta pela justaposição de infinitas subsequências finitas. Este é um fato diretamente observável na dízima de \( \frac{m}{n}\) e repetitível já que, cada vez que calculamos \( \frac{m}{n}\), podemos constatar que há \( \alpha(b,m,n)\) algarismos dizimais que se repetem na mesma ordem.
Com o que temos, até agora, se quisermos conhecer o elemento \( i\) de \( s=\{r_i\}_{i=0}^{\infty}\), temos que calcular cada um dos seus elementos separadamente, ou seja, temos que realizar \( i\) cálculos a partir de \( r_0\) se desejamos conhecer o elemento \( i\) de \( s\).
Mas, podemos dar um passo além e verificar uma fórmula simples
com a qual conseguiremos calcular qualquer um dos elementos \( r_i=s_i\) de \( s\) de uma única feita. Veremos que esta pequena fórmula interessante é muito mais útil analiticamente do que operacionalmente. É que tanto bases quanto expoentes podem ficar muito grandes e inviabilizar o seu tratamento em nível numérico.
Mas, veremos que esta pequena fórmula nos renderá uns bons avanços na direção em que queremos seguir. Para isto, vamos provar o seguinte teorema.
3.1. Alguns Corolários
O corolário a seguir é só a formalização do que já devíamos estar esperando: multiplicar, módulo n, qualquer \( r_i\in s\) por \( b^j\), leva ao resto que está na posição \( j\) depois do resto \( r_i\), ou seja, leva ao resto \( r_{i + j}\).
O corolário seguinte apenas formaliza o que já sabemos, de coração, que é: a \( \alpha\) posições após um resto \( r_i\), encontramos o mesmo resto \( r_i\) novamente.
4. Conhecendo Um Pouco Melhor os Restos
Precisamos começar a conhecer melhor quem são os restos, \( r_i\), na divisão de \( m\) por \( n\). Para isto, podemos nos perguntar quem são os fatores que dividem, ao mesmo tempo, a cada um dos restos de \( s(b,m,n)\).
Os quatro teoremas seguintes são uma ajuda importante nesta tarefa.
Para começar, o próximo Teorema 3 , abaixo, nos diz que há uma relação interessante entre qualquer \( r_i\) e o produto \( b\cdot r_0\), que envolve o resto inicial de \( s(b,m,n)\). Esta relação envolve o conceito de máximo divisor comum, ou \( mdc\), entre a quantidade \( b\cdot r_0\) e o denominador, \( n\), da divisão. Este divisor comum, ele próprio, pode ter alguns de seus fatores em \( b\) e outros em \( r_0\). Note que frisamos esta possibilidade no argumento do \( mdc\) que consta da hipótese do teorema.
Nós ainda refinaremos muito mais o conhecimento sobre a composição interna dos restos, mas, por ora, vamos apreender o seguinte fato bem básico.
Mas, podemos restringir a nossa hipótese apenas à possibilidade que envolve \( r_0\), ao invés de \( br_0\), como acima. O estabelecimento desta hipótese é muito mais um ato de vontade cuja consequência matemática imediata se amolda perfeitamente na mesmíssima forma expressa na tese do teorema anterior. Esta vontade é uma vontade restritiva: desejamos restringir o máximo divisor comum apenas a \( r_0\) e \( n\) e não mais a \( br_0\) e \( n\).
Deste modo, a prova cabível, mesmo neste contexto ligeiramente modificado, acaba por ser, ainda assim, a mesmíssima que a do Teorema 3 acima.
O próximo teorema é, em verdade, um corolário do Teorema 4 . Ele afirma que todos os restos \( r_i\) que seguem um dado resto, \( r_{\bar i}\), em \( s(b,m,n)=\{r_0,\dots,r_{\bar i},\dots, r_i,\dots\}\) devem ser divisíveis pelos divisores simultâneos de \( r_{\bar i}\) e \( n\).
Por fim, podemos já concluir que todos os restos do período verdadeiro têm o mesmo divisor máximo com \( n\). Nós logo veremos que um mesmo denominador \( n\) pode ter várias sequências \( s(b,m,n)\) ligadas a si a depender do valor do numerador \( m\) e que isto tem tudo a ver com o \( mdc\) que os restos de \( s\) têm com \( n\).
4.1. Exercícios
-
Utilize os campos abaixo para gerar os restos de \( s(b,m,n)\) para a base (\( b\)), numerador (\( m\)) e denominador (\( n\)) que você escolher. Teste várias triplas de números para verificar os resultados dos teoremas desta Seção. Utilize expressões numéricas em qualquer um dos campos. Por exemplo, para testar o Teorema 3 , eu digitaria, digamos, a expressão numérica 2*5 no campo "Base", e 2*5*7*11 no campo "Denominador" e tentaria verificar se os restos gerados são todos, \( i>0\), de fato, divisíveis pelo fator comum \( 2\) ou pelo outro fator comum \( 5\). O "Numerador" pode ser qualquer valor não-negativo. Após isto, eu substituiria o fator \( 2\) pelo fator \( 3\) em ambos os campos e tentaria verificar se todos os restos, \( i>0\), serão divisíveis por \( 3\), e assim por diante.
Denominador:
Base:
5. A Fórmula do Número de Algarismos no Falso Período
No seguinte teorema utilizaremos a noção do "menor inteiro". Se \( y = \lceil x \rceil\), então se diz que "y é o menor inteiro que é maior ou igual a x", a função teto.
5.1. Algumas Consequências da Possibilidade de se Contar o Número de Elementos do Falso Período
Deste Teorema 7 decorrem alguns resultados bem interessantes. O primeiro deles é o seguinte corolário.
Agora, vamos começar a reconhecer que subsequências infinitas de uma dada \( s(b,m,n)\) também são sequências dos restos de alguma fração \( \frac{r_i}{n}\) em que \( r_i\in s(b,m,n)\) e \( r_i\) é o resto zero de \( s(b,r_i,n)\). Veremos isto em grande detalhe no próximo livro, o qual tratará de \( \alpha\), o número de elementos do período verdadeiro.
Por ora, vamos restringir estas observações aos termos do Teorema 7 e afirmarmos o seguinte corolário que reconhece que qualquer \( s\) é a justaposição da sequência finita de um possível falso período e a sequência de infinitos períodos verdadeiros.
No Teorema 6 vimos que os restos do período verdadeiro têm todos o mesmo \( mdc\) com \( n\). No próximo corolário, veremos, mais de perto, de que modo o \( mdc\) dos restos do período falso são variáveis. Há um crescimento, em magnitude, dos \( mdc\)'s nos restos do período falso desde o primeiro até o último.
Agora, o próximo corolário mostra que o \( mdc\) fixo que os restos do período verdadeiro têm com o denominador \( n\) é igual ao tido, com o mesmo \( n\), pelo último resto do período falso, \( r_{\widetilde{\alpha}}\).
A seguinte consequência do Teorema 7 é muito mais um jeito bem indireto de enfatizar que se alguma sequência de restos tem um falso período, então, não é possível que os restos deste falso período tenham \( mdc\) unitário com \( n\), do que um resultado mais útil. O \( mdc\) unitário, neste caso, significaria que a tal sequência não tem um falso período.
Dito de outro modo, se supusermos, contraditoriamente, que uma sequência de restos, em que o último resto do período falso tivesse \( mdc\) unitário com \( n\), então, tal sequência não teria qualquer resto no período falso.
Finalmente, o corolário a seguir é um reflexo de que a existência e tamanho de um falso período dependem primeiramente da relação entre os fatores primos da base, \( b\), e os do denominador, \( n\).
Ele também dá uma das primeiras dicas indiretas ou levanta as primeiras suspeitas de que é possível fazer operações do tipo \( r\cdot s(b,1,n)=s(b,r,n)\). Começaremos a ver algo disto no próximo livro.
5.2. Exercícios
-
Utilize expressões numéricas adequadas nos campos Numerador (que, neste caso, é \( r_0\)), Denominador e Base, abaixo, para testar a afirmação do Teorema 7 . Para facilitar os testes, deixei à mão, logo abaixo, a lista dos primeiros 200 números primos abaixo.
-
Exemplo: Digamos que lidemos com os valores com as seguintes fatorações primas: \( r_0=2^2\cdot 3^3\cdot 5^5\) (no campo do numerador, utilize a expressão: 2^2 * 3^3 * 5^5), \( n=3^9\cdot 5^5\) (3^9 * 5^5) e , \( b=3^2\cdot 5^5\cdot 7^7\) (3^2 * 5^5 * 7^7). Assim, o \( mdc(b,n)=3^2\cdot 5^5\). Deste modo, a potência prima contida no \( mdc(b,n)\) que aparece também em \( n\) e \( r_0\) com a maior diferença entre os expoentes respectivos é \( 3^2\) que, em \( n\), \( r_0\) e \( b\), aparecem com os expoentes \( 9\), \( 3\) e \( 2\), respectivamente. Então, de acordo com o Teorema 7 , o valor de \( \tilde{\alpha}(b,r_0,n)\) (alfa-til) deverá ser \(\left \lceil \frac{9-3}{2} \right \rceil=3\). Convido o leitor a apreciar o fato de que o número \( 3\) recém obtido, foi numericamente calculado, mas que os resultados automáticos obtidos abaixo, são resultado de trabalho computacional realizado sob os ditames do Teorema 7 e que, por esta causa, estes resultados computacionais são uma maravilhosa confirmação da teoria que apresentamos até aqui!
-
-
Tome primos da lista abaixo ou produtos entre eles para formar \( b\), \( r_0\) e \( n\) de modo que \( mdc(b,n)=1\) e verifique se estes exemplos obedecem ao Corolário 1 .
-
Agora que você já sabe que se \( mdc(b,n)>1\), aí, \( s(b,r_0,n)\) terá um falso período, teste, com alguns exemplos, a validade do Corolário 2 . Use a lista de números primos abaixo para compor números \( b\), \( r_0\) e \( n\) e usar os campos de geração automática de modo a mostrar que \( s_1(b,r_{\tilde{\alpha}},n)\subset s\) não tem um falso período. Este fato estará evidente nos restos computados de \( s\). Mas, você ainda poderá identificar visualmente o \( r_{\tilde{\alpha}}\) para, então, calcular \( s_1\) diretamente (não como uma subsequência de \( s\)).
-
Com base em tudo o que vimos nesta Seção, sugira quaisquer 3 triplas (\( b\), \( r\), \( n\)) que satisfaça o Corolário 6 .
Lista dos primeiros 200 números primos: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223
Denominador:
Base:
6. Um Teste de Primalidade com Base no Número \(\widetilde{\alpha}\)
Os conhecimentos que auferimos a partir o Teorema 7 nos abrem, agora, a possibilidade de construirmos um algoritmo com o qual poderemos determinar se um número, \( b\), é primo ou, caso contrário, achar todos os seus divisores.
Isto é possível, pois o teorema 7 nos mostrou a relação que há entre o número de elementos no falso período e a existência de fatores comuns entre o denominador, \( n\), e a base, \( b\), ou seja, sempre que estes fatores comuns existirem, \( \tilde{\alpha}(b,r,n)\ge 1\).
Além disto, uma peça-chave do algoritmo que apresentaremos será dada no próximo teorema. Trata-se de um fato que conhecemos bem, na base 10, e segundo o qual, às vezes, a parte quebrada de uma fração \( \frac{r}{n}\) tem, ou não, um falso período, ou seja, \( \tilde{\alpha}(b,r,n)\ge 0\), e todos os demais algarismos - os do período verdadeiro - são nulos. Na escola, normalmente se diria, como já observamos, que tal dízima é finita e não periódica, ou, se \( r_1=0\), que \( \frac{r}{n}\) é um inteiro.
Neste caso, como veremos, os restos do período verdadeiro também são todos nulos. E, na verdade, a sequência de restos do período verdadeiro de \( s\), bem como a sequência de algarismos \( a\) do mesmo período verdadeiro, ao invés de serem finitas, são infinitas de período igual a \( {0}\).
Quando um número \( n\) divide um outro número, o resto, \( r_1\), desta divisão é nulo. Sabemos disto "desde sempre"! O ponto aqui, é que, agora, este fato básico aparece enquadrado em um esquema mais geral e, junto com outro fato que exporemos no Teorema 8 , abaixo, poderá ser utilizado para sondar não só a divisibilidade mas, antes, também a ocorrência de fatores comuns entre \( n\) e \( b\) - o que exporá o fato, caso ele ocorra, de que a base \( b\) não é um número primo.
O seguinte Teorema 8 aborda o efeito que se observa nos restos quando o produto \( br_0\) e o denominador têm, um com o outro, todos os fatores primos em comum.
O próximo Teorema 9 contém o cerne do algoritmo que delinearemos. Ele afirma e prova uma verdade muito acessível: se a fração \( \frac{r}{n}\) não exibe um período falso para qualquer denominador \( n\in \{2,..., b-1\}\), então, \( b\) é um número primo. E, deste modo, somos capazes de determinar se um número é primo ou composto, apenas fazendo continhas de divisão! Isto é algo surpreendente ainda que \( \frac{r}{n}\) deva ser expressa numa, não usual, base \( b \neq 10\).
6.1. Um Método para Determinar se um Número é Primo ou Descobrir os seus Divisores se Ele for Composto
6.1.1. O Algoritmo "Básico"
O algoritmo seguinte visa a determinar se um número \( b\) é primo ou não. Se \( b\) for composto, o algoritmo achará todos os divisores de \( b\).
A entrada do algoritmo é o número \( b\) que se deseja testar e um número \( r\in\{1,\dots ,n-1 \}\) - o qual, no entanto, exceto por razões especiais, será sempre a unidade, o que simplificará os cálculos. Quando fazemos \( r_0=1\), a base \( b\) passa a fazer as vezes do numerador! Veja o lado mais à esquerda de 83 para apreciar este fato simples. Durante a execução do algoritmo, os números \( n\in\{2,\dots, b-1\}\) poderão ser utilizados.
O número \( b\) é, de fato, a base em que a fração \( \frac{r}{n}\) é expressa e por esta razão utilizei o trocadilho no título desta Seção.
O leitor verá, logo abaixo, que utilizaremos \( \left\lceil\sqrt{b}\right\rceil\) (função "Menor Inteiro", ou seja, "o menor número inteiro que é maior ou igual que \( \sqrt{b}\)") em lugar de \( b\).
Isto, diminui pela metade o número de passos gerais do algoritmo e tem a ver com um critério que é conhecido como o Crivo de Erastóstenes. Não entrarei nos seus detalhes aqui. O seu entendimento é simples, o seu enunciado preciso e explicações sumárias podem ser encontradas online, e o seu uso é imediato.
O crivo tem a ver com a constatação de que se um número é composto, então, pelo menos, um dos seus divisores deve ser menor do que a sua raiz quadrada. Deste modo, se você estiver testando divisores, em ordem crescente, e não encontrar qualquer um que seja menor ou igual à raiz, então, não é preciso testar mais, pois, não haverão outros divisores, em virtude de o tal número ser primo!
6.2. Explicação de Cada Passo do Algoritmo 1
-
Neste passo, escolhemos o valor \( r=1\), como já havíamos mencionado. Isto decorre da liberdade trazida pelo Teorema 9 para se escolher qualquer valor para \( r\). Também inicializamos o valor de \( n\) com \( 2\) e indicamos este fato com os símbolos \( n\leftarrow 2\). Esta é a notação utilizada para designar a atribuição de um valor a uma variável.
-
Este passo é o mais trabalhoso. Nele, precisamos calcular os restos de \( s\). Isto pode ser feito de três formas. Podemos utilizar a fórmula 28 que foi provada no Teorema 2 ou podemos fazer a continha da divisão de \( r\) por \( n\) na base \( b\), como indicado no modelo n dividido por d, apenas usando \( b\) em lugar de \( 10\) e mantendo um olho nos restos da divisão, ou ainda, calculando cada uma da congruências tal como feito em 6. Já vimos que \( s\) pode ter ou não um falso período. Em todo o caso, os cálculos devem ser feitos cuidando-se em observar a primeira vez em que um resto repete um resto previamente calculado. Aí, é a hora de parar de calculá-los. Vimos isto no Teorema 1 : os restos do período verdadeiro são periódicos. Procedendo assim, fatalmente, acabaremos calculando os \( \tilde{\alpha}\) restos do possível período falso, caso haja um, e os \( \alpha\) restos do período verdadeiro. Portando, acabaremos calculando \( \tilde{\alpha}+\alpha\) restos, ainda que tenhamos \( \tilde{\alpha}=0\), eventualmente.
-
Sabemos dos teoremas 7 e 8 que se \( \tilde{\alpha}>0\) ou algum resto de \( s\) for nulo, então, a base \( b\) e o diverso denominador \( n\) têm fatores primos em comum. Se o teste feito neste item for verdadeiro e não se deseja conhecer os divisores de \( b\), o algoritmo pode parar imediatamente, pois já sabemos que \( b\) não é primo.
-
Sabemos também que se o resto \( r_1\in s\) for nulo, então, \( n\) deve dividir perfeitamente o numerador que, neste caso, é, como vimos, \( b\). Veja que se o teste feito neste ponto for verdadeiro, o algoritmo não sai mais do item 2.a.i e seus subitens.
-
Aumente o valor de \( n\) em uma unidade e atribua este valor a \( n\).
-
Já explicado.
-
Como pode haver fatores de \( b\) maiores que \( \sqrt{b}\), e queremos justamente descobrir estes fatores, devemos seguir iterando os cálculos até depois deste limiar.
-
-
-
-
Significado já explicado.
-
Aqui, como ainda não se descobriu divisores de \( b\), o limiar máximo será \( \sqrt{b}\)
-
Atingindo-se o limiar, \( b\) pode ser declarado um primo.
-
6.3. Algumas Observações
O Algoritmo 1 apresentado acima ainda não é ótimo. Esta ainda não é a sua melhor versão. Para começar, ele ainda faz, pelo menos, \( \tilde{\alpha}+\alpha\) cálculos a cada \( n\in \{2,..., b-1\}\). Isto pode ser melhorado! Em parte, esta limitação se deve ao fato de estarmos encapsulando em nosso algoritmo e, consequentemente, no código abaixo, o Código que calcula as sequências s e a, em Python inteiro, já pronto, que escrevemos acima para o cálculo de \( s\).
Só isto já mostra que entre uma teorização matemática e uma correspondente realização concreta pode haver uma distância grande, tanto maior quanto mais otimizada for a realização e mais ajustada a exigências concretas. Mas, por ora, a versão atual serve como prova da sanidade da teoria que está por trás dela. Logo, elementos deste algoritmo serão utilizados em algoritmos mais otimizados. Mas, antes disto, temos que desenvolver um pouco mais a teoria.
O algoritmo acima e o código abaixo servem para se descobrir primos. Assim, faz sentido ajustá-lo para ser possível opera-lo apenas em modo de descoberta. Neste caso, poderíamos criar um banco de dados para armazenar os primos já descobertos e testar novos candidatos a primo com base neste banco de modo a diminuir o número de cálculos do teste e, deste modo, torna-lo mais rápido.
6.4. O Algoritmo 1 em Código
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def is_b_prime(b):
'''
Tests the base primality.
This test is not optimal yet. It makes alpha + aplha-tilde calculuses for each d in {2,...,limit}.
But it serves as a proof of soundness of the theory behind it.
Args:
b: base to be tested.
Returns:
Two possible outcomes:
divisors: list of all b divisors, in case b is composite. Or,
'prime': string whose meaning is clear.
'''
primality = 'indefinite'
divisors = []
limit = int(b**(0.5)) + 1 # Erastosthenes sieve limit.
for d in range(2, b):
nod = n_over_d(1, d, b=b)
if nod['alpha-tilde'] == 1 and 0 in nod['repeating remainders']: # Este '1' é um falso positivo!
primality = 'composite'
divisors.append(d)
elif nod['alpha-tilde'] > 0:
primality = 'composite'
elif primality == 'indefinite' and d > limit:
primality = 'prime'
break
if primality == 'composite':
return divisors
else:
return 'prime'
6.5. Exercícios
- Exercício 1
-
Conceba uma outra solução, em código, que calcule todos os primos até um número limite, \( b\), dado como argumento de entrada. Os primos calculados devem ser armazenados ordenadamente de modo permanente. O algoritmo deve utilizar apenas este banco de dados permanente para a descoberta de primos maiores do que todos os já armazenados - isto tende a reduzir o tempo de execução da busca por primos novos, pois não testa sobre todos os inteiros; testa apenas sobre os primos já conhecidos. E, deve simplesmente informar a lista dos primos menores ou iguais a \( b\), se \( b\) for menor ou igual que o maior primo já armazenado. O algoritmo pode começar com um banco de dados já alimentado com uma lista, ordenada por tamanho, de todos os primeiros primos que o leitor conheça.
- Solução
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def all_primes_until_b_with_DB(b, DB_name = ''):
'''
Searches all primes til base b, inclusive.
Feeds an ordered prime list if it exists; otherwise, creates one.
Saves the ordered list for future use.
Finds new primes using just the primes already saved.
Args:
b: integer number until which search is made.
DB_name: name of the database file.
Returns:
A list of all primes til b.
'''
known_primes = []
if DB_name == '':
DB_name = 'prime_database.pkl'
known_primes = [2,3,5,7,11,13,17,19,23]
print(f'Nenhum banco de primos foi informado! O conjunto inicial, mínimo de primos, {known_primes}, será utilizado.')
else:
try:
with open(DB_name, 'rb') as f:
known_primes = pickle.load(f)
print("Objeto carregado com sucesso.")
except FileNotFoundError:
print(f"Erro: o arquivo {DB_name} não foi encontrado.")
return
except pickle.UnpicklingError:
print(f"Erro ao desempacotar o arquivo {DB_name}. Ele pode estar corrompido ou seu conteúdo não ser compatível.")
return
if known_primes == []:
known_primes = [2,3,5,7,11,13,17,19,23]
if b <= known_primes[-1]:
return [i for i in known_primes if i <= b]
primality = 'indefinite'
n1 = known_primes[-1] + 2
new_primes = []
for i in range(n1, b + 1):
for j in known_primes:
nod = n_over_d(1, j, b=i)
if nod['alpha-tilde'] > 0:
primality = 'composite'
break
if primality == 'composite':
primality = 'indefinite'
continue
else:
new_primes.append(i)
print(f'A lista original era a seguinte: {known_primes}.')
print(f'Nesta sondagem foram encontrados os seguintes números primos: {new_primes}.')
known_primes = known_primes + new_primes
with open(DB_name, 'wb') as f:
pickle.dump(known_primes, f)
return known_primes
- Explicação do Código
-
Nas linhas 13 até 28, cuida-se de verificar se já existe um arquivo contendo uma lista prévia de primos ou cria-se um ao fim do código nas linhas 54 e 55, com o nome
prime_database.pkl
, caso ele não exista. Este autor usou a lista inicial[2,3,5,7,11,13,17,19,23]
de 9 primos, mas o leitor pode utilizar uma lista maior desde que ela seja completa. O armazenamento é feito serializando-se a lista final de primos. Para isto, utilizamos a bibliotecaPickle
da linguagemPython
.As linhas 30 e 31 inicializam a variável
known_primes
, caso ela ainda não contenha uma lista de primos.As linhas 32 e 33, testam para ver se o argumento \( b\) é menor que o último elemento da lista
known_primes
. Se for, o código simplesmente termina retornando a lista de todos os primos até \( b\) já armazenados.As linhas 35 a 48 são as mais especiais. Elas passam por todos os inteiros que estiverem entre
n1
(o segundo inteiro após o último primo deknown_primes
, poisn1 - 1
é par!) e \( b\), inclusive, testando-os apenas contra os primos deknown_primes
para ver se algum destes inteiros são também primos, para, no fim, anexa-los aknown_primes
. O teste realizado aqui, é o teste do Teorema 9 . A linha 41, testa para ver se o número de restos do falso período é maior que zero, caso em que a negação do lado direito da dupla implicação da proposição do Teorema leva também à negação do seu lado esquerdo!, ou seja, o tamanho do falso período não é nulo e o número \( b\) é composto.Por fim, as linhas 54 e 55 salvam a lista de primos contida em
known_primes
que agora, provavelmente, foi aumentada com os novos primos que estavam sendo coletados na lista temporárianew_primes
.'''