Printable Version of Topic
Click here to view this topic in its original format
Dozensonline > Number Theory > Number Base Theory 101

Posted by: icarus Oct 10 2011, 06:34 PM
Let me begin by disclosing that I am not a professional mathematician nor do I play one on tv. I am a Missouri registered architect and member of the AIA, I am a graphic designer and member of AIGA. I am an avid competitive swimmer and member of the USMS. At most, I am an "amateur mathematician", whatever the heck that means. In recognition of this, let's start with several good sources on number bases and elementary number theory, beginning with the ones in my library:

A.) Ore, Oystein. Number Theory and Its History. Mineola, ny: Dover, 1988. [1st ed. 1948, New York, ny: McGraw-Hill Book Co.]
B.) Dudley, Underwood. Elementary Number Theory. Mineola, ny: Dover, 2008. [2nd ed. 1969, San Francisco, ca: W. H. Freeman & Co.]
C.) Weisstein, Eric W. Wolfram MathWorld. Retrieved October 2011, <>>
D.) LeVeque, William J., Elementary Theory of Numbers. Mineola, ny: Dover, 1990. [1st ed. 1962, Reading, ma: Addison-Wesley Publishing Co.]
E.) Hardy, G. H. and Wright, E. M., An Introduction to the Theory of Numbers. Sixth Edition. New York: Oxford University Press, 2008. isbn 978-0-19-921985-8, 978-0-19-921986-5 (pbk).
F.) Jones, Gareth A. and Jones, J. Mary, Elementary Number Theory. London: Springer (Undergraduate Mathematics Series), 2005.

Now if you're a quick study and ain't got time for the pain, check out Dr. Dudley's book at [B]. Of all the sources, I believe this is the ideal start. [F] is a little more conceptual and textbook-y. [E] starts off okay but gets very deep very soon, and you'll be over your head if you aren't in for a lot of math, but it is a very good book. For mathematicians, this is all child's play, I understand. My old favorite, [A], is a little dated; if you read [B] you're getting everything that's in [A].

Posted by: icarus Oct 10 2011, 07:13 PM

Briefly, someone interested in number bases, especially those that facilitate human intuitive computation, will find totatives of interest, since they tend to present resistance to human intuitive computation. There are, however, some aspects of totatives that are beneficial. A composite totative that "neighbors" the number base, e.g., the totative 9 base 10, gives decimal users simple divisibility tests for the totatives 3 and 9, as well as brief recurrent patterns in their decimally-expressed reciprocals. A great deal of totatives would seem to render a number base less "useful" for general intuitive human computation.

Wolfram Mathworld states the following on the "A totative is a positive integer less than or equal to a number n which is also relatively prime to n, where 1 is counted as being relatively prime to all numbers. The number of totatives of n is the value of the [Euler] totient function phi(n). The term was popularized by Sylvester (1879; Dickson 2005, p. 124), who spelled it 'totitive.'" The passage uses the word "popularize" loosely. About as "popular" evidently as "dozenal". "Two integers are relatively prime if they share no common positive factors (divisors) except 1. Using the notation gcd(m, n) to denote the greatest common divisor, two integers m and n are relatively prime if gcd(m, n)=1. Relatively prime integers are sometimes also called strangers or coprime and are denoted m (perpendicular sign) n.

Let's define a "digit". Let the integer r >= 2 be the radix under consideration. Then the digits of r will be all integers 0 < n <= r. The symbol "0" will represent the case where n is congruent to r. Let's ignore the special case where n = 0 (n is actually zero). Check out the definition of at Wolfram. I use Wolfram because it is a math resource on the web, and it is not Wikipedia (since some folks don't like Wikipedia).

The digits {1, 5, 7, b} are coprime to one dozen. The digits {1, 3, 7, 9} are coprime to ten. All odd digits are coprime to one dozen four. These are the set of dozenal, decimal, and hexadecimal totatives, respectively. Totatives tend to be a bit resistant to human intuitive computation.

Consider the multiplication table of base r. Let the integer 0 < t < r be coprime to r. This means the gcd(t, r) = 1. In Chicago, they'd say t and r have nothing in common. Let the integer 0 < k be a multiplier. In the multiplication table, the products of totatives have end digits that repeat a pattern every r products as the multiplier k increments. Observe the end digits of the decimal totative 7 {7, 4, 1, 8, 5, 2, 9, 6, 3, 0} and of the duodecimal totative 7 {7, 2, 9, 4, b, 6, 1, 8, 3, a, 5, 0}. This would seem to make the products of a totative t in base r a little more challenging to memorize.

Consider digital expansion of fractions where t is the denominator. The reciprocals of totatives 1/t feature recurrent digital expansions. The decimal fraction 1/7 is 0.142857142857..., the dozenal fraction 1/5 = 0.24972497... This seems to be more inconvenient than the digital expansion of, which terminate after one or more places.

Consider intuitive divisibility tests. Totatives generally will not possess an intuitive divisibility test; thus one has to resort to modular math to test for divisibility by seven in base ten, or by five in base twelve.

There are special totatives related to numbers directly neighboring the base which are less resistant. Let the integer omega = base - 1, and let the integer alpha = base + 1. Then there are numbers b coprime to r that divide omega evenly, and there are numbers a coprime to r that divide alpha evenly. (In odd bases, there is a digit 2 which divides both alpha and omega evenly). These neighbor-related totatives offer intuitive divisibility tests and have short recurrent periods in their digital fractions. The digit 3 base ten possesses a divisibility test wherein one adds up the digits of a number and takes a sum; if the sum is itself divisible by three, then the number tested is also divisible by three. In decimal, one third is 0.33333..., and one ninth is 0.111... In hexadecimal, one can test for divisibility by the totatives 3, 5 and digit-15 using the digit sum rule. Thus, the term "opaque totative" applies to any totative that is not the digit 1 nor neighbor-related. Yep I made that term up. I think it is a useful term when we are discussing number bases.

One can count the number of totatives in a given number base by using Euler's Use EulerPhi[r] in WolframAlpha or Mathematica to calculate the totient function. (I do not know the equivalent in Maple.)

I have a professor friend who thinks I am nuts over totatives because I always talk about them. The fact is I am talking about totatives like the War Department talks about the "Enemy". Lately I have a desire to find composite totatives in convenient places, like right "next to" the number base. Base 120 is interesting, because 119, the "omega", is 7 x 17, and 121 is "alpha", 11^2. This gives the user of base 120 keen divisibility tests for the first five primes plus 17, and brief recurrent digital expansions of the reciprocals of 7, 11, and 17. All of this in a number base that is highly factorable.

Totatives play a big role in cryptography.

Take a look at sources for further information:
[C],, [D] page 24, [E] page 58, [F] page 10 for "coprime", [D] pages 11-12 for "alpha" and "omega" in a proof, though the author does not refer to them as "alpha" nor "omega". Divisibility tests for "alpha, omega" [E] pages 142-3, 147. Totient function, see [A] pages 109-13, [B] page 70, [F] pages 86-87.

Posted by: icarus Oct 10 2011, 07:54 PM

Briefly, the divisor is an implement that would seem to enable intuitive human computation in a given number base.

Wolfram defines "" thus: "A divisor of a number n is a number d which divides n... also called a factor". This isn't too helpful.

Source [E], Hardy & Wright 2008, Chapter I, “The Series of Primes”, Section 1.1, "Divisibility of integers", pages 1–2, specifically: "An integer a is said to be divisible by another integer b, not 0, if there is a third integer c such that a = bc. If a and b are positive, c is necessarily positive. We express the fact that a is divisible by b, or b is a divisor of a, by b | a..."

Let's look at the notion of "divisibility" from source [D]: (LeVeque 1962, Chapter 1.1, "The Euclidean Algorithm and Its Consequences", Section 2-1, "Divisibility", page 22)
"Let a be different from 0 and let b be arbitrary. Then, if there is a c such that b = ac, we say that 'a divides b, or that 'a is a divisor of b', and write a | b ... The following statements are immediate consequences of this definition:
(1) For every a not equal to 0, a|0 and a|a.
(2) If a|b and b|c, then a|c.
(3) If a|b and a|c, then a|(bx + cy) for each x, y. (If a|b and a|c, then a is said to be a common divisor of b and c)
(4) If a|b and b not equal to 0 then |a| less than or equal to |b|."

"Trivial Divisors"
All positive integers r >= 2 possess the divisors {1, r}. These are said to be "trivial" (see source [A] page 29)

Let the integer r >= 2 be the number base, d be a divisor, and d' the divisor complement. Then we can rewrite source [E]'s equation a = bc as r = d * d'. (See source [A] page 86.)

Consider the multiplication table. Let the integer k > 0 be a multiplier. Divisors tend to have brief patterns of end digits in their products, such that the divisor d will have a cycle of end digits that are d' products long. The decimal multiplication table has two nontrivial divisors. The products of 2 end in {0,2, 4, 6, 8} and the products of five in {0, 5}. Duodecimal features four such divisors: 2 {0, 2, 4, 6, 8, a}, 3 {0, 3, 6, 9}, 4 {0, 4, 8}, and 6 {0, 6}. All bases have the trivial divisors, 1 {0, 1, ... } and r {0, 10, ...}. These seem to be easier to memorize than most any other line of products in the multiplication table.

Consider the digital expansion of fractions that have the divisor d as a denominator. All reciprocals of the divisor d in base r will have the expansion 0.d', a single place after the radix point. Very little else can be simpler when it comes to fractions and their digital equivalents. The divisor is a special kind of regular number g, an integer that produces a terminating digital fraction.

Consider the intuitive tests for divisibility by the divisor d. This is a special case of the regular divisibility tests. A regular divisibility test involves examination of the least significant digits of the integer x. In the case of a divisor d, a divisibility test for d is a regular divisibility test that involves comparison with a table of the positive products of d <= r. Thus, divisibility by five in decimal involves looking at the righmost digit of a number, say 95. If the rightmost digit (5) is any of {0, 5}, then the number 95 is divisible by 5. In base twelve, there are more divisors thus more such single-digit divisibility tests. We can test for any of {2, 3, 4, 6} by examining the last digit in base 12.

We can count the number of divisors using the Read more about it at source [A] page 86 and [B] pages 50-53. Use DivisorSigma[0, r] in Wolfram Alpha or Mathematica. I don't know the Maple function, but it shouldn't be too hard to find. Use Divisors[r] in Alpha or Mathematica to generate a list of divisors.

The divisor is thus a great aid in general human computation. The greater the number of divisors in general, it would seem the greater the number base. The problem is that numbers with more divisors are also large. Since even a handful of distinct prime divisors produces a very large number base, there is a practical limit to how many divisors one can leverage in a number base.

Divisors are a big topic in elementary number theory. Each of the sources has a chapter on such, or on "divisibility."

Posted by: icarus Oct 10 2011, 08:10 PM
The Unit.

Let the integer r >= 2 be a number base. The digit 1 is very special. It is neither prime nor composite. It is also both a divisor and a totative of a number base r. This is because 1 | r (one divides r) and the greatest common divisor (highest common factor) gcd(1, r) = 1.

Posted by: icarus Oct 10 2011, 09:15 PM
Neutral Digits.

I just wrote a paper on neutral digits. I'll post a link here once it's been reviewed. This is not a "canonical" elementary number theory topic, however the definitions and conjectures are proved in the paper.

Let the integer r >= 2 be a number base. Set d(r) as the number of divisors and t(r) as the number of totatives (I am using t in place of the Greek letter phi, since there is some problem displaying phi right now).

We can produce a "neutral digit counting function" using the following formula:
n(r) = d(r) + t(r) - 1

Note, this formula appears at the OEIS sequence, which is by this same definition, the set of neutral digits. (Edited 12 June 2014.)

We subtract 1 because it is counted both in d(r) and t(r), since it is a divisor of and coprime to r. Observe that many of the composite numbers r > 4 have a significant difference between the number of divisors and non-unitary totatives:
(in the case of r = 2, the difference is -1 since there is only one totative, digit-1.)
In the paper I prove that there are neutral digits for every composite r > 4, and that there are two possible kinds of neutral digit. I've called the two kinds of neutral digits the "semidivisor" and the "semitotative".


Let the integer p be a prime divisor of r. A semidivisor is a regular neutral digit that does not divide r evenly, and is the product of at least two prime divisors p.

To define the semidivisor we need the, and the unique factorization / prime power decomposition formula. See sources [A] page 86, [ B] pages 16-18, [E] page 3, [F] page 20. Let the integer k >= 1, and let the integer p be a distinct prime divisor of r. Let the integer e > 0 be the multiplicity (i.e., the exponent) of p in r.


Then a divisor d of r can be expressed as

It is too "rich" in at least one prime divisor p, when compared to the base r. Digit 4 base 6 has a prime divisor 2 with multiplicity 2, whilst there is only one 2 in 6. Digit 8 base 10 has a prime divisor 2 with multiplicity 3, whilst there is only one 2 in 10.

I wrote an algorithm in autumn 2013 that can produce the quantity of semidivisors for any given base. This was submitted to the OEIS 11 June 2014 and is now sequence The semidivisor also appears in an article I wrote for the ACM Inroads in early 2012. Note that a sequence that quantifies regular digits for bases n appears at (Edited 12 June 2014.)

The semidivisor, like other regular numbers, is generally an asset for those interested in human intuitive computation. In the multiplication table the semidivisor shares the shorter end-digit periods as divisors (there is a relationship between the semidivisor and a complement in these cycles). A semidivisor enjoys a terminating digital expression of its reciprocal. One eighth in decimal is 0.125. One dozen-fourth, a regular number in dozenal is 0;09. The number of places after the radix point will be greater than one, related to the "maximum multiplicity differential" of the semidivisor and the number base. Calculate the maximum multiplicity differential by finding which prime divisor has the highest multiplicity difference with the corresponding prime in the number base. The regular divisibility tests apply to semidivisors. This is a stumbling block for "remote" or "enriched" semidivisors, i.e., those having a high maximum multiplicity differential. Though one can use the regular divisibility test in decimal for eight, this involves knowing the 125 combinations of the three end digits divisible by eight {000, 008, 016, 024, 032, 040, 048, ... 984, 992}.

I've proved in the paper that all composite bases r that are not powers of primes have at least one semidivisor. This rules out base 4 for neutral digits, as it is the square of 2. Base 6 is the smallest base that has a semidivisor, digit-4.


The semitotative is easier to define. Let the integer q be a prime that is coprime to r. A semitotative is a non-regular neutral digit that is the product of at least one prime divisor p and at least one prime totative q.

In the paper I proved that a given number base, an integer r >= 2 will have at least one semitotative if a minimum totative q is smaller than the complement to the minimum prime divisor p. Thus, every composite number r > 6 will have semitotatives. This leaves r = 4 without neutral digits, and makes r = 6 unique in that it possesses semidivisors, but no semitotatives.

I wrote an algorithm in autumn 2013 that can produce the quantity of semitotatives for any given base. This was submitted to the OEIS 11 June 2014 and is now sequence The semitotative also appears in an article I wrote for the ACM Inroads in early 2012. (Edited 12 June 2014.)

The semitotative behaves like a semidivisor in the multiplication table, with short end-digit patterns. The digital expansion of multiples of reciprocals of semitotatives is recurrent. Semitotatives as digital reciprocals feature a brief, non-repeating set of digits, then a recurrent mantissa. One sixth in base ten is 0.1666..., one tenth in base twelve is 0;124972497... See source [E] page 142. Like the totative, the semitotative possesses no intuitive divisibility rule unless it is a product of two coprime factors that possess regular or neighbor-related intuitive divisibility tests. This is what I call a "compound intuitive divisibility test" in an upcoming paper.

Thus, with the neutral digits, we have a full "spectrum" of digits with direct relationships to the number base r. This enables the production of digit maps, which indicate the "usefulness" of a number base r, usefulness defined as being beneficial to the intuitive human computation in base r, ignoring the effects of magnitude of r. We can use "digit maps" of number bases r as a shorthand for their utility, since the types of digits speak to their behavior in a few basic applications (multiplication tables, divisibility tests, digital fractions, etc.)

Posted by: m1n1f1g Oct 10 2011, 09:54 PM
Can we define semidivisors as digits that do not divide r, but do divide rk for some k > 1? And, if so, can we say how "related" they are to the base by saying the power needed? For example, dozenal 8 would be a semidivisor-2 (8|102), whilst decimal 8 would be a semidivisor-3 (8|103). This is important because the division rules beyond semidivisor-2 are often relatively difficult. Yes, it's the last k digits, but what should they be? I know it's possible, but it's a lot more difficult for semidivisor-3s than for semidivisor-2s.

Posted by: icarus Oct 10 2011, 10:59 PM

Yes, that is a plausible definition.

Let's look at an analogous situation. Let the integer p be a prime represented in the prime decomposition of r. Let the integer q be a prime unrepresented in the prime decomposition of r. Then p | r and q is coprime to r.

Using the definition of "coprime" that I normally encounter, we read that an integer a is coprime to b iff gcd(a, b) = 1. To me, that seems more like a "telltale effect". We can say that a number a is a neutral digit of b iff 1 < gcd(a, b) < a. We can also say that a is a divisor of b iff gcd(a, b) = a. A more direct definition would seem to be a is coprime to b if the prime decomposition of b includes no non-unitary divisor of a. (If it isn't "more direct" than perhaps it is a "structural" definition, toward which I am usually biased.)

I'd recommend we use the term "regular number" in general if we are referring to integers that are products powers of the prime divisors p of base r, to the exclusion of any other prime q. Such numbers are restricted to the standard form


This is an existing and well-supported term. Then we have regular digits which are regular numbers less than or equal to r. There are two kinds of regular digits, those that divide r, and those which do not divide r, but as you point out, do divide r^k for some k > 1.

Consider this chart:

|------------------------------------------------| Regular Numbers
|----------|-----------------| r
Divisors | Semidivisors

I think you'll find that the distinction between regular digits is less important than portrayed here. My analysis uses r as a dividing line since that is the only line that makes sense. If you want to consider the "remoteness" of the regular digit g from r as a sort of index, I think that is possible. Use this formula


That is, the maximum difference between the multiplicity a of p in d and multiplicity e of p in r. I suppose we'd need to let any negative value of this differential be truncated to zero, since there is no effect of a "deficient divisor", say digit 6 base 72 (2 * 3 vs. 2^3 * 3 ^ 2) on its behavior across the basic applications. (I have to go to base 72 to get a divisor that fits "under the limbo bar" and isn't a square root; I can't use a prime power, because these have no semidivisor, but they do have regular numbers g > r.)

This would make digit 2 base 10 a regular number at level 0 (a divisor), digit 4 base 10 a regular number at level 1, digit 8 base 10 a regular number at level 2, number 16 base 10 a regular number at level 3, etc. Then we can know the number of places in the terminating decimal representation: the multiplicity differential + 1. This distinction is indeed useful for this purpose. Then the semidivisor is simply a regular number g < r that does not divide r, and a divisor is a regular number whose "maximum multiplicity differential" is zero (or less, if we permit the differential to possess negative value). Thus we have a continuum of regular digits, with special cases. For other purposes, we can acknowledge the special cases, but for the purpose I think you're considering, there isn't really a need to acknowledge them.

Posted by: m1n1f1g Oct 11 2011, 04:55 PM
While looking back to your definition of a I found this:
QUOTE (icarus @ Oct 10 2011, 10:15 PM)
Then a divisor d of r can be expressed as


Shouldn't that be [doHTML]

Anyway, your indices seem better, with divisors being 0 rather than 1. I wanted that, but I couldn't justify it mathematically.

I thought "regular numbers" were numbers which are 5-smooth. They're effectively what you would call regular numbers of base 26.

Posted by: icarus Oct 11 2011, 06:30 PM

I've fixed it. Normally I don't "edit" messages but with these posts I will do so, so that they are correct. Later this will go on the DSA website as part of a larger effort, probably in early 2012.

Regular Number.
The notion of "regular number" does arise in the study of (Duncan Melville). This Wikipedia definition of uses this definition. Let the integers {a, b, c} >= 0 be the exponents of the prime divisors 2, 3, and 5, respectively. Let n be an integer. A regular [sexagesimal] number is a number of the form
This is the Sloane number sequence, there called "5-smooth numbers: i.e. numbers whose prime divisors are all <= 5":
{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, ...}
The integer multiples of reciprocals of regular [sexagesimal] numbers enjoy a terminating [sexagesimal] digital expansion. A comment at Sloane's reads, "Sometimes called the Hamming sequence, since Hamming asked for an efficient algorithm to generate the list, in ascending order, of all numbers of the form 2^i 3^j 5^k for i,j,k >= 0. The problem was popularized by Edsger Dijkstra." This is the definition at Wikipedia and equivalent to the formula in this post, immediately above. This definition of "regular [sexagesimal] number" is thus equivalent to "5-smooth number". You would be correct in interpreting a "5-smooth number" also to be a regular number in base thirty, since the distinct prime divisors of thirty {2, 3, 5} are those of sixty {2, 3, 5}. The 5-smooth numbers are also regular in bases 120 and 360, and are a subset of the regular numbers of base 2520, since the distinct prime divisors of the first two are {2, 3, 5}, but those of 2520 are {2, 3, 5, 7}.

The definition of at MathWorld talks of a decimal regular number. Using the variables we set immediately above, a regular [decimal] number is a number of the form
This is the Sloane number sequence, simply referred to as "Numbers of the form 2^i*5^j", avoiding the term "regular [decimal] numbers":
{1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, ...}
Nonetheless, a description reads, "These are the natural numbers whose reciprocals are terminating decimals". This is equivalent to the definition at MathWorld and the formula in this post immediately above. Examples in source [E] starting at page 140 use the regular [decimal] number for exploration of representation of numbers by decimals. (See Hardy & Wright 2008, Chapter IX, "The Representation of Numbers by Decimals".) The same number sequence are regular vigesimal numbers, since the decimal distinct prime divisors {2, 5} are also the vigesimal distinct prime divisors {2, 5}.

Source [A] page 316 states the following:
Ore 1948, Chapter 13, "Theory of Decimal Expansions", page 316, specifically: "In general, let us say that a number is regular with respect to some base number b when it can be expanded in the corresponding number system with a finite number of negative powers of b. ... one concludes that the regular numbers are the fractions r = p/q, where q contains no other prime factors other than those that divide b."
This is a more general definition than those at MathWorld/Melville and Wikipedia/Hardy & Wright. Clearly the definitions at MathWorld/Melville and Wikipedia/Hardy & Wright are simply base-specific definitions of a larger concept of "regularity", i.e., those numbers g such that the prime divisors p of g are limited to those distinct prime divisors p found in the prime decomposition of the number base r, and exclude all prime numbers q not found in the prime decomposition of r.

The definition I use is the general definition of regular number given by Ore, by analogy of using "digital fraction" in place of "decimal fraction", "radix point" or "unit point" in place of "decimal [point]", etc. I use "5-smooth number" or "regular sexagesimal number" to refer to numbers of the form
and "regular decimal number" for those of the form

The regular dozenal numbers, {1, 2, 3, 4, 6, 8, 9, 10;, 14;, 16;, 20;, 23;, 28;, ...} I refer to as "three-smooth" or "regular dozenal" numbers. Using variables set at the start of this post, these are of the form

Posted by: dgoodmaniii Oct 12 2011, 06:41 PM
Keep them coming, please! I'm learning more number theory in this thread than I did in fourteen years of public schooling.

Posted by: m1n1f1g Oct 12 2011, 10:01 PM
QUOTE (dgoodmaniii @ Oct 12 2011, 07:41 PM)
Keep them coming, please!  I'm learning more number theory in this thread than I did in fourteen years of public schooling.

Good observation. The only one of these terms I've learnt in school is "divisor" (well, "factor" as it is often called). I haven't done A levels yet, but I can't see them cropping up there. The concepts are interesting to study, but probably only by people who are already interested in maths. I suppose they're a bit difficult to test on, beyond "How many totatives does the number 16 have?". There should be a coursework task to write about something interesting in an interesting way, I'm sick of writing rushed history essays for exams. angry.gif

On the regular numbers thing, according to your evidence you seem entitled to call them regular numbers for an arbitrary base. The evidence fits logically in an OR operation of proof, meaning that you've already proved your point. Actually, that really meant nothing, all I'm saying is that you can continue as before.

Posted by: icarus Oct 13 2011, 03:30 PM
Euler Totient Function.

m1n1f1g implies above that the question of "how many totatives does the number 16 have" is perhaps a trivial question, and in everyday life it might be so. Another way to state "how many totatives does the number 16 have" is "how many numbers 0 < n <= r are coprime to r = 16?" This question is a central topic in elementary number theory, studied by the greatest mathematicians, Euler, Fermat, principally. The following sources have chapters on the function:

[ A ] Chapter 5.5 "The Aliquot Parts", "Euler's Function"
[ B ] Section 9 "Euler's Theorem and Function"
[ D ] Chapter 3.4 "Reduced Residue Systems and Euler's [phi] Function"
[ E ] Chapter 5.5 "Congruences and Residues", "Euler's Function phi(m)"
[ F ] Chapter 5 "Euler's Function"

The Euler function, for the rest of the world outside of those who love number bases, is more closely associated with the notion of congruences / modular math and the greatest common divisor (highest common factor) than "totatives". The function counts how many numbers 0 < n <= r have gcd(n, r) = 1. (Remember that gcd(n, r) = 1 is usually cited as the definition for "coprime / relatively prime", it is the sure test that indicates n and r are coprime.)

This summarizes the RSA public-key cryptography algorithm. (Read more about RSA at If you visit it, you'll see that the Euler totient function is highly important to the algorithm. In fact, if you are planning to encrypt a message, you want a lot of "resistance", you want as many totatives as you can get. If you're encrypting a message, you need large prime numbers. The document provides references and does a good job of explaining the basics of the method. This method was developed (looking at Wikipedia) in the seventies. This is an example of how a seemingly unimportant basic mathematical property can become a seriously powerful application. Imagine what today's internet/computer society would be like without public-key encryption?

Because the Euler totient function was discovered around the time when modular math, congruences, and residues were, strangely this end of the "digit spectrum" is well-founded in mathematics. Thankfully we can "detect" how many totatives there are in a base, how many integers 0 < n <= r are coprime to r without having to count them like (but the row examples are a neat way of studying the function).

Let the integer r >= 2 be a number base. Let the prime p be a prime divisor of r (i.e., p | r). Let the integer e > 0 be the multiplicity (i.e., exponent) of p in r. Let the integer k >= 1. Consider the standard prime power decomposition of r:

with p1 < p1 < ... < pk

Sources [A, p. 110], [C,], [D, pp. 43-44] state that


This means every prime has (prime - 1) totatives. Using the nomenclature earlier established in this thread


Reading further in these sources, you'll see the function is multiplicative, dependent on the distinct prime divisors pk of r.
Sources [A, p. 113], [B, p. 70], [C,], [D, p. 45], [E, pp. 64-65], [F, p. 87] show that we can compute the Euler totient function by


Please do not neglect to check the sources. These sources have more information about any of the topics than can be posted on this forum. I think anyone interested in number bases should be familiar with the things that have been posted thus far (except perhaps the "neutral digits" as presented here; folks should know about regular digits, though. I think the neutral digits paper fills in a gap and allows us to succinctly analyze any number base r). Many of the sources ([A], [B], [D]) are available from Dover, meaning that they aren't that expensive. Source [C],, is a good internet reference, like an encyclopedia for maths. Hardy & Wright (source [E]) and Jones & Jones (source [F]) are more expensive and more serious. There are things I doubt I'll ever understand in both of them.

One never knows where this knowledge will take you. I tutor eighth grade (13-14 year old for the UK readers on this site) girls in pre-algebra. Many many times the comment pops up "why do we even have to know this," "if it can't equal six than why do they even write a six, why don't they write seven," etc. We live in a world where algorithms increasingly determine outcomes, where one can make billions on an algorithm. Number theory, mathematics, and logic are the keys to the algorithms.

Posted by: daedalus Oct 14 2011, 05:28 PM
[doHTML]user posted image
[doHTML]user posted image

Posted by: m1n1f1g Oct 14 2011, 10:25 PM
Were you supposed to be logged in as daedalus? I thought that was your quick-fix temporary profile.

Anyway, it's surprising to see how many bases are better than binary in this respect, but also how that side is far slower to reach 0 than the primes are to reach 1. It's common sense really, that when r = infinity, r/(r-1) = 1; but it's amazing to think that this base may have no totatives, if it is a multiple of everything. Not that that'd be useful. Every number would be a special case, and each new multiplication attempted would need to be worked out manually, by adding numbers repetitively and looking them up on some colossal number line. But that's stupid tongue.gif.

Posted by: icarus Oct 14 2011, 10:43 PM
Yes, I've noticed that. That was a mistake. When I used this device I had an autofill and it put in what I logged in last time. It almost happened twice!

When you say "better than binary" you mean "better than the number bases that are powers of two" and can include any number bases that are powers of any single prime. "Better" here meaning having a lower proportion of totatives, which represent resistance to human intuitive computation.

I think binary is the best base, if you are not limited by human cognitive ability. Specifically, if you can parse "11111011011" as fast as "2011" decimal. This is what I can't study: what is the lowest base that does not throw us for a loop when we try to parse strings of digits? To me, it seems like 7 or 8. I have a way to gauge it but it isn't as steeped in mathematics as the facts conspire against large bases.

Posted by: icarus Oct 14 2011, 10:45 PM
Visit this for a PDF with digit maps for all bases 2 <= r <= 120.

Posted by: icarus Oct 14 2011, 10:49 PM
user posted image
This is part of a larger work that applies the analysis to all number bases below 26; that will be available at the DSA website. There is another method of analysis that is planned, but I am far from finishing it.
Ciao for now, family dinner, a patriarch is having his birthday gala and I get to sit with all the kiddies!

Posted by: icarus Dec 5 2011, 04:17 PM

Posted by: icarus Apr 26 2012, 10:43 PM

Posted by: icarus Sep 14 2012, 09:57 PM

Posted by: icarus Oct 5 2012, 03:17 PM

Posted by: icarus Oct 5 2012, 03:22 PM

Posted by: icarus Oct 5 2012, 03:58 PM

Posted by: Double sharp Oct 23 2017, 03:33 PM
QUOTE (icarus @ Oct 5 2012 @ 03:58 PM)
If we have bases that incorporate larger primes p > 7, we might accept more profound “blunting” to buy resolution of smaller primes. This might indicate that our number base is out of tune!

This in fact suggests that because primes above 7 become a natural part of factorisation at a scale too fine for any auxiliary use, bases with prime factors larger than 7 essentially act like these primes don't really exist for the purpose of auxiliaries, and simply have to use unmodified superior highly composites whether or not they gel well with the base (and they don't). (Which is a bit different from decimal, which can use unmodified superior highly composites, but gels well with them.)

Powered by Invision Power Board (
© Invision Power Services (