Difference between revisions of "Divisor"

Revision as of 15:29, 12 October 2006

A natural number $\displaystyle{d}$ is called a divisor of a natural number $\displaystyle{n}$ if there is a natural number $\displaystyle{k}$ such that $n=kd$ or, in other words, if $\displaystyle\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 main article, Counting divisors. If $n=p_1^{\alpha_1}\cdot\dots\cdot p_n^{\alpha_n}$ is the prime factorization of $\displaystyle{n}$ , then the number $d(n)$ of different divisors of $n$ is given by the formula $d(n)=(\alpha_1+1)\cdot\dots\cdot(\alpha_n+1)$ . It is often useful to know that this expression grows slower than any positive power of $\displaystyle{n}$ as $\displaystyle n\to\infty$ . Another useful idea is that $d(n)$ is odd if and only if $\displaystyle{n}$ is a perfect square.

Useful formulae

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

Revision as of 08:36, 11 August 2006 (view source) JBL (talk \| contribs) m ← Older edit		Revision as of 15:29, 12 October 2006 (view source) JBL (talk \| contribs) m (→‎Notation) Newer edit →
Line 5:		Line 5:


−	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 integer \| odd]] if and only if <math>\displaystyle{n}</math> is a perfect square.

	==Useful formulae==		==Useful formulae==

Page

Toolbox

Search

Difference between revisions of "Divisor"

Revision as of 15:29, 12 October 2006

Notation

Useful formulae

See also