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.” 1
G.H. Hardy, A Mathematician’s Apology, Cambridge University Press, p. 140. (1993 printing)
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.
Example1.8.
Form a sequence of positive integers using the following rules. Start with a positive integer \(n>1\text{.}\) If \(n\) is odd, then the next number is \(3n+1\text{.}\) If \(n\) is even, then the next number is \(n/2\text{.}\) Halt if you ever reach \(1\text{.}\) For example, if we start with \(28\text{,}\) the sequence is
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\text{.}\) However, is there some positive integer \(n\) (possibly quite large) so that if you start from \(n\text{,}\) you will never reach \(1\text{?}\)
Example1.9.
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\text{,}\) so:
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
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\text{?}\) OK, how about \(1348433\text{?}\) Now for a real challenge. Suppose you are told that the integer
\begin{align*}
c = \amp\,\, 5568490117077035708244283173335040521716369235589951150965\\
\amp\,\, 2043138898236817075547572153799
\end{align*}
is the product of two primes \(a\) and \(b\text{.}\) 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 2
sagemath.org
. We will sometimes embed interactive SageMath cells in the text, but you can also use SageMath for free online via CoCalc 3
cocalc.com
. For example, the SageMath cell below will produce the factorization shown above.
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:
\begin{align*}
a \amp = 2425967623052370772757633156976982469681\quad\text{and}\\
b \amp = 22953686867719691230002707821868552601124472329079.
\end{align*}
The SageMath code below calculates \(a\times b\text{,}\) and returns the result instantly.
On the other hand, if you ask SageMath to factor \(c\text{,}\) 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\text{!}\)
Questions arising in number theory can also have an enumerative flair, as the following example shows.
Example1.10.
In Figure 1.11, we show the integer partitions of \(8\text{.}\)
8 distinct parts
7+1 distinct parts, odd parts
6+2 distinct parts
6+1+1
5+3 distinct parts, odd parts
5+2+1 distinct parts
5+1+1+1 odd parts
4+4
4+3+1 distinct parts
4+2+2
4+2+1+1
4+1+1+1+1
3+3+2
3+3+1+1 odd parts
3+2+2+1
3+2+1+1+1
3+1+1+1+1+1 odd parts
2+2+2+2
2+2+2+1+1
2+2+1+1+1+1
2+1+1+1+1+1+1
1+1+1+1+1+1+1+1 odd parts
Figure1.11.The partitions of \(8\text{,}\) 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\text{?}\) 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?
