Divisor
From AoPSWiki
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 
. Another useful idea is that is odd if and only if is a perfect square.
Useful formulae
- If
and are relatively prime, then 
-
