Cataloging-in-Publication Data (CIP) (Brazilian Book Chamber, SP, Brazil) Rodrigues, A. P. The formula for false decimal period length/ A. P. Rodrigues. --2nd ed. Passo de Torres, SC Ed. do Autor, 2025. ISBN 978-65-01-64010-5 1. Mathematics 2. Numbers Study and teaching 3. Numbers Theory I. Title. 25-293846.1 CDD-510 Systematic cataloging indexes: 1. Mathematics 510 Aline Graziele Benitez Librarian CRB-1/3129
To the Inventor of numbers.
To the servant of God Marcelo Henrique Câmara†, in memoriam.
Preface
When we divide a number by another, the result is expressed as a sequence of digits. This sequence of digits has a fractional part, which are the digits that come after the decimal point. This fractional part itself has two portions that are not especially highlighted from each other: one that is always there and another that only sometimes appears.
It’s possible to calculate the number of digits in the decimal expansion of any rational number. There is always a sequence of digits that repeats, and sometimes another sequence that occurs only once. We can calculate the number of digits in both!
For example, the decimal expansion of \( \frac{1}{7}=0,142857...\) has 6 digits that repeat indefinitely, in the same order, \(142857\), thus forming the infinite decimal of the number \( \frac{1}{7}\).
Another example is the fraction \( \frac{8}{65}=0,123076923...\). The initial sequence, \( 123\), of three digits, occurs only once. After this initial period, the decimal expansion of \( \frac{8}{65}\) is composed solely of the sequence \( 076923\).
It was by observing numbers like these that, many years ago, I sought to find the formula that would give the exact quantity of digits in the period of any number in the form \( \frac{1}{n}\).
The first insights into how to arrive at such a formula occurred gradually, over a long time.
In the meantime, I calculated, calculated, and calculated… Nowadays, I realize that, back then, I spent long periods in a state of extreme concentration that wasn’t entirely palatable for family, friends, and close acquaintances. But, although the social aspect of my life at that time fell short of my own expectations, this fact was, eventually, compensated by small discoveries and by the beauty and truth of certain equations, the fruit of work that never denied me occasional joys and satisfactions.
I truly spent, often, hours, days, and nights trying to conjure mathematical truths from thoughts and mental schemas that, at the time, were still poorly or not at all equipped with the proper instruments of the art. Not that I am much better today than I was then, but knowing that Reality exists in God, that mathematical abstractions move from that toward Him and are nothing more than abstractions if restricted to excessive logico-analytical formalisms, without the baptism in the deep waters of poetry to the open seas of dialectics — I repeat, knowing this strengthens the intellect, for it fills thought with those extracts of reality ranging from the most material and crude to the abyssal intangibilities of the Word and, beyond, into the Spirit.
I eventually arrived at the formulas I was searching for. First, I obtained the formula for the repeating period, or true period, and named it \( \alpha\) (Greek letter alpha). When I finally arrived at the formula for that first period, the one that doesn’t always occur, the false period, I called it \( \widetilde{\alpha}\) (read as alpha tilde). I, personally, call all this work Alpha Theory. The development of the theory is far from finished, much farther than its beginning up to the moment I am writing! But, each time I return to it, I return because a new intuition becomes perceptible and usually brings with it the end of a very long thread.
Subsequently, I advanced a little further and arrived at a formula for \( \alpha(b,m,n)\) and \( \widetilde{\alpha}(b,m,n)\), which give the number of digits in the decimal period and false period of any rational number, \( \frac{m}{n}\), and in any base \( b\). But the theme of this first book is the formula for the number of digits in the false period and the path that leads to it.
The reader will see that the theory develops from an initial formalization of the simple procedure that performs the division of \( m\) by \( n\) to, starting from the second volume, an algebraic treatment that relates \( \alpha\) with other quantities and entities that naturally arise during this digit counting process, and, suddenly, we will leap into an open field where integers themselves will be given in algebraic form in terms of the \( \alpha\)`s involved in their prime factorization. It’s a long journey where beauty and admiration intensify, more than compensating for the effort of the path.
The reader will also see that the numbers \( \alpha\) or \( \widetilde{\alpha}\) are not so important in themselves. That’s because they change from base to base. I will explain this in great detail in this present volume and the next. But the attempt to frame them in formulas is so fruitful, beautiful, and nourishing, for it leads to the mathematization of the very way a rational number is written, in any base, and strengthens the evidence that leads us to define real numbers as being, at the same time, the gregarious and unitary characteristic of the whole and its parts, which is, in fact, an aspect of everything that is an object of experience.
The mathematics used in the presentation of this theory deals with simple concepts that are easy to grasp, and anyone with a strong willingness can perfectly understand the subject. Soon, I will start publishing videos on my YouTube channel (@aprodriguesOficial) to provide further explanations on some points presented in this book and to introduce some of the key concepts that serve as the basis for alpha theory.
This volume presents the rudiments of alpha theory and concludes with the exposition of the formula for \( \widetilde{\alpha}\) and at least one of its interesting applications. Everything we see here will serve as the basis for the content of the next book, which, in this author’s opinion, is the main and most interesting part of alpha theory.
As a final word for this preface, I would like to say that the subject presented here stems from an interest that never depended on grades, salary, or financial compensation, although the latter two would have been much welcomed and missed. I merely tried to solve a problem as it presented itself to me and have succeeded in doing so. Certainly, I am not the first to speak about these things, nor will I be the last. I have no intention of being aligned with what is being said or done in academia, although I do not disregard any of it.
Thus, I am no longer in a hurry to seek the limits of current knowledge, which are constantly expanding. This author values depth more than breadth and, even so, delves into it at a snail’s pace, unconcerned with the inflated growth of science in our time where the increase in knowledge also reflects the increase in contradictions and frauds, truly scientific.
When it comes to the life of study, I try to follow the indications given by my most personal interests or those pointed out by the needs of what I am studying at a given moment. Certainly, this is not a recipe that works for everyone. Each individual with a vocation for a life of study must first understand themselves and know how to arrange resources and opportunities for this purpose in the best way for themselves. This author views the life of study in the present time as a preparation for Eternity, in which, in truth, we already are. Therefore, there is no haste whatsoever to reach any destination, only the serious commitment to lead myself outward toward ever-larger domains of Reality.
- Preface
- 1. The Division of One Number by Another
- 2. The Periodicity of Sequence s
- 3. A Formula for the Direct Calculation of Sequence s Remainders
- 4. Understanding Remainders Better
- 5. The Formula for the Number of Digits in the False Period
- 6. A Primality Test Based on the Number \(\widetilde{\alpha}\)
1. The Division of One Number by Another
Consider the division that is performed in the long division setup 1 divided by 7 below. This is how we learn to do it from our first school grades. This is the simple procedure by which we divide any number \( n\) by another number \( d\). It is our starting point.
1 | 7 |
---|---|
-0 |
0.142857 |
10 |
|
-7 |
|
30 |
|
-28 |
|
20 |
|
-14 |
|
60 |
|
-56 |
|
40 |
|
-35 |
|
50 |
|
-49 |
|
1 |
For now, let’s just observe that, in 1 divided by 7, we stopped calculating when we obtained the number \( 1\), which is the numerator with which we began the calculation.
Now, we must recognize that, in the long division setup above, we performed the following calculations:
If needed, the reader should manually perform the division of 1 by 7, or any pairs of numbers, to convince themselves (and recall) what we have just seen.
Now, let’s make a clever manipulation in each of the equations above, transposing the second term of the left side with the number on the right side.
Now, we’ll make a "leap of insight" and translate the 8 equations above into mathematical congruences. This simple language transposition will equip us with the operative and expressive algebraic possibilities we’ll use throughout this work. This translation makes the 8 equations above look like this:
Well, now, let’s show the general form of the long division setup used to divide a number \( n\) by another number \( d\). The long division setup 1 divided by 7 above is a particular case of what we will present below.
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}\) |
As before, this calculation can be readily converted to
then, we transpose terms to obtain
and, finally, convert (5) to the congruential format:
This is the point we wanted to reach! From here, Alpha Theory unfolds!
Next, we will see that the expression in 6 is readily generalized for any base \( b\), so that its appearance becomes:
I want to anticipate that the expressions in 6 and 7 allow for the counting of the number of periodic digits in the decimal expansion of \( \frac{n}{d}\), and this happens, basically, because \( r_0=r_{\alpha}\). There are other details involved in this last small equation. We will see all of them, in full, in what follows.
Finally, let’s observe that 7 contains, within itself, a finite sequence, \( s\), of positive integers. These positive integers are the remainders, \( r_i\), that appear in the division of \( n\) by \( d\). Thus, \( s=\{r_i\}_{i=0}^{\alpha}\). Alpha Theory is all about counting the elements of \( s\) and attempting to discern its beautiful and fruitful mathematical properties.
2. The Periodicity of Sequence s
The sequence \( s\) naturally inherits the decimal periodicity of \( \frac{n}{d}\). From this perspective, it wouldn’t be necessary to prove that \( s\) is periodic, as it couldn’t be otherwise, given that it’s simply an integral part of the long division setup n divided by d which, as we know, is where this periodicity manifests and from where, to begin with, we know it occurs.
But, undertaking the task of such a proof is, as we will see, so remarkably fruitful that we will completely forget the toil of plowing this land and planting upon it.
2.1. The False Period and the True Periods
All this work stems from the observation of countless division calculations. When, pages ago, I said that I calculated, calculated, and calculated, this is what I was referring to. In fact, any child or teenager who follows the first school lessons on the division process will probably hear that there are rational numbers with finite decimal expansions and others with infinite periodic decimal expansions. This can be observed in the long division setups. It is common to write numbers with fractional parts with ellipses after the last digit, either to indicate that the calculation would continue, if we wished, or to indicate that the period would repeat.
In fact, every decimal expansion is periodic! This innocuous detail will soon become crystal clear. When we say that some decimal expansions are finite, it’s because we observe a first sequence of digits followed by another sequence of infinite zeros. The first sequence of digits is the false period (which doesn’t always occur), while the infinite sequence of zeros is precisely the periodic sequence whose period is exactly the digit zero.
The general form of the decimal expansion of a number \( \frac{n}{d}\) is simply
where \( a_0\) is the integer part of \( \frac{n}{d}\), while \( a_1\dots a_{\tilde{\alpha}}\) is the possible false period and \( a_{\tilde{\alpha} + 1}\dots a_{\tilde{\alpha} + \alpha}\) is the period of digits that repeat.
The symbol \( \widetilde{\alpha}\) designates the number of elements in the false period. It is a very fortunate fact that we have been able to provide the exact formula that calculates this number as well. We will arrive at this great formula through an extremely detailed approach in the forthcoming chapters.
The decimal digits of \( \frac{n}{d}\) are accompanied by the respective remainders of this division, namely, the elements of the finite sequence
Note that if \( \tilde{\alpha}=0\), this means that neither \( \frac{n}{d}\) nor \( s\) have a false period and that both 8 and 9 will, respectively, have the following appearances:
and
which are the true periods that repeat indefinitely.
2.2. The Fundamental Periodicity Theorem
Next, I state and prove the Fundamental Periodicity Theorem for \( s\), generalized for any base \( b\). This is, in fact, the fundamental theorem of Alpha Theory. It forms the basis, directly or indirectly, for almost everything we will state from now on.
From this point, we will always refer to the periodicity phenomenon observed in the decimal digits of a division, say, \( \frac{m}{n}\), through the corresponding sequence of congruences, or, more specifically, through the sequence \( s=s(b,m,n)\), where the arguments \( b\), \( m\), and \( n\) indicate, respectively, the base in which the number \( \frac{m}{n}\) is being expressed, the numerator - second argument - and the denominator (third argument). Note that the numerator \( m\) may not coincide with \( r_0\) and, for this reason, it does not appear in \( s(b,m,n)=\{r_i\}_{i=0}^{\tilde{\alpha} + \alpha}\). Soon, we will show that if \( r_0\in s(b,m,n)\), then \( s(b,m,n)=s(b,r_0,n)\). We will see this in much greater detail in the following chapters.
Before stating the periodicity theorem, we need to consider one more detail. We saw, for example, in 5, that the sequence of digits involved in \( \frac{m}{n}\) can be calculated from the remainders - the elements of s - and the denominator. We summarize this fact in Definition 1 below. With it, we complete the fundamental pieces of information we need to continue the development of this work.
With this definition, we express in a clear and direct way what we had already seen, as we mentioned, in the set of equations in 5. The definition above uses the fact that the elements \( s_i\) of \( s\) are the remainders \( r_i\) of the division. Let us now proceed to the following Fundamental Theorem:
2.3. Solved Exercises
- Exercise 1
-
Write code in Python, or your preferred language, that models the Fundamental Periodicity Theorem, mainly, the calculation of remainders. Explain the code.
- Solution
-
Python Code that models the Fundamental Periodicity Theorem. The
n_over_d
method calculates the remainders and the periodic and non-periodic digits related to the fraction \( \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
In lines 16 to 20, I define or initialize a dictionary,
dic
, which already contains, from the outset, the values for the numerator (n), the denominator (d), the base (b), and the integer part,dic['integer part']
, of the fraction’s result \( \frac{n}{d}\).In lines 22 to 30, variables and vectors with suggestive names (in English) are also initialized with appropriate values for the operations to be performed inside the
while
loop that starts on line 31.Note how line 24 of the code Code that calculates sequences s and a, in Python above contains the operation equivalent to that found in the second and third lines of n divided by d, in the calculation column, and which corresponds to the calculation of \( r_0\) (which on the 3rd line already appears multiplied by base 10).
The
while
loop executes until the last remainder of the true period is found, which, according to Theorem 1 , occurs the first time a remainder that is already in the set of remaindersremainders
vector, is calculated again. See the scope of theif
statement on line 34. If thisif
statement is true, that is, if the currentremainder
is already in theremainders
vector, then thewhile
loop is interrupted (break
).When the
while
loop is interrupted, the dictionarydic
is updated with the collected information: number of elements in the true period (alpha: \( \alpha\)), number of elements in the false period, if any (alpha-tilde: \( \tilde{\alpha}\)), and the remainders and digits of the false period and the true period, respectively, under the keysnon-repeating remainders
,non-repeating decimals
,repeating remainders
andrepeating decimals
, which correspond to the elements of \( s\) and the elements of \( a\) (equation 12).
A Javascript translation of Code that calculates sequences s and a, in Python is running on this book and is responsible for automatically generating values in the Exercise Sections!
- 2: Use the fields below again to input numerators (n) and denominators (d) to automatically calculate and display the remainders and digits of the division \( \frac{n}{d}\). Use different combinations of \( n\), \( d\), and \( b\) to try and find combinations that generate false periods and those that don’t. By testing increasingly large numbers for the denominator, you will probably see that your browser will start to respond slowly and may eventually freeze or become unresponsive for very large numbers!
Denominator:
Base:
3. A Formula for the Direct Calculation of Sequence s Remainders
The sequence \( s(b,m,n)\) is an infinite sequence that is formed by the juxtaposition of infinitely many finite subsequences. This is a directly observable fact in the decimal expansion of \( \frac{m}{n}\) and repeatable since, each time we calculate \( \frac{m}{n}\), we can confirm that there are \( \alpha(b,m,n)\) decimal digits that repeat in the same order.
With what we have, so far, if we want to know the element \( i\) of \( s=\{r_i\}_{i=0}^{\infty}\), we have to calculate each of its elements separately, that is, we have to perform \( i\) calculations starting from \( r_0\) if we wish to know the element \( i\) of \( s\).
But, we can take a step further and verify a simple formula
with which we will be able to calculate any of the elements \( r_i=s_i\) of \( s\) in a single step. We will see that this small interesting formula is much more analytically useful than operationally. This is because both bases and exponents can become very large and render their numerical treatment unfeasible.
But, we will see that this small formula will yield some good advances in the direction we want to follow. For this, we will prove the following theorem.
3.1. Some Corollaries
The following corollary is merely the formalization of what we should already expect: multiplying, modulo n, any \( r_i\in s\) by \( b^j\), leads to the remainder that is in position \( j\) after the remainder \( r_i\), that is, it leads to the remainder \( r_{i + j}\).
The next corollary merely formalizes what we already know, by heart, which is: \( \alpha\) positions after a remainder \( r_i\), we find the same remainder \( r_i\) again.
4. Understanding Remainders Better
We need to start understanding better who the remainders, \( r_i\), are in the division of \( m\) by \( n\). For this, we can ask ourselves who the factors are that simultaneously divide each of the remainders of \( s(b,m,n)\).
The four following theorems are an important aid in this task.
To begin, the next Theorem 3 , below, tells us that there is an interesting relation between any \( r_i\) and the product \( b\cdot r_0\), which involves the initial remainder of \( s(b,m,n)\). This relation involves the concept of greatest common divisor, or \( gcd\), between the quantity \( b\cdot r_0\) and the denominator, \( n\), of the division. This common divisor, itself, may have some of its factors in \( b\) and others in \( r_0\). Note that we emphasize this possibility in the argument of the \( gcd\) that appears in the hypothesis of the theorem.
We will still further refine our understanding of the internal composition of remainders, but, for now, let us grasp the following very basic fact.
However, we can restrict our hypothesis only to the possibility that involves \( r_0\), instead of \( br_0\), as above. The establishment of this hypothesis is much more an act of will whose immediate mathematical consequence conforms perfectly to the very same form expressed in the thesis of the previous theorem. This will is a restrictive will: we wish to restrict the greatest common divisor only to \( r_0\) and \( n\) and no longer to \( br_0\) and \( n\).
Thus, the applicable proof, even in this slightly modified context, turns out to be, nonetheless, the very same as that of Theorem 3 above.
The next theorem is, in fact, a corollary of Theorem 4 . It states that all remainders \( r_i\) that follow a given remainder, \( r_{\bar i}\), in \( s(b,m,n)=\{r_0,\dots,r_{\bar i},\dots, r_i,\dots\}\) must be divisible by the common divisors of \( r_{\bar i}\) and \( n\).
Finally, we can already conclude that all remainders of the true period have the same greatest common divisor with \( n\). We will soon see that the same denominator \( n\) can have several sequences \( s(b,m,n)\) linked to it depending on the numerator’s value \( m\), and that this is intrinsically linked to the \( gcd\) that the remainders of \( s\) have with \( n\).
4.1. Exercises
-
Use the fields below to generate the remainders of \( s(b,m,n)\) for the base (\( b\)), numerator (\( m\)) and denominator (\( n\)) you choose. Test various triples of numbers to verify the results of the theorems in this Section. Use numerical expressions in any of the fields. For example, to test Theorem 3 , I would enter, say, the numerical expression 2*5 in the "Base" field, and 2*5*7*11 in the "Denominator" field and try to verify if all the generated remainders, \( i>0\), are indeed divisible by the common factor \( 2\) or by the other common factor \( 5\). The "Numerator" can be any non-negative value. After this, I would replace the factor \( 2\) with factor \( 3\) in both fields and try to verify if all the remainders, \( i>0\), will be divisible by \( 3\), and so on.
Denominator:
Base:
5. The Formula for the Number of Digits in the False Period
In the following theorem, we will use the notion of the "least integer". If \( y = \lceil x \rceil\), then it is said that "y is the least integer that is greater than or equal to x", the ceiling function.
5.1. Some Consequences of the Ability to Count the Number of Elements in the False Period
From this Theorem 7 , some very interesting results follow. The first of these is the following corollary.
Now, let us begin to recognize that infinite subsequences of a given \( s(b,m,n)\) are also sequences of remainders of some fraction \( \frac{r_i}{n}\) where \( r_i\in s(b,m,n)\) and \( r_i\) is the initial remainder of s from \( s(b,r_i,n)\). We will see this in great detail in the next book, which will deal with \( \alpha\), the number of elements of the true period.
For now, let us restrict these observations to the terms of Theorem 7 and affirm the following corollary which recognizes that any \( s\) is the juxtaposition of the finite sequence of a possible false period and the sequence of infinite true periods.
In Theorem 6 , we saw that the remainders of the true period all have the same \( gcd\) with \( n\). In the next corollary, we will see, more closely, how the \( gcd\)s of the remainders of the false period are variable. There is a growth, in magnitude, of the \( gcd\)s in the remainders of the false period from the first to the last.
Now, the next corollary shows that the fixed \( gcd\) that the remainders of the true period have with the denominator \( n\) is equal to that held, with the same \( n\), by the last remainder of the false period, \( r_{\widetilde{\alpha}}\).
The following consequence of Theorem 7 is much more a very indirect way of emphasizing that if some sequence of remainders has a false period, then it is not possible for the remainders of this false period to have a unitary \( gcd\) with \( n\), than a more useful result. A unitary \( gcd\), in this case, would mean that such a sequence does not have a false period.
Stated differently, if we suppose, contradictorily, that a sequence of remainders, in which the last remainder of the false period had a unitary \( gcd\) with \( n\), then such a sequence would not have any remainder in the false period.
Finally, the following corollary is a reflection that the existence and size of a false period depend primarily on the relation between the prime factors of the base, \( b\), and those of the denominator, \( n\).
It also gives one of the first indirect hints or raises the first suspicions that it is possible to perform operations of the type \( r\cdot s(b,1,n)=s(b,r,n)\). We will begin to see some of this in the next book.
5.2. Exercises
-
Use appropriate numerical expressions in the fields
Numerator
(which, in this case, is \( r_0\)),Denominator
, andBase
below, to test the assertion of Theorem 7 . To facilitate the tests, I have provided, right below, a list of the first 200 prime numbers.-
Example: Let’s say we deal with values with the following prime factorizations: \( r_0=2^2\cdot 3^3\cdot 5^5\) (in the numerator field, use the expression: 2^2 * 3^3 * 5^5), \( n=3^9\cdot 5^5\) (3^9 * 5^5) and , \( b=3^2\cdot 5^5\cdot 7^7\) (3^2 * 5^5 * 7^7). Thus, \( gcd(b,n)=3^2\cdot 5^5\). In this way, the prime power contained in \( gcd(b,n)\) that also appears in \( n\) and \( r_0\) with the largest difference between the respective exponents is \( 3^2\) which, in \( n\), \( r_0\) and \( b\), appear with exponents \( 9\), \( 3\) and \( 2\), respectively. So, according to Theorem 7 , the value of \( \tilde{\alpha}(b,r_0,n)\) (alpha-tilde) should be \(\left \lceil \frac{9-3}{2} \right \rceil=3\). I invite the reader to appreciate the fact that the number \( 3\) just obtained, was numerically calculated, but that the automatic results obtained below are the result of computational work performed under the dictates of Theorem 7 and that, for this reason, these computational results are a marvelous confirmation of the theory we have presented so far!
-
-
Take primes from the list below or products among them to form \( b\), \( r_0\) and \( n\) in such a way that \( gcd(b,n)=1\) and check if these examples obey Corollary 1 .
-
Now that you already know that if \( gcd(b,n)>1\), then \( s(b,r_0,n)\) will have a false period, test, with some examples, the validity of Corollary 2 . Use the list of prime numbers below to compose numbers \( b\), \( r_0\) and \( n\) and use the automatic generation fields to show that \( s_1(b,r_{\tilde{\alpha}},n)\subset s\) does not have a false period. This fact will be evident in the computed remainders of \( s\). But, you will still be able to visually identify \( r_{\tilde{\alpha}}\) to, then, calculate \( s_1\) directly (not as a subsequence of \( s\)).
-
Based on everything we have seen in this Section, suggest any 3 triples (\( b\), \( r\), \( n\)) that satisfy Corollary 6 .
List of the first 200 prime numbers: 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. A Primality Test Based on the Number \(\widetilde{\alpha}\)
The knowledge we derive from Theorem 7 now opens up the possibility for us to construct an algorithm with which we can determine if a number, \( b\), is prime or, otherwise, find all its divisors.
This is possible, because Theorem 7 showed us the relation between the number of elements in the false period and the existence of common factors between the denominator, \( n\), and the base, \( b\), that is, whenever these common factors exist, \( \tilde{\alpha}(b,r,n)\ge 1\).
Furthermore, a key component of the algorithm we will present will be given in the next theorem. This is a fact we know well, in base 10, according to which, sometimes, the fractional part of a fraction \( \frac{r}{n}\) may or may not have a false period, i.e., \( \tilde{\alpha}(b,r,n)\ge 0\), and all other digits - those of the true period - are zero. In school, one would normally say, as we have already observed, that such a decimal expansion is finite and non-periodic, or, if \( r_1=0\), that \( \frac{r}{n}\) is an integer.
In this case, as we will see, the remainders of the true period are also all zero. And, in fact, the sequence of remainders of the true period of \( s\), as well as the sequence of digits \( a\) of the same true period, instead of being finite, are infinite with a period equal to \( {0}\).
When a number \( n\) divides another number, the remainder, \( r_1\), of this division is zero. We have known this "forever"! The point here is that, now, this basic fact appears framed within a more general scheme and, along with another fact we will present in Theorem 8 below, can be used to probe not only divisibility but, first, also the occurrence of common factors between \( n\) and \( b\) - which will reveal the fact, should it occur, that the base \( b\) is not a prime number.
The following Theorem 8 addresses the effect observed in the remainders when the product \( br_0\) and the denominator have, with each other, all prime factors in common.
The next Theorem 9 contains the core of the algorithm we will outline. It states and proves a very accessible truth: if the fraction \( \frac{r}{n}\) does not exhibit a false period for any denominator \( n\in \{2,..., b-1\}\), then \( b\) is a prime number. And, in this way, we are able to determine if a number is prime or composite, simply by performing long division calculations! This is somewhat surprising, even though \( \frac{r}{n}\) must be expressed in a non-usual base \( b \neq 10\).
6.1. A Method to Determine if a Number is Prime or Discover its Divisors if it is Composite
6.1.1. The "Basic" Algorithm
The following algorithm aims to determine if a number \( b\) is prime or not. If \( b\) is composite, the algorithm will find all its divisors.
The algorithm’s input is the number \( b\) to be tested and a number \( r\in\{1,\dots ,n-1 \}\) - which, however, except for special reasons, will always be unity, which will simplify the calculations. When we set \( r_0=1\), the base \( b\) takes the place of the numerator! See the leftmost side of 83 to appreciate this simple fact. During the algorithm’s execution, the numbers \( n\in\{2,\dots, b-1\}\) can be used.
The number \( b\) is, in fact, the base in which the fraction \( \frac{r}{n}\) is expressed, and for this reason I used the pun in this Section’s title.
The reader will see, below, that we will use \( \left\lceil\sqrt{b}\right\rceil\) (the "Least Integer" function, that is, "the smallest integer that is greater than or equal to \( \sqrt{b}\)") instead of \( b\). This halves the number of general algorithm steps and has to do with a criterion known as the Sieve of Eratosthenes. I will not go into its details here. Its understanding is simple, its precise statement, and summary explanations can be found online, and its use is immediate. The sieve has to do with the observation that if a number is composite, then at least one of its divisors must be smaller than its square root. In this way, if you are testing divisors, in ascending order, and do not find any that is less than or equal to the root, then it is not necessary to test further, because there will be no other divisors, due to the number being prime!
6.2. Explanation of Each Step of Algorithm 1
-
In this step, we choose the value \( r=1\), as we had already mentioned. This follows from the freedom provided by Theorem 9 to choose any value for \( r\). We also initialize the value of \( n\) to \( 2\) and indicate this fact with the symbols \( n\leftarrow 2\). This is the notation used to designate the assignment of a value to a variable.
-
This step is the most laborious. In it, we need to calculate the remainders of \( s\). This can be done in three ways. We can use formula 28 which was proven in Theorem 2 or we can perform the long division calculation of \( r\) by \( n\) in base \( b\), as indicated in model n divided by d, just using \( b\) instead of \( 10\) and keeping an eye on the remainders of the division, or, alternatively, calculating each of the congruences as done in 6. We have already seen that \( s\) may or may not have a false period. In any case, the calculations must be performed taking care to observe the first time a remainder repeats a previously calculated remainder. At that point, it is time to stop calculating them. We saw this in Theorem 1 : the remainders of the true period are periodic. Proceeding thus, we will inevitably end up calculating the \( \tilde{\alpha}\) remainders of the possible false period, if there is one, and the \( \alpha\) remainders of the true period. Therefore, we will end up calculating \( \tilde{\alpha}+\alpha\) remainders, even if we eventually have \( \tilde{\alpha}=0\).
-
We know from theorems 7 and 8 that if \( \tilde{\alpha}>0\) or any remainder of \( s\) is zero, then the base \( b\) and the various denominator \( n\) have common prime factors. If the test performed in this item is true and one does not wish to know the divisors of \( b\), the algorithm can stop immediately, as we already know that \( b\) is not prime.
-
We also know that if the remainder \( r_1\in s\) is zero, then \( n\) must perfectly divide the numerator which, in this case, is, as we saw, \( b\). Note that if the test performed at this point is true, the algorithm will not leave item 2.a.i and its sub-items.
-
Increase the value of \( n\) by one unit and assign this value to \( n\).
-
Already explained.
-
Since there may be factors of \( b\) greater than \( \sqrt{b}\), and we specifically want to discover these factors, we must continue iterating the calculations until after this threshold.
-
-
-
-
Meaning already explained.
-
Here, as no divisors of \( b\) have yet been discovered, the maximum threshold will be \( \sqrt{b}\)
-
Upon reaching the threshold, \( b\) can be declared prime.
-
6.3. Some Observations
The Algorithm 1 presented above is not yet optimal. This is not its best version yet. To begin, it still performs, at least, \( \tilde{\alpha}+\alpha\) calculations for each \( n\in \{2,..., b-1\}\). This can be improved! In part, this limitation is due to the fact that we are encapsulating in our algorithm and, consequently, in the code below, the entire Code that calculates sequences s and a, in Python, already ready, which we wrote above for the calculation of \( s\).
This alone shows that between a mathematical theorization and a corresponding concrete realization there can be a great distance, even greater the more optimized the realization is and the more adjusted to concrete demands. But, for now, the current version serves as proof of the soundness of the theory behind it. Therefore, elements of this algorithm will be used in more optimized algorithms. But, before that, we need to develop the theory a bit more.
The algorithm above and the code below serve to discover primes. Thus, it makes sense to adjust it to be operable only in "discovery" mode. In this case, we could create a database to store the already discovered primes and test new prime candidates based on this database in order to decrease the number of test calculations and, thus, make it faster.
6.4. The Algorithm 1 in Code
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']: # This '1' is a false positive!
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. Exercises
- Exercise 1
-
Devise another solution, in code, that calculates all primes up to a given limit, \( b\), provided as an input argument. The calculated primes must be stored in permanent ordered fashion. The algorithm should use only this permanent database for the discovery of primes larger than all those already stored - this tends to reduce the execution time for new prime searches, as it does not test against all integers; it tests only against the already known primes. And, it should simply report the list of primes less than or equal to \( b\), if \( b\) is less than or equal to the largest prime already stored. The algorithm can start with a database already populated with a list, ordered by size, of all the first primes that the reader knows.
- Solution
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'No prime database was provided! The initial, minimum set of primes, {known_primes}, will be used.')
else:
try:
with open(DB_name, 'rb') as f:
known_primes = pickle.load(f)
print("Object loaded successfully.")
except FileNotFoundError:
print(f"Error: file {DB_name} not found.")
return
except pickle.UnpicklingError:
print(f"Error unpickling file {DB_name}. It may be corrupted or its content incompatible.")
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'The original list was as follows: {known_primes}.')
print(f'In this probing, the following prime numbers were found: {new_primes}.')
known_primes = known_primes + new_primes
with open(DB_name, 'wb') as f:
pickle.dump(known_primes, f)
return known_primes
- Explanation of the Code
-
In lines 13 to 28, care is taken to check if a file containing a previous list of primes already exists or to create one at the end of the code in lines 54 and 55, with the name
prime_database.pkl
, if it does not exist. This author used the initial list[2,3,5,7,11,13,17,19,23]
of 9 primes, but the reader can use a larger list provided it is complete. The storage is done by serializing the final list of primes. For this, we use thePickle
library of thePython
language.Lines 30 and 31 initialize the variable
known_primes
, if it does not yet contain a list of primes.Lines 32 and 33 test to see if the argument \( b\) is less than the last element of the list
known_primes
. If so, the code simply terminates by returning the list of all primes up to \( b\) already stored.Lines 35 to 48 are the most special. They iterate through all integers between
n1
(the second integer after the last prime inknown_primes
, becausen1 - 1
is even!) and \( b\), inclusive, testing them only against the primes inknown_primes
to see if any of these integers are also prime, to, in the end, append them toknown_primes
. The test performed here is the test of Theorem 9 . Line 41 tests to see if the number of remainders in the false period is greater than zero, in which case the negation of the right side of the Theorem’s proposition’s double implication also leads to the negation of its left side!, meaning the size of the false period is not zero and the number \( b\) is composite.Finally, lines 54 and 55 save the list of primes contained in
known_primes
which now, presumably, has been augmented with the new primes that were being collected in the temporary listnew_primes
.