Divisor: Difference between revisions

Revision as of 22:43, 31 May 2008

A natural number ${d}$ is called a divisor of a natural number ${n}$ if there is a natural number ${k}$ such that $n=kd$ or, in other words, if $\frac nd$ is also a natural number (i.e $d$ divides $n$ ). 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$ .

See the main article on counting divisors. If $n=p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}}\cdot\dots\cdot p_m^{\alpha_m}$ is the prime factorization of ${n}$ , then the number $d(n)$ of different divisors of $n$ is given by the formula $d(n)=(\alpha_{1} + 1)\cdot(\alpha_{2} + 1)\cdot\dots\cdot(\alpha_{m} + 1)$ . It is often useful to know that this expression grows slower than any positive power of ${n}$ as $n\to\infty$ . Another useful idea is that $d(n)$ is odd if and only if ${n}$ is a perfect square.

Useful formulae

If ${m}$ and ${n}$ are relatively prime, then $d(mn)=d(m)d(n)$
${\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)}$

@@ Line 1: / Line 1: @@
-A [[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.
+A [[natural number]] <math>{d}</math> is called a '''divisor''' of a natural number <math>{n}</math> if there is a natural number <math>{k}</math> such that <math>n=kd</math> or, in other words, if <math>\frac nd</math> is also a natural number (i.e <math>d</math> divides <math>n</math>). See [[Divisibility]] for more information.
 == Notation==
@@ Line 5: / Line 5: @@
-See the main article on [[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 integer | odd]] if and only if <math>\displaystyle{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 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>{m}</math> and <math>{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>{\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==

Page

Toolbox

Search

Divisor: Difference between revisions

Revision as of 22:43, 31 May 2008

Notation

Useful formulae

See also