A Fórmula Do
Número de Algarismos
no Falso Período Dizimal

Segunda Edição

A. P. Rodrigues

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

© 2025 por A. P. Rodrigues

Visite o canal de Youtube do autor https://www.youtube.com/@aprodriguesOficial

Envie uma mensagem para [email protected]

Visite também o website do autor em https://aprodrigues.com

Agosto 2025

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 dividido por 7.
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

\[\begin{equation} \begin{matrix} 1-7\cdot 0=1\\ 10-7\cdot 1 = 3 \\ 30-7\cdot 4 = 2 \\ 20-7\cdot 2 = 6 \\ 60-7\cdot 8 = 4 \\ 40-7\cdot 5 = 5 \\ 50-7\cdot 7 = 1 \end{matrix} \end{equation}\]

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.

\[\begin{equation} \begin{matrix} 1-1=7\cdot 0\\ 10-3 = 7\cdot 1 \\ 30-2 = 7\cdot 4 \\ 20-6 = 7\cdot 2 \\ 60-4 = 7\cdot 8 \\ 40-5 = 7\cdot 5 \\ 50-1 = 7\cdot 7 \end{matrix} \end{equation}\]

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:

\[\begin{equation} \begin{matrix} 1\equiv 1 (mod\ 7) \\ 10\equiv 3 (mod\ 7) \\ 30\equiv 2 (mod\ 7) \\ 20\equiv 6 (mod\ 7)\\ 60\equiv 4 (mod\ 7) \\ 40\equiv 5 (mod\ 7) \\ 50\equiv 1 (mod\ 7) \end{matrix} \end{equation}\]

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 dividido por d.
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

\[\begin{equation} \begin{matrix} n-d\cdot a_0=r_0\\ 10\cdot r_0-d\cdot a_0 = r_1\\ 10\cdot r_1-d\cdot a_1 = r_2\\ 10\cdot r_2-d\cdot a_2 = r_3\\ \vdots\\ 10\cdot r_{\alpha-1}-d\cdot a_{\alpha} = r_{\alpha} \end{matrix} \end{equation}\]

para, então, trocarmos membros de lado e obtermos

\[\begin{equation} \begin{matrix} n-r_0=d\cdot a_0\\ 10\cdot r_0-r_1 = d\cdot a_0\\ 10\cdot r_1-r_2 = d\cdot a_1\\ 10\cdot r_2-r_3 = d\cdot a_2\\ \vdots\\ 10\cdot r_{\alpha-1}-r_{\alpha} = d\cdot a_{\alpha} \end{matrix} \end{equation}\]

e, finalmente, fazermos a conversão de (5) para o formato congruencial

\[\begin{equation} \begin{matrix} n\equiv r_0(mod\ d)\\ 10\cdot r_0\equiv r_1 (mod\ d)\\ 10\cdot r_1\equiv r_2 (mod\ d)\\ 10\cdot r_2\equiv r_3 (mod\ d)\\ \vdots\\ 10\cdot r_{\alpha-1}\equiv r_{\alpha} (mod\ d) \end{matrix} \end{equation}\]

É 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

\[\begin{equation} \begin{matrix} n\equiv r_0(mod\ d)\\ b\cdot r_0\equiv r_1 (mod\ d)\\ b\cdot r_1\equiv r_2 (mod\ d)\\ b\cdot r_2\equiv r_3 (mod\ d)\\ \vdots\\ b\cdot r_{\alpha-1}\equiv r_{\alpha} (mod\ d) \end{matrix} \end{equation}\]

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.

1.1. Exercícios

  1. Utilize 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}\).

Numerador:
Denominador:
Base:

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

\[\begin{equation} a_0,a_1\dots a_{\tilde{\alpha}}a_{\tilde{\alpha} + 1}\dots a_{\tilde{\alpha} + \alpha}\dots \end{equation}\]

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

\[\begin{equation} s=\{r_0,r_1,\dots, r_{\tilde{\alpha}},r_{\tilde{\alpha} + 1},\dots, r_{\tilde{\alpha} + \alpha}\} \end{equation}\]

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

\[\begin{equation} a_0,a_{1}\dots a_{\alpha}\dots \end{equation}\]

e

\[\begin{equation} s=\{r_0,r_{1},\dots, r_{\alpha}\} \end{equation}\]

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.

Definição 1: Sejam \( b\in \mathbb{N}\), \( n\in \mathbb{N}-\{0\}\) e \( r_i\in\{0,...,n-1\}\). A expressão dos algarismos de uma sequência \( s\) é a sequência dos algarismos do falso período, se houver, e do período de s, e tem a seguinte forma

\[\begin{equation} a(b,r_0,n)=\{ \frac{bs_{i-1}-s_i}{n} \}_{i=1}^{\widetilde{\alpha}+\alpha} \end{equation}\]

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:

Teorema 1: Sejam \( b\in \mathbb{N}\), \( n\in \mathbb{N}-\{0\}\) e \( r_i\in\{0,...,n-1\}\). A sequência de congruências abaixo é periódica de período \( \pi\), ou seja, \( r_i=r_{i+\pi}\), podendo, ou não, haver um primeiro período que não se repete .

\[\begin{equation} \begin{matrix} b\cdot r_0 &\equiv &r_1 & (mod\ \ n)\\ b\cdot r_1 &\equiv &r_2 & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ b\cdot r_i &\equiv &r_{i+1} & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ \end{matrix} \end{equation}\]

Prova: \( \{0,...,n-1\}\) é um conjunto completo de resíduos módulo n. Todos os demais números naturais são equivalentes, módulo n, a algum resíduo contido neste conjunto.

Deste modo, qualquer sequência de congruências com mais de \( n\) congruências apresentará, pelo menos, um \( r_T\) repetido no lado direito de uma delas.

Suponha que \( r_T\) seja a primeira repetição, de fato.

Suponha que \( r_T\) repita um \( r_i\) no lado esquerdo de qualquer uma das congruências acima, ou seja, \( 0\leq i\leq T-1\).

\[\begin{equation} \begin{matrix} b\cdot r_0 &\equiv &r_1 & (mod\ \ n)\\ b\cdot r_1 &\equiv &r_2 & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ b\cdot r_i &\equiv &r_{i+1} & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ b\cdot r_{T-1} &\equiv &r_{T} & (mod\ \ n)\\ \vdots & &\vdots & \vdots \end{matrix} \end{equation}\]

Então,

\[\begin{equation} r_i=r_T \end{equation}\]

e temos as seguintes 2 equações, módulo n, advindas, respectivamente, das congruências \( i+1\) e \( T+1\) de 14.

\[\begin{equation} b \cdot r_i \equiv r_{i+1} \end{equation}\]
\[\begin{equation} b \cdot r_T \equiv r_{T+1} \end{equation}\]

Por causa de 15, a equação 18 abaixo pode ser escrita a partir de 16 e 17.

\[\begin{equation} r_{i+1} \equiv r_{T+1} \end{equation}\]

donde deve-se concluir a igualdade

\[\begin{equation} r_{i+1} = r_{T+1} \end{equation}\]

uma vez que \( r_{i+1}\) e \( r_{T+1}\), pertencendo ao mesmo conjunto de resíduos módulo n, só seriam diferentes se fossem incongruentes. Lembremos que os resíduos, módulo n, do conjunto \( \{0,...,n-1\}\) são incongruentes entre si.

Acabamos de mostrar que se houver a repetição em 14, haverá também a repetição em 19, ou seja, o resto no lado direito da congruência \( i+1\) é igual ao resto no lado direito de \( T+1\).

\[\begin{equation} \begin{matrix} b\cdot r_0 &\equiv &r_1 & (mod\ \ n)\\ b\cdot r_1 &\equiv &r_2 & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ b\cdot r_i &\equiv &r_{i+1} & (mod\ \ n)\\ b\cdot r_{i+1} &\equiv &r_{i+2} & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ b\cdot r_{T-1} &\equiv &r_{T} & (mod\ \ n)\\ b\cdot r_{T} &\equiv &r_{T+1} & (mod\ \ n)\\ b\cdot r_{T+1} &\equiv &r_{T+2} & (mod\ \ n)\\ \vdots & &\vdots & \vdots \end{matrix} \end{equation}\]

Acontece que, como podemos ver em 20, o resto \( r_{T+1}\), no lado direito da congruência \( T+1\), repete o resto \( r_{i+1}\) no lado esquerdo da congruência \( i+2\). Logo, os restos \( r_{i+2}\) e \( r_{T+2}\) devem ser iguais também, através do mesmo raciocínio que levou a 19.

Veja que o número de congruências é o mesmo, \( \pi\), entre as congruências \( i+1\) e \( T\) e entre as congruências \( T+1\) e \( i+2\).

\[\begin{equation} T-i=\ \ \pi\ \ =(T+1)-(i+1) \end{equation}\]

Suponha, então, por indução, que a partir da congruência \( i+1\) até uma congruência qualquer \( j+\pi\) tenhamos verificado que os restos se repetem de \( \pi\) em \( \pi\) congruências.

Isto quer dizer que o resto \( r_{j + \pi}\), que está a direita da congruência \( j+\pi\), repete o resto \( r_j\), à esquerda da congruência \( j+1\).

Assim, o resto \( r_{j+\pi}\) está também à esquerda da congruência \( j+\pi +1\). Qual será o valor, \( x\), do resto à direita desta congruência?

\[\begin{equation} \begin{matrix} b\cdot r_0 &\equiv &r_1 & (mod\ \ n)\\ b\cdot r_1 &\equiv &r_2 & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ \vdots & &\vdots & \vdots \\ \vdots & &\vdots & \vdots \\ b\cdot r_{j} &\equiv &r_{j+1} & (mod\ \ n)\\ \vdots & &\vdots & \vdots \\ b\cdot r_{j+\pi-1} &\equiv &r_{j+\pi} & (mod\ \ n)\\ b\cdot r_{j+\pi} &\equiv &x & (mod\ \ n)\\ \vdots & &\vdots & \vdots \end{matrix} \end{equation}\]

A resposta vem da comparação entre as congruências \( j+1\) e \( j+\pi+1\).

\[\begin{equation} b\cdot r_{j} \equiv r_{j+1} (mod\ \ n) \end{equation}\]
\[\begin{equation} b\cdot r_{j+\pi} \equiv x (mod\ \ n) \end{equation}\]

Já que

\[\begin{equation} r_j=r_{j+\pi} \end{equation}\]

teremos, de 23 e 24 que

\[\begin{equation} r_{j+1}\equiv x(mod\ \ n) \end{equation}\]

donde se conclui que

\[\begin{equation} r_{j+1}= x \end{equation}\]

uma vez que ambos pertencem ao conjunto \( \{0,...,n-1\}\), de elementos incongruentes entre si, a congruência em 26 só pode valer se a igualdade em 27 valer também.

Mas \( x\) é \( r_{j+\pi+1}\). Logo, mostramos que, a partir da congruência \( T\), todo o resto repete o resto que está à direita \( \pi\) congruências atrás.

Por fim, os restos \( r_1,..., r_{i-1}\) são um primeiro período que não se repete . Este falso período só existirá se \( r_T\) repetir um resto diferente de \( r_0\). Como queríamos demonstrar.

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 vetor remainders, seja novamente calculado. Veja o escopo do if da linha 34. Se este if for verdadeiro, ou seja, se o remainder da vez, já estiver no vetor remainders, então, o laço while é interrompido (break).

Quando o while é interrompido, o dicionário dic é 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 chaves non-repeating remainders, non-repeating decimals, repeating remainders e repeating 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!
Numerador:
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

\[\begin{equation} r_i \equiv b^{i} \cdot r_0 (mod\ \ n) \end{equation}\]

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.

Teorema 2:

\[\begin{equation} s(b,r_0,n) \ \ =\ \ \{r_i\}_{i=0}^{\infty } \Longleftrightarrow s_i= r_i \equiv b^{i} \cdot r_0 (mod\ \ n) \end{equation}\]

Prova: Parte \( \Longrightarrow\).

Do Teorema Fundamental, sabe-se que para cada \( i\)

\[\begin{equation} s(b,r_0,n) \ \ =\ \ \{r_i\}_{i=0}^{\infty } \Longleftrightarrow b\cdot r_i\equiv r_{i+1}(mod\ \ n) \end{equation}\]

Logo, a primeira congruência de \( s\) é

\[\begin{equation} b \cdot r_0 \equiv r_1 (mod\ \ n) \end{equation}\]

A segunda congruência de \( s\) é

\[\begin{equation} b \cdot r_1 \equiv r_2 (mod\ \ n) \end{equation}\]

Agora, suponha, por indução, que tenhamos verificado que 30 vale até \( i-1\), de modo que valha

\[\begin{equation} b^{i-1} \cdot r_0 \equiv r_{i-1} (mod\ \ n) \end{equation}\]

Mas, a congruência \( i\) de \( s\) é

\[\begin{equation} b \cdot r_{i-1} \equiv r_i (mod\ \ n) \end{equation}\]

Substituindo de 33 em 34, obtém-se o lado direito da equivalência lógica do teorema.

Parte \( \Longleftarrow\).

Se se tem o lado direito da equivalência lógica deste Teorema para todo \( i\), então, para cada \( i>0\) podemos escrever

\[\begin{equation} (mod\ \ n) s_i= r_i \equiv b^{i} \cdot r_0 \equiv b\cdot (b^{i-1}\cdot r_0) \equiv b\cdot r_{i-1} \end{equation}\]

que de acordo com 30 implica no lado esquerdo da dupla implicação deste teorema, C.Q.D.

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}\).

Corolário 1 do Teorema 2 :

\[\begin{equation} r_{i+j} \equiv b^{j} \cdot r_i (mod\ \ n) \end{equation}\]

Prova: O lado direito da dupla implicação em 30, nos permite escrever, módulo n, a seguinte agradável congruência

\[\begin{equation} b^j r_{i} \equiv b^j b^{i} r_0 \Longrightarrow b^j r_{i} \equiv b^{i+j} r_0 \Longrightarrow b^j r_{i} \equiv r_{i+j} \end{equation}\]

C.Q.D.

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.

Corolário 2 do Teorema 2 : Seja \( \alpha\) o número de elementos no período verdadeiro de \( s\) e seja \( r_i\in s\) qualquer resto deste período verdadeiro, ou seja, \( \tilde{\alpha}\le i\). Então,

\[\begin{equation} b^{\alpha}r_i\equiv r_i(mod\ \ n) \end{equation}\]

Prova:

Do Corolário 1 , podemos escrever

\[\begin{equation} b^{\alpha} r_{i} \equiv r_{\alpha+i} \end{equation}\]

mas, como \( r_i\) pertence ao período verdadeiro e este tem \( \alpha\) elementos, segue que \( r_i=r_{i+\alpha}\). Daí, vem o resultado que desejamos. C.Q.D.

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.

Teorema 3: Seja \( s =\{r_i\}_{i=1}^{\infty}\) e seja \( mdc(b\cdot r_0,n)=d\), então, para todo \( i>0\),

\[\begin{equation} d |r_i \end{equation}\]

Prova: O elemento \( i\) de \( s\), módulo n, é

\[\begin{equation} s_i= r_i\equiv b^{i}\cdot r_0 \end{equation}\]

Daí, vem que

\[\begin{equation} \begin{matrix} n |(b^{i}\cdot r_0-r_i)\ \ \Longrightarrow\ \ d |(b^{i}\cdot r_0-r_i)\ \ \Longrightarrow\ \ \newline \Longrightarrow\ \ \frac{(b^{i}\cdot r_0-r_i)}{d}=m\in\mathbb{Z} \ \ \Longrightarrow \newline \Longrightarrow\ \ b^{i}\cdot r_0-dm=r_i \ \ \Longrightarrow\ \ d | r_i \end{matrix} \end{equation}\]

Como queríamos demonstrar.

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.

Teorema 4: Seja \( s =\{r_i\}_{i=1}^{\infty}\) e seja \( mdc(r_0,n)=d\), então, para todo \( i>0\),

\[\begin{equation} d |r_i \end{equation}\]

Prova: O elemento \( i\) de \( s\), módulo n, é

\[\begin{equation} s_i= r_i\equiv b^{i}\cdot r_0 \end{equation}\]

Daí, vem que

\[\begin{equation} \begin{matrix} n |(b^{i}\cdot r_0-r_i)\ \ \Longrightarrow\ \ d |(b^{i}\cdot r_0-r_i)\ \ \Longrightarrow\ \ \newline \Longrightarrow\ \ \frac{(b^{i}\cdot r_0-r_i)}{d}=m\in\mathbb{Z} \ \ \Longrightarrow \newline \Longrightarrow\ \ b^{i}\cdot r_0-dm=r_i \ \ \Longrightarrow\ \ d | r_i \end{matrix} \end{equation}\]

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\).

Teorema 5: Seja \( mdc( r_{\bar i},n)=d\), então para todo \( i>\bar i\),

\[\begin{equation} d |r_{ i} \end{equation}\]

Prova: O elemento \( \bar i +1\) de \( s\), módulo n, é

\[\begin{equation} br_{\bar i}\equiv r_{\bar i +1} \end{equation}\]

Daí vem que

\[\begin{equation} \begin{matrix} n |(b\cdot r_{\bar i}-r_{\bar i+1}) \ \ \Longrightarrow\ \ d |(b\cdot r_{\bar i}-r_{\bar i+1}) \ \ \Longrightarrow\ \ \newline \Longrightarrow\ \ \frac{(b\cdot r_{\bar i}-r_{\bar i+1})}{d}=m\in\mathbb{Z} \ \ \Longrightarrow \newline \Longrightarrow\ \ b\cdot r_{\bar i}-dm=r_{\bar i+1} \ \ \Longrightarrow\ \ d | r_{\bar i+1} \end{matrix} \end{equation}\]

Agora, para concluir a prova, por indução, deve-se supor que se observou que todos os restos até um dado \( I> \bar i\) são divisíveis por \( d\), para, então, escrever-se uma equação análoga a 47 para \( I+1\) e, por fim, terminar a provar com uma expressão análoga a 48. Como queríamos demonstrar.

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\).

Teorema 6: Todo resto do período verdadeiro de \( s(b,r_0,n)\) tem o mesmo mdc com \( n\).

Prova: Sejam quaisquer \( j < k\), maiores ou iguais que o número de elementos, \( \tilde{\alpha}\), no possível falso período.

De acordo com o Teorema 5 ,

\[\begin{equation} d_1=mdc(r_j,n)\ \ |\ \ r_k \end{equation}\]

Mas, em virtude da periodicidade do período verdadeiro de \( s\), há um \( i\geq 0\) para o qual \( k<j+i\alpha\) e \( r_j=r_{j+i\alpha}\).

Novamente, de acordo com o Teorema 5 ,

\[\begin{equation} d_2=mdc(r_k,n)\ \ |\ \ r_j=r_{j+i\alpha} \end{equation}\]

De 49 vem que \( d_1 \leq d_2\), já que \( d_1\) divide \( n\) e \( r_k\); mas de 50, segue que \( d_2 \leq d_1\), uma vez que \( d_2\) divide \( n\) e \( r_j=r_{j+i\alpha}\). A conclusão é que

\[\begin{equation} d_1 = d_2 \end{equation}\]

4.1. Exercícios

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

Numerador:
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.

Teorema 7: Seja \( P= \{ p_1,\dots,p_c,\dots,p_{\tau} \}\) o conjunto dos fatores primos que pertencem à fatoração de \( b\), \( r_0\) ou \( n\).

Consideremos, para os objetivos deste teorema, que as suas fatorações tenham, cada uma, todos os elementos de \( P\), ainda que com expoente nulo, de modo que possamos escrever \( b=\prod_{c=1}^{\tau}p_c^{e_{b,c}}\), \( r_0=\prod_{c=1}^{\tau}p_c^{e_{r_0,c}}\) e \( n=\prod_{c=1}^{\tau}p_c^{e_{n,c}}\).

Então, o número de restos no falso período de \( s(b,r_0,n)\) é

\[\begin{equation} \widetilde{\alpha}(b,r_0,n) = \begin{cases} 0 & \text{ se mdc(b,n)=1}\\ \max_c \left\lceil \frac{e_{n,c}-e_{r_0,c}}{e_{b,c}} \right\rceil & \text{ caso contrário } \end{cases} \end{equation}\]

Prova: De acordo com o Teorema 2 , todos os restos \( r_i\in s\) podem ser calculados a partir de \( r_0\) da seguinte forma

\[\begin{equation} r_i \equiv b^{i} \cdot r_0 (mod\ \ n) \end{equation}\]

Então, para qualquer \( i\) tem-se

\[\begin{equation} \begin{matrix} \frac{b^ir_0-r_i}{n} &=& \frac{(\prod_{c=1}^{\tau}p_c^{e_{b,c}})^i \prod_{c=1}^{\tau}p_c^{e_{r_0,c}} -r_i } { \prod_{c=1}^{\tau}p_c^{e_{n,c}} }\\ &=& \frac{\prod_{c=1}^{\tau}p_c^{ie_{b,c}+e_{r_0,c}} -r_i } { \prod_{c=1}^{\tau}p_c^{e_{n,c}} } \in \mathbb{Z} \end{matrix} \end{equation}\]

Se \( br_0\) e \( n\) tiverem divisores comuns, então, podemos nos perguntar sobre o máximo divisor comum entre eles, o que, por definição, é

\[\begin{equation} mdc(br_0,n)=\prod_{c=1}^{\tau} p_c^{\min\{e_{b,c}+e_{r_0,c},e_{n,c}\}} \end{equation}\]

Do lado mais à direita de 54 e do Teorema 3 , sabemos que \( \prod_{c=1}^{\tau} p_c^{\min\{e_{b,c}+e_{r_0,c},e_{n,c}\}}\) em 55 deve dividir \( r_i\) em 54.

Mas, o expoente presente em 55 corresponde ao expoente no numerador do membro mais à direita de 54, quando \( i=1\).

O importante a percebermos, agora, é que, enquanto \( i\) for tal que

\[\begin{equation} i\cdot e_{b,c}+e_{r_0,c}=\min\{i\cdot e_{b,c}+e_{r_0,c},e_{n,c}\} \end{equation}\]

teremos que ter

\[\begin{equation} \begin{matrix} mdc(b^i r_0,n)&=&\prod_{c\in P} p_c^{\min\{i\cdot e_{b,c}+e_{r_0,c},e_{n,c}\}}\\ &=&\prod_{c\in P} p_c^{i\cdot e_{b,c}+e_{r_0,c}} \end{matrix} \end{equation}\]

visto que \( e_{b,c}\), \( e_{r_0,c}\) e \( e_{n,c}\) são todos expoentes, não nulos, de um mesmo fator primo que está presente em \( br_0\) e \( n\).

Entretanto, é preciso perceber que \( i\), em 53, cresce ilimitadamente, mas que

\[\begin{equation} \prod_{c\in P}p_c^{i\cdot e_{b,c}+e_{r_0,c}}\ \ \nmid\ \ r_i \end{equation}\]

para todo \( i\), já que \( r_i\in\{0,\dots,n-1\}\), pois \( \prod_{c\in P}p_c^{i\cdot e_{b,c}+e_{r_0,c}}\) ficará, eventualmente, bem maior que \( r_i\). Perceba que, quando \( i\) é tal que 58 começa a valer, então, o lado direito de 54 deixa de pertencer a \( \mathbb{Z}\), visto que, se valesse, o seu denominador teria fatores comuns com apenas uma das parcelas do numerador.

Então, cabe agora perguntar para qual \( i\) começa a valer 58, pois, a partir dele, de acordo com 55, deve começar a valer

\[\begin{equation} mdc(b^i r_0,n)=\prod_{c\in P} p_c^{e_{n,c}} \end{equation}\]

Em qualquer caso, o maior \( i\), chamemo-lo de \( \tilde{i}\), que ainda torna 55 verdadeira, satisfaz também a seguinte inequação

\[\begin{equation} \tilde{i}\cdot e_{b,c}+e_{r_0,c}\ge e_{n,c} \end{equation}\]

É preciso perceber que há \( \tau\) inequações em 60, que se resolvem para algum \( i\), e que, portanto, o \( \tilde{i}\) desejado é aquele para o qual há algum \( c\) que satisfaça

\[\begin{equation} \widetilde{i} = \max_c \left\lceil \frac{e_{n,c}-e_{r_0,c}}{e_{b,c}} \right\rceil \end{equation}\]

Verifiquemos agora que o \( \widetilde{i}\) é, de fato, o número de restos no falso período. Eu afirmo que ele é.

O Teorema Fundamental afirma que a sequência \( s\) pode ter um falso período. Suponhamos que o tenha.

Seja

\[\begin{equation} s(b,r_0,n)=\{r_0,...,r_{\widetilde{i}},r_{\widetilde{i}+1},...,r_{\widetilde{i}+\alpha},...\} \end{equation}\]

em que \( r_0,...,r_{\widetilde{i}},r_{\widetilde{i} + 1},...,r_{\widetilde{i} + \alpha}\) é a sequência composta por um suposto falso período seguido da primeira ocorrência do período verdadeiro.

Deixe \( i\) variar entre \( 0\) e \( {\widetilde{i} + \alpha}\). Veja que se \( i \leq \widetilde{i}\), então, vale 57 com o lado esquerdo de 56, ou seja, \( mdc(b^i r_0,n)\) varia com \( i\), o que é o mesmo que dizer que quanto maior for o \( i\), maior será \( mdc(b^i r_0,n)\).

Por outro lado, se \( i \geq \widetilde{i} + 1\), então vale 59. Neste caso, \( mdc(b^i r_0,n)\) é fixo, ou seja, todos os restos de \( s\) a partir do resto \( {\widetilde{i}+1}\) têm o mesmo \( mdc\) com \( n\). Então, de acordo com o Teorema 6 , estes devem ser os restos do período verdadeiro.

Logo, \( \widetilde{i}\) conta o último resto do falso período e é, de fato, o número de restos neste falso período.

Antes de finalizarmos esta prova, vejamos o que acontece quando \( e_{b,c}=0\), já que ele se encontra no denominador de 61. Para isto, olhemos rapidamente para a equação 60. Nela, vemos que se \( e_{b,c}=0\), o valor de \( \widetilde i\) não tem qualquer influência sobre 60. Mas, vemos que se \( e_{b,c}=0\), então, a base e o numerador não têm fatores em comum e \( mdc(b,n)=1\). Isto quer dizer que a variação de \( i\) não produzirá restos cujo \( mdc\) com \( n\) seja variável, ou seja, todos os restos pertencem ao período verdadeiro. Logo, se \( e_{b,c}=0\), então, o número de elementos no falso período é nulo também. Este é o primeiro caso de 52.

Finalmente, já que o número de restos do falso período é uma função da base, do primeiro resto escolhido e de \( n\), façamos \( {\widetilde{i}}= \widetilde{\alpha}(b,r_0,n)\). C.Q.D.

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.

Corolário 1 do Teorema 7 : Se \( mdc(b,n)=1\), então, \( s(b, r_0, n)\) não tem um falso período.

Prova: Se \( mdc(b,n)=1\), então, todos os expoentes dos fatores primos de \( mdc(b,n)\) são nulos. Isto quer dizer que não há fatores primos comuns entre \( n\) e \( b\). Sendo assim, \( e_{b,c}\) e \( e_{n,c}\) devem ser nulos também. Logo, as \( \tau\) equações em 60 do Teorema 7 têm a forma

\[\begin{equation} \widetilde{i}\cdot 0 + e_{r_0,c} \ge 0 \end{equation}\]

que é satisfeita por qualquer \( \widetilde{i}\) não negativo, sendo que o menor \( \widetilde{i}\) não negativo que satisfaz esta inequação algo incomum é \( \widetilde{i}=0\). Isto é, se \( mdc(b,n)=1\), então, \( s(b, r_0, n)\) não tem um falso período. C.Q.D.

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.

Corolário 2 do Teorema 7 : Seja

\[\begin{equation} s(b,r_0,n) = ( \{s_i\}_{i=0}^{\widetilde{i}} , s(b,r_{\widetilde{i}},n) ) \end{equation}\]

Então, a subsequência \( s(b,r_{\widetilde{i}},n)\) não tem um falso período.

Prova: A equação 62 do Teorema 7 equivale a 64 deste Corolário e \( r_{\widetilde{i}}\) faz o papel de \( r_0\) em \( s(b,r_{\widetilde{i}},n)\). Vimos em 59 do Teorema 7 que, quando \( \widetilde{i}_c\) cresce e se torna \( \widetilde{\alpha}\), então, a desigualdade \( \widetilde{i}_c\cdot e_{b, c} + e_{r_0, c}\geq e_{n, c}\) passa a valer e o mdc, abaixo, também passa a vigorar.

\[\begin{equation} mdc(b^i r_0,n)=\prod_{c\in P} p_c^{e_{n,c}} \end{equation}\]

Mas, vimos que este é o caso em que os restos têm mdc fixo com \( n\) e que, portanto, só podem ser os restos do período verdadeiro. Como, para \( s(b,r_{\widetilde{i}},n)\), este é o caso desde o resto inicial, \( r_{\widetilde{i}}\), decorre, daí, que ela não tem um falso período.

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.

Corolário 3 do Teorema 7 : Se \( j<i\le\widetilde{\alpha}\), então,

\[\begin{equation} mdc(n,r_j)< mdc(n,r_i) \end{equation}\]

Prova: Se o falso período tiver um só elemento, não há como realizar a comparação em 66.

Suponha, portanto, que \( \widetilde{\alpha}\ge 2\).

Então, da equação 54, sabemos que \( r_j\) e \( r_i\) partilham, respectivamente, do \( mdc\) que \( b^j r_0\) e \( b^i r_0\) têm com \( n\), ou seja, temos

\[\begin{equation} \begin{matrix} mdc(n,r_j)&=&\prod_{c=1}^{\tau} p_c^{min\{ je_{b,c}+e_{r_0,c} , e_{n,c} \} }\\ &=&\prod_{c=1}^{\tau} p_c^{je_{b,c}+e_{r_0,c}} \end{matrix} \end{equation}\]

e

\[\begin{equation} \begin{matrix} mdc(n,r_i)&=&\prod_{c=1}^{\tau} p_c^{min\{ ie_{b,c}+e_{r_0,c} , e_{n,c} \} }\\ &=&\prod_{c=1}^{\tau} p_c^{ie_{b,c}+e_{r_0,c}} \end{matrix} \end{equation}\]

Deste modo, como \( j<i\) para as mesmas potências primas, teremos que ter

\[\begin{equation} \frac{mdc(n,r_i)}{mdc(n,r_j)}=\prod_{alguns\ \ c's}^{ }p_c^{(i-j)e_{b,c}}>1 \end{equation}\]

ou seja, a inequação em 66 é verdadeira, C.Q.D.

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}}\).

Corolário 4 do Teorema 7 :

\[\begin{equation} \widetilde{\alpha} \le i \Longrightarrow mdc(n,r_{\widetilde{\alpha}}) = mdc(n,r_i) \end{equation}\]

Prova: Havendo um falso período, enquanto \( i\le\widetilde{\alpha}\), o

\[\begin{equation} mdc(n,r_i)=\prod_{c=1}^{\tau} p_c^{min\{ ie_{b,c}+e_{r_0,c} , e_{n,c} \} } \end{equation}\]

de acordo com a equação 67 ou 68 do corolário 3 deste teorema.

Isto quer dizer que

\[\begin{equation} mdc(n,r_{\widetilde{\alpha}})=\prod_{c=1}^{\tau} p_c^{min\{ \widetilde{\alpha}e_{b,c}+e_{r_0,c} , e_{n,c} \} } \end{equation}\]

O ponto \( i=\widetilde{\alpha}\) é o ponto em que 56 deixa de valer e em que passa a valer \( \widetilde{\alpha}e_{b,c}+e_{r_0,c} \ge e_{n,c}\), o que corresponde à equação 60 do Teorema 7 e que decorre de se haver chegado à posição em que vale 59.

Aprecie o fato de que se \( mdc(n, r_{\widetilde{\alpha}+1})>mdc(n, r_{\widetilde{\alpha}})\), então, o resto \( r_{\widetilde{\alpha}}\) não é o último do período falso! Contradição! Por outro lado, se \( mdc(n, r_{\widetilde{\alpha}+1})<mdc(n, r_{\widetilde{\alpha}})\), então, \( r_{\widetilde{\alpha}+1}\) não é o primeiro do período verdadeiro! Contradição! Logo, só nos resta concluir a igualdade.

Logo, se \(\widetilde{\alpha} \le i \), o expoente em 72 torna-se fixo, \( e_{n,c}\), e 72 se torna constante também, isto é,

\[\begin{equation} mdc(n,r_i)=\prod_{c=1}^{\tau}p_c^{e_{n,c}}=mdc(n, r_{\widetilde{\alpha}}) \end{equation}\]

C.Q.D.

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.

Corolário 5 do Teorema 7 : Seja

\[\begin{equation} s(b,r,n) = ( \{r_j\}_{j=0}^{\widetilde{\alpha}} , s_1(b,r_{\widetilde{\alpha}},n) ) \end{equation}\]

Então,

\[\begin{equation} mdc(n,r_{\widetilde{\alpha}})=1 \Longrightarrow \widetilde{\alpha}=0 \ \ e\ \ mdc(n,b)=1 \end{equation}\]

Prova: \( \widetilde{\alpha}=0\) significa que \( s\) não tem falso período (Neste caso, \( r_0\) figurará também como o "resto zero" do período verdadeiro, isto é, módulo n, valerá \(b^ir_{\widetilde{\alpha}}\equiv r_{i+\widetilde{\alpha}}\in s_1\)).

Dos corolários 3 e 4 deste Teorema, conclui-se que se \( j\le\widetilde{\alpha}<i\), então,

\[\begin{equation} mdc(n,r_j)\le mdc(n,r_{\widetilde{\alpha}}) = mdc(n,r_i) \end{equation}\]

Agora, em virtude da hipótese em 75, obtemos

\[\begin{equation} mdc(n,r_j)\le mdc(n,r_{\widetilde{\alpha}}) = 1 \end{equation}\]

De 77 se conclui que se \( j\le\widetilde{\alpha}\), então, deve-se ter

\[\begin{equation} mdc(n,r_j)=1 \end{equation}\]

ou seja, os restos do período falso têm \( mdc\) unitário com \( n\).

Então, da equação 57 do Teorema 7 temos

\[\begin{equation} mdc(n,r_j)=\prod_{c=1}^{\tau} p_c^{min\{ je_{b,c}+e_{r_0,c} , e_{n,c} \} } = 1 \end{equation}\]

De 79, temos que concluir que, para todo \( c\), ou

\[\begin{equation} je_{b,c}+e_{r_0,c}=0 \end{equation}\]

ou

\[\begin{equation} e_{n,c}=0 \end{equation}\]

ou ambos.

Se 80 valer, temos que ter

\[\begin{equation} e_{b,c}=e_{r_0,c}=0 \end{equation}\]

já que nenhum destes expoentes é negativo.

Se \( e_{b,c}=0\) para todo \( c\), então, os fatores comuns que figurariam no \( mdc(b,n)\) são todos unitários. Deste modo, caímos na hipótese do Corolário 1 , da qual vem a tese deste. C.Q.D.

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.

Corolário 6 do Teorema 7 : Se \( s(b,1,n)\) não tem um falso período, então, \( s(b,r,n)\) também não tem, seja qual for o \( r\).

Prova: Seja qual for o \( r\) escolhido, de acordo com a equação 52 do Teorema 7 , um \( r > 1\) contribuiria para diminuir o valor da função “maior inteiro” não negativo, pois o expoente respectivo diminui o numerador, em virtude do sinal negativo que o precede.

Assim, o falso período de \( s(b,r,n)\) não pode ser maior que o falso período de \( s(b,1,n)\). C.Q.D.

5.2. Exercícios

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

    1. 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!

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

  3. 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\)).

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

Numerador:
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.

Teorema 8: Para qualquer \( r_0, b\in \mathbb{N}-{0}\),

\( br_0\) tem todos os fatores primos de \( n\) - independentemente dos expoentes com que apareçam na fatoração prima de \( br_0\) -, se, e somente se, o período verdadeiro de \( s(b,r_0,n)\) é {0}.

Prova: Parte \( \Longrightarrow\)

Vários elementos do presente argumento já estão incluídos na prova do Teorema 7 .

A equação 54 do Teorema 6 é

\[\begin{equation} \frac{b^ir_0-r_i}{n} \ \ =\ \ \frac{(\prod_{c=1}^{\tau}p_c^{e_{b,c}})^i \prod_{c=1}^{\tau}p_c^{e_{r_0,c}} -r_i } { \prod_{c=1}^{\tau}p_c^{e_{n,c}} } \ \ =\ \ \frac{\prod_{c=1}^{\tau}p_c^{ie_{b,c}+e_{r_0,c}} -r_i } { \prod_{c=1}^{\tau}p_c^{e_{n,c}} } \in \mathbb{Z} \end{equation}\]

Por hipótese, não podem ser nulos os expoentes, \( e_{b,c}\), daqueles fatores primos de \( b\), \( p_c\), que estejam também presentes em \( n\).

O expoente \( i\ge 0\) cresce sem limites.

De acordo com o Teorema 7 , o número de restos no falso período de \( s(b,r,n)\) equivale ao menor \( i\) inteiro que seja maior que \( \frac{e_{n,c}-e_{r_0,c}}{e_{b,c}}\), o que, como vimos, equivale àquele primeiro \( i\) que torna todos os expoentes de qualquer fator primo em \( b\) maior ou igual que qualquer dos expoentes, \( e_{n,c}\), respectivos nos fatores primos também respectivos de \( n\). Quando isto acontece, \( e_{n,c}\) se torna mínimo para todo o \( c\) e aí, teremos que ter o seguinte

\[\begin{equation} mdc( \prod_{c=1}^{\tau}p_c^{ie_{b,c}+e_{r_0,c}} , \prod_{c=1}^{\tau}p_c^{e_{n,c}} ) = \prod_{c=1}^{\tau}p_c^{e_{n,c}} \end{equation}\]

Mas se o lado direito de 84, que é \( n\) de acordo com 83, divide o produtório que está no numerador do membro direito da igualdade em 83, então devemos ter também

\[\begin{equation} n | r_i \end{equation}\]

Então, é forçoso concluir-se que

\[\begin{equation} r_i\equiv 0(mod\ \ n) \end{equation}\]

o que só pode ser verdadeiro se

\[\begin{equation} r_i= 0 \end{equation}\]

A equação 87 vale para qualquer \( i\ge \widetilde{\alpha}\).

Logo, após o falso período, se houver um, seguir-se-á uma sequência infinita de zeros. Ou seja, o período verdadeiro calculado a cada \( r_i\) que se repete é \( {0}\).

Parte \(\Longleftarrow\).

Seja \( r_i=0\) para todo o \( i\ge \tilde{\alpha}\).

Então, podemos escrever 83 assim

\[\begin{equation} \frac{b^ir_0}{n} \ \ =\ \ \frac{\prod_{c=1}^{\tau}p_c^{ie_{b,c}+e_{r_0,c}} } { \prod_{c=1}^{\tau}p_c^{e_{n,c}} } \in \mathbb{Z} \end{equation}\]

Logo, \( n|b^i r_0\) para todo \( i\ge \tilde{\alpha}\), ou seja, \( b^i r_0\) tem todos os fatores primos de \( n\).

Por fim, é fácil ver que se para \( i\ge \tilde{\alpha}\), \( b^i r_0\) tem, de fato, todos os fatores primos de \( n\), e que estes fatores devem ter estado presentes em \( b^i r_0\), com algum expoente não nulo, quando \( 0\le i< \tilde{\alpha}\), C.Q.D.

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\).

Teorema 9: Sejam \( n,b>1\). Então,

\( \tilde{\alpha}(b,r,n)=0\) para todo \( n\in \{2,...,b-1\}\) e, para qualquer \( r\), se, e somente se, \( b\) é primo.

Prova: Parte \( \Longrightarrow\).

Se \( \tilde{\alpha}(b,r,n)=0\), então \( s(b,r,n)\) não tem um falso período, seja qual for o \( r\), e todos os restos de \( s\) são os do período verdadeiro.

Neste caso, de acordo com o Teorema 7 , os expoentes dos fatores primos comuns a \( n\) e \( b\) são todos nulos, ou seja, \( n\nmid b\) e, por hipótese, isto deve ser verdade para todo \( n\in \{2,...,b-1\}\). Então, apenas \( 1\) e \( b\) dividem \( b\). Logo, \( b\) é primo.

Parte \( \Longleftarrow\).

Se \( b\) é primo, então \( n\nmid b\) para \( n\in \{2,...,b-1\}\). Então, os expoentes dos fatores primos comuns de \( b\) e \( n\) são todos nulos. Do Teorema 7 , segue que \( \tilde{\alpha}(b,r,n)=0\) .

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!

Algoritmo 1 (Básico):

  1. Tome o número \( b\) que será testado.

    1. Fixe \( r=1\) e inicialize \( n\) com o primeiro inteiro do conjunto \( \{2, ..., b-1\}\), ou seja, \( n\leftarrow 2\).

  2. Calcule \( s(b,1,n)\) até o resto de índice \( \tilde{\alpha}+\alpha\).

    1. Se \( \tilde{\alpha}>0\) ou \( 0\in s\), então, o número \( b\) é composto!

      1. Se \( s\ni 0=r_1\), então, \( n\) é um divisor de \( b\).

        1. Faça \( n\leftarrow n+1\).

        2. Calcule \( s(b,1,n)\) até o resto de índice \( \tilde{\alpha}+\alpha\).

        3. Repita o item 2.a.i enquanto \( n\le b-1\).

  3. Faça \( n\leftarrow n+1\).

  4. Repita o item 2 enquanto \( n\le\left\lceil\sqrt{b}\right\rceil\).

    1. Se \( n=\left\lceil\sqrt{b}\right\rceil\), então, o número \( b\) é primo!

6.2. Explicação de Cada Passo do Algoritmo 1

  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.

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

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

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

        1. Aumente o valor de \( n\) em uma unidade e atribua este valor a \( n\).

        2. Já explicado.

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

  3. Significado já explicado.

  4. Aqui, como ainda não se descobriu divisores de \( b\), o limiar máximo será \( \sqrt{b}\)

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

O Algoritmo 1 em Python.
 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
Código para sondagem e armazenamento de números primos em Python.
 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 biblioteca Pickle da linguagem Python.

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 de known_primes, pois n1 - 1 é par!) e \( b\), inclusive, testando-os apenas contra os primos de known_primes para ver se algum destes inteiros são também primos, para, no fim, anexa-los a known_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ária new_primes.'''