Divisor

Revision as of 23:19, 28 July 2006 by Joml88 (talk | contribs)

Definition

Any 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

See also