Number theory

Number theory is the study of integers. At first, it's not clear what can be done with this field, because they're just integers, right? Well, actually, it turns out that it's pretty easy to write hard problems about integers.

All these don't seem to be easy! In fact, the statement that the last one has no solutions is Fermat's Last Theorem, which is famous for taking over three centuries before a proof is found!

In contrast, try replacing “integer” with “real number” above, and see how easy these problems become! In fact, because of this, number theory is a very fertile source of challenging programming contest problems. That's why we're studying it.

Many of the things that will be tackled here will also be tackled in Chapter 4 of MIT 6.042. This is a great resource; I highly recommend reading it alongside our "number theory" sections.

Since we're dealing with integers, we'll assume all variables refer to integers, unless stated otherwise.

Divisibility

We say that $a$ divides $b$ if there exists an integer $c$ such that $ac = b$. We write this as $a \mid b$. For example, $6$ divides $18$ because $6\cdot 3 = 18$. Also, $11$ divides $11$ because $11\cdot 1 = 11$. Note that this notion of divisibility includes zero and negative numbers. For example,

The last one might be counterintuitive because you usually can't divide by $0$. However, note that “divides” is not exactly the same as the “division” operation. You can think of “$a$ divides $b$” as “It is possible to divide $b$ things into groups of size $a$”.

If $a$ divides $b$, we can also say that $b$ is a multiple of $a$, and $a$ is a factor, or divisor, of $b$.

At first, this notion of “divides” sounds very basic. But this is actually the source of the richness of number theory! Just from these definitions, we can list lots of properties of integers. Many of these may be obvious to you, but some may not be. Please try to understand each statement.

Again, please try to understand what each statement means. We won't prove them because they would take up too much space. Instead, we leave it up to you. Proving them is a good practice of your proving skills (which you learned from the "Proofs" section). If you want to see an example proof, I recommend reading Chapter 4 of MIT 6.042.

Division Theorem

A very important theorem that we will use later on is the division theorem, which simply says that when you divide $a$ by $b$, then you get a unique quotient $q$ and a remainder $r$ that is less than $b$. More precisely:

Division theorem. For $a$ and $b$ with $b > 0$, there exist unique integers $q$ and $r$ such that $a = bq + r$ and $0 \le r < b$.

For example, if $a = 78$ and $b = 15$, then we have the quotient $q = 5$ and the remainder $r = 3$, because $78 = 15\cdot 5 + 3$ and $0 \le 3 < 15$. And sure enough, this $q$ and $r$ is the only pair of values satisfying it.

Note that negative $a$s are allowed! In this case, we must choose $q$ so that $r$ is positive. For example, if $a = -3$ and $b = 5$, then $q = -1$ and $r = 2$.

The division theorem is intuitive enough, so we won't prove it. You can certainly try.

Division and modulo

Since the $q$ and $r$ in the division theorem are so useful, we have some special notation for them. We write $\lfloor a/b \rfloor = q$ and $a \bmod b = r$.

$\lfloor a/b \rfloor$ is just the notation for floor division. In general, the notation $\lfloor x \rfloor$ denotes the floor of $x$, or the greatest integer $\le x$.

$a \bmod b$ stands for the modulo operation. We read this as “$a$ modulo $b$”. “Modulo” is just a fancy name for remainder, so don't worry about it.

In C++, division a / b of the various int types is actually floor division. There is also an operator for modulo: a % b. However, both these codes behave differently from above when a is negative. (So be careful!) The difference is that when a is negative, then division rounds off to zero, and modulo becomes negative (or zero). Thus, -8 / 5 = -1 and -8 % 5 = -3 even though $\lfloor -8/5 \rfloor = -2$ and $-8 \bmod 5 = 2$. If you want a code that emulates the modulo operation, see the following:

  1. int div(int a, int b) {
  2. if (b < 0) {
  3. // make the denominator positive using floor(-a/-b) = floor(a/b)
  4. a = -a;
  5. b = -b;
  6. }
  7. if (a > 0 || a % b == 0)
  8. return a / b;
  9. else
  10. return a / b - 1;
  11. }
  12. int mod(int a, int b) {
  13. return a - div(a, b) * b;
  14. }

Problems