Divisor: Difference between revisions

Revision as of 11:39, 21 June 2006

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. 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.

How many divisors does a number have

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[\frac N1\right]+\left[\frac N2\right]+\dots+\left[\frac NN\right]= N\ln N+O(N)}$

@@ 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.
+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.
+=== Notation===
+A common notation to indicate a number is a divisor of another is n|k. This means that n divides k.
 ===How many divisors does a number have===
@@ Line 12: / Line 15: @@
 *[[Number theory]]
 *[[GCD]]
+*[[Divisibility]]

Page

Toolbox

Search