Difference between revisions of "Divisor"
ComplexZeta (talk | contribs) m (→Useful formulae: Replaced [...] by \lfloor...\rfloor) |
|||
Line 1: | Line 1: | ||
− | + | ==Definition== | |
− | Any [[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. See [[Divisibility]] for more information. | + | Any [[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 (i.e <math>d</math> divides <math>n</math>). See [[Divisibility]] for more information. |
+ | |||
+ | == Notation== | ||
+ | A common notation to indicate a number is a divisor of another is <math>n|k</math>. This means that <math>n</math> divides <math>k</math>. | ||
− | |||
− | |||
− | |||
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. | 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== | |
* 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\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>\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== | |
− | *[[ | + | * [[Divisor function]] |
− | *[[Number theory]] | + | * [[Number theory]] |
− | *[[GCD]] | + | * [[GCD]] |
− | *[[Divisibility]] | + | * [[Divisibility]] |
Revision as of 22:19, 28 July 2006
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 (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 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