Difference between revisions of "Divisor"
(→Notation) |
(→Notation) |
||
Line 8: | Line 8: | ||
We also know that the product of the divisors of any integer <math>n</math> is <cmath>n^{\frac{t(n)}{2}}.</cmath> | We also know that the product of the divisors of any integer <math>n</math> is <cmath>n^{\frac{t(n)}{2}}.</cmath> | ||
Another useful idea is that <math>d(n)</math> is [[odd integer | odd]] if and only if <math>{n}</math> is a [[perfect square]]. | 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 formulas== | ==Useful formulas== | ||
* If <math>{m}</math> and <math>{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>{\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> |
Revision as of 22:39, 2 June 2022
A 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 the main article on 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
.
We also know that the product of the divisors of any integer
is
Another useful idea is that
is odd if and only if
is a perfect square.
Useful formulas
- If
and
are relatively prime, then