Last edited 10/31/2008 8:55:00 AM

 

NUMBER THEORY

Number theory is the study of the properties of the integers, particularly concerning prime numbers. It is often one of the first courses after calculus that math majors take. Some parts of number theory have important uses in computing science.

It might be better to call it “integer theory”, but the name “number theory” has been around for more than a century so I think we are stuck with it. (See cognitive dissonance.)

Division of Integers

Definition   An integer k divides a nonzero integer m (written  ) if there is an integer q with the property that .

Examples

¨   (“3 divides 6”)  because  6 and 3 are integers, 6 is not zero, and  (so  ).  

¨  3 does not divide 7 because there is no integer q with the property that .  (It is true that  but  is not an integer.)

¨  5 does not divide 0 because the definition requires m to be nonzero.  (A few authors do not require that m be nonzero.)  Notice that  but 5 does not divide 0 anyway.

Usage

You can word “  ” in any of these ways:

¨  k divides m.

¨  k is a divisor of m.

¨  k is a factor of m.

¨  m is divisible by k.

Confusions to watch out for

¨  Don't confuse the vertical line “|”, a verb meaning “divides”, with the slanting line “/” used in fractions. The expression “  “ is a (true) sentence, but the expression “  “ is the name of a number (the number  ), and does not form a complete sentence in itself.  An additional source of confusion is the fact that the numbers are reversed between the two notations:  because  is an integer.

¨  In the notation “  ” and in the phrase “  ” in the definition, the k and the m occur in opposite order.  Thus  because .  When you do pattern matching this sort of switch can really trip you up.

¨  The definition of “divides“ requires that the numbers involved be integers. So it doesn't make sense in general to talk about one real number dividing another. It is tempting, for example, to say that 2 divides 2π, but according to the definition given here, that statement is meaningless.

¨  You must take the definition literally.  Using the letter q in the definition may suggest to you that in the statement , q is the quotient when m is divided by k.  Indeed it is.  But it would be a bad thing to think of q as a quotient.  The definition does not say “the quotient when m is divided by k must be an integer”.  After all, in the terminology of grade school, 2 is the quotient when 7 is divided by 3 (see box), but that does not mean that 3 divides 7.   Many authors use “integer quotient” as a name for q  to avoid this confusion.  (See cognitive dissonance).  

 

Facts about division 

To Do

Images and metaphors for division

Congruence mod n

Definition

Let k be a positive integer and m and n be any integers.  Then m is congruent to n mod k if k divides .

Notation

¨  In number theory, the standard notations  or  is used to mean that m is congruent to n mod k .

¨  Computer scientists may write  to mean m is congruent to n mod k .  In that notation, “  ” means the remainder when m is divided by k.   This is the way MOD is used in modern computer languages.  See here for the connection between remainders and congruence.

Examples

¨   because 7 divides 6112, which is 49.  This could also be written as  or , the latter meaning that .

¨   because 7 divides 1261, which is 49.

Properties of congruence

Theorem 

For a fixed positive integer k, congruence (mod k) is an equivalence relation on .

Proof

¨  Reflexive:  Must show that for all integers m, .  This is correct because k divides m  m, which is zero (every integer divides 0).

¨  Symmetric:  Must show that for all integers m and n, if  then .  Rewriting, we must show that if k divides m  n, then k divides n  m.  Rewriting again using the definition of divides, we must show that if there is an integer q for which  then there is an integer  for which .  To accomplish this, let .

¨  Transitive:  Must show that for all integers m, n and p, if  and  then .  Rewriting again, we must show that if k divides m  n and k divides n  p, then k divides m  p.  Rewrite yet again:  We must show that if there are integers q and  for which  and , then there is an integer  for which .  This calculation pulls a rabbit out of a hat to do this:

                                 

so we can let  

Definition

Let k be a positive integer and m any integer.  The remainder when m is divided by k is just the remainder when you do long division.  The most usable mathematical definition is:

.  The remainder when m is divided by k is the unique integer r satisfying

a)             

b)             for some integer q

To make this a valid definition you must show that there is just one integer satisfying a) and b). 

Examples

¨  The remainder when 65 is divided by 7 is 2.  This is because a)   and b) . The picture on the right shows the calculation using long division.

Theorem

Two positive integers m and n are congruent mod k if and only if m and n leave the same remainder when divided by k. 

Proof

Theorem

If  and  then  and  

Proof

Remarks

¨  This theorem means that if you have an expression involving integers, addition and multiplication, you can freely substitute integers congruent to the integers you replace and the expression will evaluate to an integer that, although it may be different, will be congruent (mod k) to the original value.

¨  Mathematicians describe this fact as saying that “addition and multiplication are compatible with congruence”. 

Examples

130.4.2 Example As an example, what is 5⁸ congruent to (mod 16)? The arithmetic is much simplified if you reduce each time you multiply by 5:

5   5 (mod16)

52  25 9 (mod 16)

53  ₅ · 9 45 13 (mod 16)

54  5· 13 65 1 (mod 16)

58  ₍₅₄₎₂ ¹² 1 (mod 16)

130.4.3 Remark This ability to compute powers fast is the basis of an important technique in cryptography.

130.4.4 Exercise Compute:

a)5¹² (mod 4)

b)5¹² (mod 10) c) 5¹² (mod 16) (Answer on page 250.)

130.4.5 Exercise Prove that if s | t, then

ms ns (mod t)

 m n (mod t/s)

Images and metaphors for congruence

Clock