Difference between revisions of "Divisor"
(→Notation) |
(→Notation) |
||
(2 intermediate revisions by 2 users not shown) | |||
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> |
Latest revision as of 18:50, 29 August 2023
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