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 )
Definition An integer k divides a nonzero integer m (written ) if there is an integer q with the property that .
(“3 divides 6”) because
¨ k divides m.
¨ k is a divisor of m.
¨ k is a factor of m.
¨ m is divisible by k.
¨ 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.
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
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
¨ 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.
¨ 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.
For a fixed positive integer k, congruence (mod k) is an equivalence relation on .
¨ 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
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
b) for some integer q
To make this a valid definition you must show that there is just one integer satisfying a) and b).
¨ 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.
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.
If and then and
¨ 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”.