Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Divisor"

(→‎See also)
(→‎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]].
 +
<math>7^1 / cdot / 5^3 / cdot / 3^1 / cdot / 2^4</math>
  
 
==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 21:26, 2 June 2022

A natural number ${d}$ is called a divisor of a natural number ${n}$ if there is a natural number ${k}$ such that $n=kd$ or, in other words, if $\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 the main article on counting divisors. If $n=p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}}\cdot\dots\cdot p_m^{\alpha_m}$ is the prime factorization of ${n}$, then the number $d(n)$ of different divisors of $n$ is given by the formula $d(n)=(\alpha_{1} + 1)\cdot(\alpha_{2} + 1)\cdot\dots\cdot(\alpha_{m} + 1)$. It is often useful to know that this expression grows slower than any positive power of ${n}$ as $n\to\infty$. We also know that the product of the divisors of any integer $n$ is \[n^{\frac{t(n)}{2}}.\] Another useful idea is that $d(n)$ is odd if and only if ${n}$ is a perfect square. $7^1 / cdot / 5^3 / cdot / 3^1 / cdot / 2^4$

Useful formulas

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Divisor&oldid=174269"