A Little Number Theory

Number theory focuses on the structure of the integers, especially insofar as divisibility is concerned. Both the mathematical and Pythonic language will be used here. Typography is the tell.

Definition. If \(d\) is a nonzero integer and \(a\) is any integer, we write \(d \vert a\) if for some integer \(q\), \(a = dq\). This is a formal way of saying that \(d\) divides \(a\) evenly. In this case we will say that \(d\) is a divisor or factor of \(a\). We will say that \(d\) is a proper divisor of \(a\) if \(d \not= \pm a\).

Notice that all integers are divisible by 1 and -1. Also notice that all nonzero integers divide 0 evenly.

5| 26    Moore says false
         last digit is not 0 or 6  (remainder is 1)

7 | 35    35 = 7*5  TRUE

a| b if b%a == 0

If d and a are integers, we test for divisiblity using the predicate a%d == 0.

Here are some simple facts about divisibility. supppse \(d\vert a\) and \(d \vert b\). Then we can write \(a = dq\) and \(b = sq\) for some integers \(s\) and \(t\). Notice that $$ a + b = dq + sq = q(d + s).$$ Since \(d + s\) is an integer, \(d\vert a + b\). Also, if \(c\) is an integer we have \(ac = dqc = d(qc)\). Since \(qc\) is an integer, \(d| ac\).

    5 | 100 and 5 | 25  5 | (100 + 25)
    5 | 100 so 5 | 3*100

An easy consequence of this is that if \(d \vert a\) and \(d \vert b\), then \(d \vert ax + by\) for any integers \(x\) and \(y\).

Theorem. [Division Algorithm] If \(b\) and \(a\) are integers with \(a\gt 0\), then there are unique integers \(q\) and \(r\) so that \(b = aq + r\) and \(0 \le r \lt a\).

We shall not prove this theorem, although I should mention that the mechanism of doing so is the fact that any nonvoid subset of the positive integers has a least element.

This is the reason that the mod operator % works. In fact, what this theorem delivers is that q = b//a and r = b%a. That's what you really need to now. Hence we have this identity.

b = a*b//a + b%a

b = 127
a = 15
b//a = 8
b % a = 7

127 == 15*8 + 7  True!!!

Commmon Divisors Suppose that \(a\) and \(b\) are integers. An integer \(d\) is a common divisor of \(a) and \(b\) if \(d\vert a\) and \(d \vert b\). Observe that 1 is a common divisor of any pair of integers.

Since every pair of integers has a common divisor, and no divisor of an integer can be larger than that integer, every pair of integers has a greatest common divisor (gcd).

Here is the wormwood method of computing a gcd

gcd(144, 52)

          52                144
         /  \               /  \
        2   26             4   36--4--2
           /  \           / \  |   |
          2   13         2  2  9   2
                              / \
                             3  3

     52 = 2*2*13     144 = 2*2*2*2*3*3

     gcd(144,52) = 4