Difference between revisions of "Divisor"
IntrepidMath (talk | contribs) |
|||
| Line 2: | Line 2: | ||
An [[natural number]] <math>\displaystyle{d}</math> is called a divisor of a natural number <math>\displaystyle{n}</math> if there is a natural number <math>\displaystyle{k}</math> such that <math>n=kd</math> or, in other words, if <math>\displaystyle\frac nd</math> is also a natural number. | An [[natural number]] <math>\displaystyle{d}</math> is called a divisor of a natural number <math>\displaystyle{n}</math> if there is a natural number <math>\displaystyle{k}</math> such that <math>n=kd</math> or, in other words, if <math>\displaystyle\frac nd</math> is also a natural number. | ||
===How many divisors does a number have=== | ===How many divisors does a number have=== | ||
| − | If <math>n=p_1^{\alpha_1}\cdot\dots\cdot p_n^{\alpha_n}</math> is the [[prime factorization]] of <math>\displaystyle{n}</math>, then the number <math>d(n)</math> of different divisors of <math>n</math> is given by the formula <math>d(n)=(\alpha_1+1)\cdot\dots\cdot(\alpha_n+1)</math>. It is often useful to know that this expression grows slower than any positive power of <math>\displaystyle{n}</math> as <math>\displaystyle n\to\infty</math>. Another useful idea is that <math>d(n)</math> is odd if and only if <math>\displaystyle{n}</math> is a perfect square. | + | See main article, [[Counting divisors]]. If <math>n=p_1^{\alpha_1}\cdot\dots\cdot p_n^{\alpha_n}</math> is the [[prime factorization]] of <math>\displaystyle{n}</math>, then the number <math>d(n)</math> of different divisors of <math>n</math> is given by the formula <math>d(n)=(\alpha_1+1)\cdot\dots\cdot(\alpha_n+1)</math>. It is often useful to know that this expression grows slower than any positive power of <math>\displaystyle{n}</math> as <math>\displaystyle n\to\infty</math>. Another useful idea is that <math>d(n)</math> is odd if and only if <math>\displaystyle{n}</math> is a perfect square. |
| + | |||
===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> | ||
| Line 8: | Line 9: | ||
===See also=== | ===See also=== | ||
*[[Sum of divisors function]] | *[[Sum of divisors function]] | ||
| + | *[[Number theory]] | ||
| + | *[[GCD]] | ||
Revision as of 22:47, 19 June 2006
Definition
An 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.
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)
