Number Theory Notes (22 Oct 2011) – Part I

Background required: none.

For the first lecture, we shall look at congruence and modular arithmetic. Many of you may have already known (at least on an intuitive level) that square integers can only end in 0, 1, 4, 5, 6, 9; that the product of two odd numbers is odd; that it’s possible to compute the last digit of (say) 3^{2011} without since the last digit of 3^n goes in cycles. Here, we shall develop the theory behind it and use it to solve some problems later.

We need a language to state something like “n has remainder 5 when divided by 8″. This is where modular arithmetic comes in.

Definition : if a, b, m are integers, we write a \equiv b \pmod m if a-b is a multiple of m; i.e. if a-b = mk for some integer k. In English, we say “a is congruent to b modulo m”.

Thus, saying “n has remainder 5 when divided by 8″ is the same as n \equiv 5 \pmod 8. [ Exercise in definition: what does it mean to say a \equiv b \pmod 0? ] To do anything useful with this notation, we need to develop its properties. First, some very basic ones.

Let a, b, c, m be integers. Then the following hold:

  1. We always have a \equiv a \pmod m.
  2. If a \equiv b \pmod m, then b \equiv a \pmod m.
  3. If a \equiv b \pmod m and b \equiv c \pmod m, then a \equiv c \pmod m.

We shall leave out their proofs since they’re really easy. [ E.g. to prove the third property, we have a \equiv b \pmod m \implies a-b = mj and b \equiv c \pmod m \implies b-c = mk for some integers j and k; thus, a-c = m(j+k) \implies a \equiv c \pmod m. ]

The crux of these three properties is that on a purely symbolic level, the notation a \equiv b \pmod m behaves like equality. Thus, we can write without restraint something like

-5 \equiv 1 \equiv 7 \equiv -11 \equiv \ldots \pmod 6

thanks to the third property above.

The next three properties tell us that the notation is consistent with respect to arithmetic operations.

Let a, b, c, d, m be integers. Then the following hold:

  1. If a \equiv b \pmod m and c \equiv d \pmod m then a+c \equiv b+d \pmod m.
  2. If a \equiv b \pmod m and c \equiv d \pmod m then ac \equiv bd \pmod m.
  3. If a \equiv b \pmod m then a^n \equiv b^n \pmod m for all n = 1, 2, 3, …

The proofs are as follows. For (4) and (5), we can write a – b = mj and c – d = mk for some integers j and k. Thus:

(a+c) - (b+d) = (a-b) + (c-d) = m(j+k) \implies a+c \equiv b+d \pmod m.

ac - bd = a(c-d) + d(a-b) \implies a+c \equiv b+d \pmod m.

For (6), we use the known factorisation: for any positive integer n, we can factor the polynomial

X^n - Y^n = (X - Y) (X^{n-1} + X^{n-2}Y + \dots + XY^{n-2} + Y^{n-1}).

In particular, this gives a^n - b^n = (a-b)(a^{n-1} + \dots + b^{n-1}) which is a multiple of m. So our proof is done.

Finally, while the above properties already suffice, the following may come in useful.

  1. (Cancellation) If ac \equiv bc \pmod m, and (c, m) = 1 (here, (x, y) is the greatest common divisor, or highest common factor, of integers x and y), then a \equiv b \pmod m.

The proof requires Bezout’s identity : if (c, m) = 1, then we can write cx + my = 1 for some integers x and y. For example, if c = 5, m = 8, then we can write x = -3, y = 2. Thus, multiplying this identity by ab then gives:

(a – b)cx + (a – b)my = (a – b).

Since ac \equiv bc \pmod m, the (a – b)c is a multiple of m, so the first term is divisible by m. Clearly, the second term is also divisible by m. Thus, the RHS is divisible by m so a \equiv b \pmod m. QED.

 If c and m have a common factor > 1, then cancellation fails. E.g. pick m = 6, a = 4, b = 2 and c = 9. Then 4 \times 9 \equiv 2 \times 9 \pmod 6 but 4 \not\equiv 2 \pmod 6.

Coming up next: some applications of modular arithmetic.

This entry was posted in Notes and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s