Last edited 10/31/2008 8:55:00 AM
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.)
|
Definition An integer k divides a nonzero integer m (written ) if there is an integer q with the property that .
¨
(“3 divides 6”) because
¨
¨
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.
¨
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
¨
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,
Don’t read things into the definition that are not there
Let
k be a positive integer and m and n be any integers. Then m is congruent to n mod k if k divides .
¨ 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
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).
¨ 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”.