Divisor
Revision as of 22:59, 21 June 2006 by ComplexZeta (talk | contribs) (→Useful formulae: Replaced [...] by \lfloor...\rfloor)
Contents
[hide]Definition
Any natural number is called a divisor of a natural number
if there is a natural number
such that
or, in other words, if
is also a natural number. See Divisibility for more information.
Notation
A common notation to indicate a number is a divisor of another is n|k. This means that n divides k.
How many divisors does a number have
See main article, Counting divisors. If is the prime factorization of
, then the number
of different divisors of
is given by the formula
. It is often useful to know that this expression grows slower than any positive power of
as
. Another useful idea is that
is odd if and only if
is a perfect square.
Useful formulae
- If
and
are relatively prime, then