Divisor
Revision as of 11:39, 21 June 2006 by IntrepidMath (talk | contribs)
Contents
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 
![$\displaystyle{\sum_{n=1}^N d(n)=\left[\frac N1\right]+\left[\frac N2\right]+\dots+\left[\frac NN\right]= N\ln N+O(N)}$](//latex.artofproblemsolving.com/a/9/8/a98664acaee0cdf2e8a2201dc9c5f4971e5db6cf.png)
and 
![$\displaystyle{\sum_{n=1}^N d(n)=\left[\frac N1\right]+\left[\frac N2\right]+\dots+\left[\frac NN\right]= N\ln N+O(N)}$](http://latex.artofproblemsolving.com/a/9/8/a98664acaee0cdf2e8a2201dc9c5f4971e5db6cf.png)
