1.4: Combinatorics and Number Theory
- Page ID
- 97841
Broadly, number theory concerns itself with the properties of the positive integers. G.H. Hardy was a brilliant British mathematician who lived through both World Wars and conducted a large deal of number-theoretic research. He was also a pacifist who was happy that, from his perspective, his research was not “useful”. He wrote in his 1940 essay A Mathematician's Apology “[n]o one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years.” Little did he know, the purest mathematical ideas of number theory would soon become indispensable for the cryptographic techniques that kept communications secure. Our subject here is not number theory, but we will see a few times where combinatorial techniques are of use in number theory.
Form a sequence of positive integers using the following rules. Start with a positive integer \(n > 1\). If \(n\) is odd, then the next number is \(3n+1\). If \(n\) is even, then the next number is \(n/2\). Halt if you ever reach 1. For example, if we start with 28, the sequence is
\(28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1\)
Now suppose you start with 19. Then the first few terms are
\(19,58,29,88,44,22\)
But now we note that the integer 22 appears in the first sequence, so the two sequences will agree from this point on. Sequences formed by this rule are called Collatz sequences.
Pick a number somewhere between 100 and 200 and write down the sequence you get. Regardless of your choice, you will eventually halt with a 1. However, is there some positive integer \(n\) (possibly quite large) so that if you start from \(n\), you will never reach 1?
Students in middle school are taught to add fractions by finding least common multiples. For example, the least common multiple of 15 and 12 is 60, so:
\(\dfrac{2}{15} + \dfrac{7}{12} = \dfrac{8}{60} + \dfrac{35}{60} = \dfrac{43}{60}\)
How hard is it to find the least common multiple of two integers?
It's really easy if you can factor them into primes. For example, consider the problem of finding the least common multiple of \(351785000\) and \(316752027900\) if you just happen to know that
\(351785000 = 2^3 \times 5^4 \times 7 \times 19 \times 23^2\) and
\(316752027900 = 2^2 \times 3 \times 5^2 \times 7^3 \times 11 \times 23^4\).
Then the least common multiple is
\(300914426505000 = 2^3 \times 3 \times 5^4 \times 7^3 \times 11 \times 19 \times 23^4\).
So to find the least common multiple of two numbers, we just have to factor them into primes. That doesn't sound too hard. For starters, can you factor 1961? OK, how about 1348433? Now for a real challenge. Suppose you are told that the integer
\(c = 55684901170770357082442831733350405217163692355899511509652043138898236817075547572153799\)
is the product of two primes \(a\) and \(b\). Can you find them?
What if factoring is hard? Can you find the least common multiple of two relatively large integers, say each with about 500 digits, by another method? How should middle school students be taught to add fractions?
As an aside, we note that most calculators can't add or multiply two 20 digits numbers, much less two numbers with more than 500 digits. But it is relatively straightforward to write a computer program that will do the job for us. Also, there are some powerful mathematical software tools available. Two very well known commercial examples are Maple® and Mathematica®. In this text, we will from time to time, make use of the open source computer algebra system SageMath. We will sometimes embed interactive SageMath cells in the text, but you can also use SageMath for free online via the SageMath Cloud. For example, the SageMath cell below will produce the factorization shown above.
//Code
If you're reading this text in a web browser, go ahead and change the integer in the SageMath cell above to some other, perhaps larger, integer and click the button again to get the prime factorization of your new integer.
Now here's how we made up the challenge problem. First, we found a site on the web that lists large primes and found these two values:
\(a=2425967623052370772757633156976982469681\) and
\(b=22953686867719691230002707821868552601124472329079\).
The SageMath code below calculates \(a×b\), and returns the result instantly.
//Code
On the other hand, if you ask SageMath to factor \(c\), as in the cell below, you'll likely be waiting a long time. If you get a response in more than a couple of minutes, please email us so that we can update the text with larger primes \(a\) and \(b!\)
//Code
Questions arising in number theory can also have an enumerative flair, as the following example shows.
In Figure 1.11, we show the integer partitions of 8.
Figure 1.11. The partitions of 8, noting those into distinct parts and those into odd parts.
There are 22 partitions altogether, and as noted, exactly 6 of them are partitions of 8 into odd parts. Also, exactly 6 of them are partitions of 8 into distinct parts.
What would be your reaction if we asked you to find the number of integer partitions of 25892? Do you think that the number of partitions of 25892 into odd parts equals the number of partitions of 25892 into distinct parts? Is there a way to answer this question without actually calculating the number of partitions of each type?