Difference between revisions of "Divisor"
IntrepidMath (talk | contribs) |
ComplexZeta (talk | contribs) m (→Useful formulae: Replaced [...] by \lfloor...\rfloor) |
||
| Line 10: | Line 10: | ||
===Useful formulae=== | ===Useful formulae=== | ||
* If <math>\displaystyle{m}</math> and <math>\displaystyle{n}</math> are [[relatively prime]], then <math>d(mn)=d(m)d(n)</math> | * If <math>\displaystyle{m}</math> and <math>\displaystyle{n}</math> are [[relatively prime]], then <math>d(mn)=d(m)d(n)</math> | ||
| − | * <math>\displaystyle{\sum_{n=1}^N d(n)=\left | + | * <math>\displaystyle{\sum_{n=1}^N d(n)=\left\lfloor\frac N1\right\rfloor+\left\lfloor\frac N2\right\rfloor+\dots+\left\lfloor\frac NN\right\rfloor= N\ln N+O(N)}</math> |
| + | |||
===See also=== | ===See also=== | ||
*[[Sum of divisors function]] | *[[Sum of divisors function]] | ||
Revision as of 22:59, 21 June 2006
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 
and 
