Difference between revisions of "Divisor"
m |
m (→Useful formulae) |
||
| Line 7: | Line 7: | ||
See the main article on [[counting divisors]]. If <math>n=p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}}\cdot\dots\cdot p_m^{\alpha_m}</math> is the [[prime factorization]] of <math>{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(\alpha_{2} + 1)\cdot\dots\cdot(\alpha_{m} + 1)</math>. It is often useful to know that this expression grows slower than any positive power of <math>{n}</math> as <math>n\to\infty</math>. Another useful idea is that <math>d(n)</math> is [[odd integer | odd]] if and only if <math>{n}</math> is a [[perfect square]]. | See the main article on [[counting divisors]]. If <math>n=p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}}\cdot\dots\cdot p_m^{\alpha_m}</math> is the [[prime factorization]] of <math>{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(\alpha_{2} + 1)\cdot\dots\cdot(\alpha_{m} + 1)</math>. It is often useful to know that this expression grows slower than any positive power of <math>{n}</math> as <math>n\to\infty</math>. Another useful idea is that <math>d(n)</math> is [[odd integer | odd]] if and only if <math>{n}</math> is a [[perfect square]]. | ||
| − | ==Useful | + | ==Useful formulas== |
* If <math>{m}</math> and <math>{n}</math> are [[relatively prime]], then <math>d(mn)=d(m)d(n)</math> | * If <math>{m}</math> and <math>{n}</math> are [[relatively prime]], then <math>d(mn)=d(m)d(n)</math> | ||
* <math>{\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> | * <math>{\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> | ||
Revision as of 13:26, 13 June 2016
A 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 (i.e 
divides 
). See Divisibility for more information.
Notation
A common notation to indicate a number is a divisor of another is 
. This means that divides 
.
See the main article on 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 formulas
- If
and 
are relatively prime, then 
and 
