charlesreid1.com research & teaching

Euler's Theorem, the Totient Function, and Calculating Totients By Hand

Posted in Mathematics

permalink

Table of Contents

Introduction

Today we're going to delve into a little bit of number theory.

In number theory, we are usually dealing with modular arithmetic - expressions of the form:

$$ a \equiv b \mod m $$

or

$$ f(x) \equiv 0 \mod m $$

The mod indicates we're doing modular arithmetic, which is (formally) an algebraic system called a ring, which consists of the integers 0 through m.

An analogy to modular arithmetic is the way that the sine and cosine function "wrap around," and

$$ \sin \left( \dfrac{2 \pi}{3} \right) \equiv \sin \left( \dfrac{8 \pi}{3} \right) \equiv \sin \left( \dfrac{14 \pi}{3} \right) \equiv \dots $$

On a ring, this happens with the integers. So, for example,

$$ 2 \equiv 6 \equiv 10 \equiv \dots \mod 4 $$

Modular arithmetic uses the \(\equiv\) symbol, and not the \(=\) symbol, because we can't manipulate the left and right side using normal rules of algebra - solving equations on a ring requires some care.

The value of \(m\) need not be prime, generally, but if it is, we have some special properties that hold.

Complete and Reduced Residue Systems

Consider the ring of integers \(\mod 10\), which consists of the numbers

$$ \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \} $$

This is called the complete residue system mod 10. If we want to solve an equation like

$$ 2x \equiv 8 \mod 10 $$

we would normally just divide both sides by 2. But because of the "mod 10" we have to be a bit more careful. Dividing by 2 is just a way of saying, we want to multiply 2 by some number that will make 2 into 1.

However, because 2 is a factor of 10, there is no number in the complete residue system that will yield 1 mod 10 when we multiply it by 2:

$$ \begin{eqnarray*} 0 * 2 & \equiv & 0 \mod 10 \\ 1 * 2 & \equiv & 2 \mod 10 \\ 2 * 2 & \equiv & 4 \mod 10 \\ 3 * 2 & \equiv & 6 \mod 10 \\ 4 * 2 & \equiv & 8 \mod 10 \\ 5 * 2 \equiv 10 & \equiv & 0 \mod 10 \\ 6 * 2 \equiv 12 & \equiv & 2 \mod 10 \\ 7 * 2 \equiv 14 & \equiv & 4 \mod 10 \\ 8 * 2 \equiv 16 & \equiv & 6 \mod 10 \\ 9 * 2 \equiv 18 & \equiv & 8 \mod 10 \end{eqnarray*} $$

The same difficulty appears if we try and solve an equation like

$$ 5x \equiv 8 \mod 10 $$

for the same reason - 5 is a factor of 10, so it has no inverse mod 10.

Contrast that with solving an equation like

$$ 3x \equiv 8 \mod 10 $$

which, because 3 does not share any factors with 10, means we can find a number such that 3 times that number yields 1 mod 10:

$$ 3 \times 7 \equiv 21 \equiv 1 \mod 10 $$

so we can solve the equation by multiplying both sides by 7, the inverse of 3:

$$ \begin{eqnarray*} 3 x & \equiv & 8 \mod 10 \\ (7 \times 3) x & \equiv & (7 \times 8) \mod 10 \\ x &=& 56 \mod 10 \\ x &=& 6 \mod 10 \end{eqnarray*} $$

We can resolve this by creating a reduced residue system, which is a set of integers that have inverses mod 10. The reduced residue system consists of integers that

  • Have no common factors with the ring size \(m\)
  • Have no two elements that are congruent \mod m

So a reduced residue system \(\mod 10\) could be, for example,

$$ \{ 1, 3, 7, 9 \} $$

(other reduced residue systems are possible as well).

It is important to note that we do not include 0, in general, because 0 shares all factors with \(m\) - that is, every number in the complete residue system divides 0, so the greatest common factor of \(0\) and \(m\) is \(m\) and not 1!

(The only exception to this rule is \(m=1\), but this is a trivial case, since every integer is congruent mod 1.)

The reduced residue system has the property that any number in the complete residue system can be generated from the reduced residue system via addition.

Further, the size of the reduced residue system can be expressed using a function called the Euler totient function, denoted \(\phi(m)\). The totient function quantifies the number of integers less than \(m\) that are relatively prime with \(m\) (that is, two numbers such that the greatest common factor, denoted with the shorthand \((a,m)\), is 1).

Euler's Totient Function

Euler's totient function, \(\phi(m)\), turns out to be an extremely useful quantity in number theory. It also provides a quantitative measure of how divisible a number is. Take the two numbers 960 and 961 as examples:

$$ \phi(960) = 256 \qquad \phi(961) = 930 $$

from this, we can see that 960 has many more factors than 961. Here are their prime factorizations:

$$ \begin{eqnarray*} 960 = 2^6 \times 3 \times 5 \\ 961 = 31^2 \end{eqnarray*} $$

This means that the ring of integers mod 960 will have far more congruences that cannot be solved compared to the ring of integers mod 961.

Historical Note: The notation \(\phi(n)\) was first used by the mathematician Carl Friedrich Gauss in his incredible book Disquisitiones Arithmeticae, an important historical textbook that focused on gathering all of the results known to that point about number theory in a single work. (Gauss did omit the parenthesis, however, writing the totient function simply as \(\phi n\).)

Calculating the Totient Function by Hand

It may be obvious that the totient function is simple to compute using a computer; but the question naturally arises: can we compute totient functions for large integers by hand?

It turns out we can - we just need to be able to factor the number in question. (Note that this requirement is true generally; see the section on RSA Cryptography in a post to follow).

Let's first illustrate some rules for computing the totient function of composite numbers with some simple examples.

Totient Property: Prime Power

The first useful property is computing the totient function of a number that is a prime number raised to some power. Let's take the simple example of \(81 = 9^2 = 3^4\). We know that any number that shares factors with 81 is a multiple of 3 less than or equal to 81, which is the set of numbers

$$ \{ 1 \times 3, 2 \times 3, 3 \times 3, \dots, 3^{4-1} \times 3 \} $$

and there are \(3^{4-1}\) of these numbers. Thus, of all of the integers from \(1\) to \(3^4\), there are \(3^3\) of them that are not relatively prime with \(3^4\). So the totient function can be written:

$$ \begin{eqnarray*} \phi(81) &=& \phi(3^4) = 3^{4} - 3^{4-1} \\ \phi(81) &=& 81 - 27 \\ \phi(81) &=& = 54 \end{eqnarray*} $$

In general, if we are considering the totient function of a prime power \(p^k\), we can write the totient function as

$$ \phi(p^k) = p^{k} - p^{k-1} $$

Totient Property: Product of Primes

If we take a composite number like 20, we can split the totient function of 20 into the product of the totient function of the factors of 20:

$$ \begin{eqnarray*} 20 = 5 \times 4 \\ \phi(20) = \phi(5) \times \phi(4) \\ \phi(20) = 4 \times 2 = 8 \end{eqnarray*} $$

which is, indeed, the value of \(\phi(20)\). However, this does not hold generally, as we can see from computing the totient of 50:

$$ \begin{eqnarray*} 50 = 5 \times 10 \\ \phi(50) \neq \phi(5) \times \phi(10) \phi(50) \neq 4 \times 4 \phi(50) \neq 16 \end{eqnarray*} $$

In fact, the value of \(\phi(50)\) is 20, not 16! The problem is with our choice of factors, 5 and 10. These two numbers share a common factor of 5, meaning their totient functions do not account for all of the numbers that will be relatively prime with 50.

To fix this, we can further break down 50 into its prime factorization, and compute the totient function of those primes:

$$ \begin{eqnarray*} 50 &=& 2 \times 5^2 \\ \phi(50) &=& \phi(2) \times \phi(5^2) \\ \phi(50) &=& 1 \times ( 5^2 - 5 ) \\ \phi(50) &=& 1 \times 20 \\ \phi(50) &=& 20 \end{eqnarray*} $$

which gives us the correct result of 20.

Generalizing this rule, we can say that we can break down the totient function of a product of two numbers \(s \times t\) into the product of totient functions \(\phi(s)\) and \(\phi(t)\) only if the greatest common factor between \(s\) and \(t\) is 1.

Totient Example

Let's consider the following example: suppose we wish to compute

$$ \phi( 280 ) $$

We can start by recognizing some factors of 280 - we can pull out the factors 7 and 4, and 2 and 5. These can be further factored to yield the prime factorization of 280:

$$ 280 = 2^3 \times 5 \times 7 $$

Now we can use the property that the totient function of an integer \(m\) can be expressed as the product of the totient functions of the factors of \(m\). So we can write \(\phi(280)\) as any of the following equivalent expressions:

$$ \begin{eqnarray*} \phi(280) &=& \phi(10) \times \phi(7) \times \phi(2^2) \\ \phi(280) &=& \phi( 2^3 ) \times \phi(5) \times \phi(7) \end{eqnarray*} $$

Using the second expression, we know that

$$ \begin{eqnarray*} \phi(2^3) &=& (2^3 - 2^2) = 4 \\ \phi(5) &=& 4 \\ \phi(7) &=& 6 \end{eqnarray*} $$

for an overall totient function value of

$$ \begin{eqnarray*} \phi(280) &=& 4 \times 4 \times 6 \\ \phi(280) &=& 96 \end{eqnarray*} $$

which is indeed the correct result:

Totient function calculation with Wolfram Alpha

Tags:    mathematics    factors    number theory    euler   

Project Euler Problem 1

Posted in Mathematics

permalink

Table of Contents

Overview: The Problem

Project Euler is a website that provides mathematically-oriented programming problems. There are many (over 500) and they are a rich source of profound mathematical insights.

I have been considering a writeup that goes deep into a particular problem, so why not do it with problem 1?

Problem 1 of Project Euler asks:

Find the sum of all the multiples of 3 or 5 below 1000.

It is a pretty simple task - one of the first things covered in a decent programming course is the assortment of mathematical operators, including the modular operator and multiplication operator, useful here.

This problem is also a familiar problem in another guise - any computer science student who has solved a variant of the fizz buzz problem will recognize this task (in the fizz buzz problem, you print fizz every time a number is divisible by 3 and buzz every time it is divisible by 5, etc.)

It is a deceptively simple problem. In fact, it is so easy to solve with a computer that you almost lose a sense of what the manual process would look like. How might we perform this task by hand?

Finally, it is an example of a problem in which we are trying to find the number of outcomes of several classes of events, and some of the events are labeled with both classes. This means it will be important to learn and apply the Inclusion-Exclusion Principle. (Fortunately, this principle is fairly straightforward to apply.)

We will get to the algorithm to counting these factors by hand, and handling more complicated constraints as well, but first I'll address why this problem - this task - was deemed important enough to be the very first step that nearly everyone takes on their epic (or... not so epic) Project Euler journey.

Why This Problem?

The central task in this problem is to find multiples of a number \(k\), and count them. The task is simple enough (unlike later Project Euler questions, which can be downright frightening at times), but still requires knowledge of loops, operators, and basic algorithm design. It's no litmus test for whether you can solve Problem 100, but it gets you started.

The task at the heart of this problem - iterating through a list of multiples of a number - is at the heart of the Sieve of Eratosthenes algorithm, which in turn is at the heart of applied number theory. While it may not be the algorithm applied in practice, it is the first and most important algorithm number theorists learn.

It's also a first lesson in the subtleties of Project Euler problems - the eager but naive algorithm designer will count all multiples of 3, then all multiples of 5, forgetting that some repeat.

Project Euler Fail

Welcome to Project Euler.

Going Deeper: An Example

It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,001 - and to do so without explicitly enumerating them with a computer.

To do this, we can express the problem in set notation. We have three sets, A, B, C, containing multiples of 3, 4, and 5, respectively. In set theory language, we wish to find

$$ ( A \bigcup B ) \backslash C $$

We can start by counting the sets A and B, as well as accounting for \(A \bigcap B\) (numbers that are multiples of both a and b).

Next, we can count \(A \bigcap C\) and \(B \bigcap C\), which are the multiples of a and b that we counted that we should not have because they are multiples of c.

Finally, we cannot forget \(A \bigcap B \bigcap C\) - numbers that have a, b, and c as multiples. This case is a bit tricky. Any item that is in \(A \bigcap B \bigcap C\) has already been removed - twice. The first time was when it was removed because it was in \(A \bigcap C\), and the second time was when it was removed because it was in \(B \bigcap C\). Therefore, we must add each of these items back in, to account for the double-removal and ensure these items are only removed once.

So we will add the items in \(A \bigcap B \bigcap C\) back into the final set.

Visually representing A, B, and C with a Venn diagram,

Project Euler Problem 1 Venn Diagram

To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:

$$ \mbox{card}(A) = \mbox{floor}\left( \frac{2001}{3} \right) = 667 $$
$$ \mbox{card}(B) = \mbox{floor}\left( \frac{2001}{4} \right) = 500 $$

Next, we subtract the duplicates (numbers with both A and B as factors):

$$ \mbox{card}(A \bigcap B) = \mbox{floor}\left( \frac{2001}{3 \cdot 4} \right) = 166 $$

Now subtract integers that have both a and c as multiples, or b and c as multiples:

$$ \mbox{card}(A \bigcap C) = \mbox{floor}\left( \frac{2001}{3 \cdot 5} \right) = 133 $$
$$ \mbox{card}(B \bigcap C) = \mbox{floor}\left( \frac{2001}{4 \cdot 5} \right) = 100 $$

And last but not least, those numbers with a, b, and c as factors were just removed twice, so we add them back in once:

$$ \mbox{card}(A \bigcap B \bigcap C) = \mbox{floor}\left( \frac{2001}{3 \cdot 4 \cdot 5} \right) = 33 $$

This gives a total number of multiples M below N with a or b as a factor, but not c:

$$ M = \mbox{floor}\left( \frac{N}{a} \right) + \mbox{floor}\left( \frac{N}{b} \right) - \mbox{floor}\left( \frac{N}{ab} \right) - \mbox{floor}\left( \frac{N}{ac} \right) - \mbox{floor}\left( \frac{N}{bc} \right) + \mbox{floor}\left( \frac{N}{abc} \right) $$

in our specific case,

$$ \begin{align} M &=& 667 + 500 - 166 - 133 - 100 + 33 \\ M &=& 801 \end{align} $$

Tags:    computer science    mathematics    factors    sequences    euler    project euler   

Shortest Lattice Paths and Multiset Permutations

Posted in Mathematics

permalink

Table of Contents

The Lattice Paths Problem

I first came across the lattice paths problem in Project Euler problem 15. The question described a 2x2 square lattice, and illustrated the 6 ways of navigating from the top left corner to the bottom right corner by taking the minimum number of steps - 2 right steps and 2 down steps.

The question then asks for the number of minimum paths on a 20 x 20 grid. Needless to say, even without seeing the number, it should be obvious that enumerating all of these paths would get extremely expensive with grid dimensions growing beyond 10. That means this should be approached as an analytical combinatorics problem, not a computational combinatorics problem. As it turns out, there is a closed-form solution, and this is one of the few Project Euler questions that can be answered with the straightforward use of Wolfram Alpha (I solved it while boarding a bus).

But this is an interesting problem that goes beyond the Project Euler question - it has to do with a combinatorics problem that is maddeningly simple, yet surprisingly difficult to formulate - the problem of multisets.

Problem Formulation: Permutations

Thinking through the 2x2 grid, we already stated that the shortest path must consist of 2 right moves and 2 down moves - the number of paths is simply a question of the order in which these moves are made. Let us represent the path that moves right twice, then down twice, using the string

RRDD

Now we have a way of representing paths through the lattice - and we've turned our very specific lattice problem into a much more general combinatorics problem. How many unique permutations of the above path/string can we find?

Permutations of Unique Items (Factorial)

Let's suppose we have a string consisting of unique characters:

ABCDEFG

Now how many permutations of this string are there? The first letter can be any of the 7 characters, so we have 7 possibilities. The second letter can be any of the remaining 6 characters, so we have 7 * 6 possibilities. And so on down the line, until we get a total number of possible permutations of the string equal to

$$ 7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040 $$

There are 5040 unique permutations of the string.

Our situation is complicated by the fact that some of our permutations are repeated. For example, if we label the two down moves as D1 and D2, we can choose the first move as D1 and the second move as D2, or the first move as D2 and the second move as D1 - the two are equivalent. This will eliminate some of the permutations.

Permutations of Items with Duplicates (Multichoose)

Our case is slightly different: we have items with duplicates. This fits into a general combinatorics framework called stars-and-bars (link to Wikipedia article). In this framework, we are trying to determine the number of ways that we can partition a set of n objects into a set of \(k\) bins. The \(n\) objects are often denoted as star characters, and the k bins are formed by k-1 bar characters.

For example, if we are adding 5 components to a circuit board, and they can be any one of 9 possible components, we can represent this as the partitioning of 5 stars among 9 bins, or 8 bars. Here are some possibilities:

||||||||        <-- No choices made yet (9 bins, 8 partitions)
*|*||*||*|*||   <-- Mix of different components
||*|*||*|*||*   <-- Mix of different components
****|||*|||||   <-- Heavy on component 1
*|**|||**||||   <-- Two pairs

In the case of our lattice path problem, we have only two unique characters, D and R. We can think of the problem of generating permutations as inserting the down moves into a sequence of right moves. We have a certain number of locations where we can insert the down moves, and down moves can be inserted in order.

This is what's often called a stars-and-bars problem in combinatorics: trying to determine the number of permutations of items from multisets can be described as partitioning star characters with bar characters.

To formulate our problem in these terms, we can think of "distributing" our down moves as we move right through the lattice. On the 20x20 grid, we are going to make 20 right moves, and we can distribute our 20 down moves at any of 21 possible locations (columns of points on the lattice).

Thus, our n items, the 20 down moves, are being placed between the 20 right moves, which are the 20 bars that create 21 bins (21 locations to place the down moves).

Example

Considering the smaller 2x2 example, and replacing bars with R, we have, for a 2x2 lattice, six possibilities:

RR    <-- No choices made yet
**RR  <-- all on left
*R*R  <-- distributed... etc...
*RR*
R**R
R*R*
RR**

To enumerate the number of possibilities, we use the multichoose function, denoted "n multichoose k". This counts the number of ways to place n objects (D) into \(k\) bins (created by \(k-1\) other objects, R). The multichoose function is defined as (see https://en.wikipedia.org/wiki/Multiset#Counting_multisets wikipedia page for proper Latex notation - it looks like the binomial coefficient but with 2 parentheses):

$$ n \mbox{ multichoose } k = \binom{n+k-1}{n} $$

where, again, n is number of objects, being split into \(k\) partitions by \(k-1\) other objects.

Now, let's plug in the numbers for the 2 by 2 lattice. We get:

$$ n = 2, k = 3 $$

We are partitioning 2 down moves among 3 possible columns in the lattice. This gives:

$$ 2 \mbox{ multichoose } 3 = \binom{2+3-1}{2} = \binom{4}{2} = 10 $$

which is indeed the number of paths through the lattice.

Solving 2D Rectangular Lattice

To generalize, on a lattice of width \(W\) and height \(H\), we have \(W\) right moves that form \(W+1\) partitions, in which we are placing H items. The number of possible paths through the lattice is therefore equivalent to permutations of the string:

RRRR...(W times)...RRRDDDD...(H times)...DDDD

Now n and k are given by:

$$ n = H, k = W+1 $$

so the total number of possible paths through the W x H square lattice is:

$$ (H) \mbox{ multichoose } (W+1) = \binom{W+1+H-1}{H} = \binom{W+H}{H} $$

More Examples

The number of minimal paths through a 4 x 2 lattice (identical to the number of paths through a 2 x 4 lattice) is:

$$ P = \binom{4+2}{2} = \binom{4+2}{4} = 15 $$

The number of minimal paths through an 8x8 lattice is given by:

$$ P = \binom{8+8}{8} = 12,870 $$

and finally, the number of minimal paths through a 20 x 20 lattice is given by:

$$ P = \binom{20+20}{20} = 137,846,528,\mbox{XXX} $$

(This is the Project Euler problem 15 answer so last few digits are omitted.)

Solving 2D Square Lattice (Special Case)

If we use the above formulas for the special case where the dimensions of the grid are equal, such as the 20 x 20 case, we get the simpler and more symmetric formula:

$$ P = \binom{2D}{D} $$

where \(D\) is the dimension of the square grid.

Solving 3D Cuboid Lattice

(Note: cuboids are the 3D analogue of 2D rectangles.)

If we take this idea a step further, and use a slightly different combinatoric formula, we can generalize the problem to paths through higher dimensional lattices. This is an approach I came up with through trial and error, and some experimentation with Mathematica.

Suppose we have a 3D lattice, composed of 8 cubes, 2 on each side. Now we wish to know: how many shortest Manhattan distance paths are there through the lattice, from one corner to the other?

This can be re-cast, as we did above, as the problem of counting unique permutations of a string of the form:

UURRBB

where U denotes an up move, R denotes a right move, and B denotes a back move.

While we could use the multiset approach from above to describe this problem, it turns out that this approach is not powerful enough to describe the problem of arbitrary 3D lattices.

Let's pose the problem slightly more generally: we have C bags of moves or characters, each of a different size. We must use each character i precisely as many times as we have instances in its bag C_i. How many unique permutations are there?

Consider the following example string of length \(N = 14\), consisting of:

$$ \begin{array} N_x &=& 4 \mbox{ UP moves} \\ N_x &=& 4 \mbox{ RIGHT moves} \\ N_x &=& 6 \mbox{ BACK moves} \end{array} $$

These form a path through a 3D lattice of size \(4 \times 4 \times 6\):

UUUURRRRBBBBBB

The number of unique permutations can be computed by breaking this into sub-problems. Start by asking how many permutations there are of the string:

UUUUXXXXXXXXXX

(Treating the Rs and Bs as identical). Then we get:

$$ \binom{N}{N_x} = \binom{N_x + N_y + N_z}{N_x} = \binom{14}{10} = 1001 $$

Next, we deal with the other sub-problem, the Xs, by asking how many ways we can permute the following string:

RRRRBBBBBB

which is solved via another binomial coefficient. This number of permutations is given by:

$$ \binom{N_y + N_z}{N_y} = \binom{N_y + N_z}{N_z} = \binom{10}{4} = \binom{10}{6} = 210 $$

Now combining these, we get the overall number of permutations:

$$ P = \binom{14}{4} \cdot \binom{10}{4} = 210,210 $$

Solving 3D Cubic Lattice (Special Case)

If we have the special case of a perfect cubic lattice, the formula above reduces to the nice and symmetric:

$$ \dfrac{(3n)!}{(n!)^3} $$

Solving N-Dimensional Square Lattice (N-Dimensional Multisets)

Let's look at the example of a traversal of a 4D lattice, which we can think of as the evolution of a 3D traversal in time (a step in the fourth dimension would represent a "pause" in the 3D traversal).

Consider the traversal of a cube with dimensions \(3 \times 4 \times 5 \times 3\). Then

$$ N = 3 + 4 + 5 + 3 $$
$$ N_x = 3 $$
$$ N_y = 4 $$
$$ N_z = 5 $$
$$ N_t = 3 $$

A path on this 4D lattice has the form:

UUURRRRBBBBBWWW

(where \(W\) denotes wait, or a step in the time dimension).

The number of permutations is given by:

$$ P = \binom{N_x + N_y + N_z + N_t}{N_x} \cdot \binom{N_y + N_z + N_t}{N_y} \cdot \binom{N_z + N_t}{N_z} $$

For our specific example,

$$ P = \binom{3+4+5+3}{3} \cdot \binom{4+5+3}{4} \cdot \binom{5+3}{5} = 455 \cdot 495 \cdot 56 = 12,612,600 $$

Confirmed by Mathematica:

Permutations with Mathematica