Basic Definitions

Unique Prime Factorization

 
Not all sets of numbers have this 'UF' or unique factorization property. For example,
9 = 3 * 3 = (7 + 2 sqrt[10])(7 - 2 sqrt[10]) but none of these can be broken up further using
numbers of the form a + b sqrt[10], so the "ring of integers" Z[sqrt[10]] is not a UFD or
'unique factorization domain.'

Divisors (counting and adding them) (See Prob Of Week #150)

Example 1: How many numbers go into 36 evenly (with no remainder)?

There are 9 divisors of 36 : {1, 2, 3, 4, 6, 9, 12, 18, 36}.
These can be arranged into a 3 x 3 rectangle, called a divisor chart:

      1

      2

      4

      3

      6

      12

      9

      18

      36

     

Notice from above that 36 = 2^2 * 3^2 ; the exponents are 2 and 2.
There is one more column than powers of 2, and one more row than powers of 3,
so there are 3 x 3 = 9 divisors. Our function notation is d(36) = 9.
       
Example 2: How many divisors does 21 million have?

21,000,000 = 3 * 7 * 10^6 = 2^6 * 3^1 * 5^6 * 7^1 ;

the exponents are 6, 1, 6, and 1 ; so the number has 7 * 2 * 7 * 2 = 196 divisors :
They are {1, 2, 3, 4, 5, 6, 7, 8, 10, . . . , 10500000, 21000000} (I left a few out.)
 
Example 3: What do the divisors in the 36-chart add up to?
See below that the actual sum is 91 ; but also notice that the column sum and row sum
that start with 1 are 1+3+9 = 13 , 1+2+4 = 7 , and that 13*7 = 91. Coincidence? Hmm . . .

Arithmetic Functions (pronounced "a-rith-MEH-tic") 8/01

Let's look at several integer functions using function notation, inputting only integers:
d(n) = number of (positive) divisors of n (including 1 and n)
s(n) = sum of divisors of n (incl. 1 and n; usually 'sigma(n)')
ph(n) = number of nos. less than n with no common factors with n (usu. 'phi of n').
A(n) = abundancy index of n, defined as the ratio s(n) / n .
 
For example if n = 36 we have nine divisors ; so
d(36) = #{1, 2, 3, 4, 6, 9, 12, 18, 36} = 9 ; s(36) = 1+2+3+4+6+9+12+18+36 = 91 ;
ph(36) = #{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35} = 12 ; A(36) = 91 / 36 ~ 2.528.
 
One special case: if n = p prime, then d(p) = 2, s(p) = p+1, ph(p) = 1, A(p) = 1+(1/p).
The n is perfect if s(n) = 2n, or A(n) = 2 ; deficient if A(n) < 2 , and abundant if A(n) > 2.
For example, 36 is abundant, 35 is deficient, and 28 is perfect. Check it yourself!
 
For a good source of super-abundant numbers see the supercomposites page.
Challenge: Try to prove or at least verify with examples that d, s, and ph are
"multiplicative" functions, meaning that if m and n are relatively prime then
d(mn) = d(m) d(n) and so on (for s and ph)..
What about the case where m and n have a common factor k? What if there
are more than two numbers? What about the A function, is it multiplicative?
     
 
Well, that's it for now. Check back often for new stuff!
Click below for other topics, or visit the ask dan page!
 
[ number theory | geometry | top of page | lessons index]

 
+ Basic Skills +
Arithmetic, Prealgebra, Beginning Algebra
+ Precalculus +
Intermed.Algebra, Functions & graphs, Trigonometry
+ Calculus +
Limits, Differential Calc, Integral Calc, Vector Calc
+ Beyond Calculus +
Linear Algebra, Diff Equations, Math Major stuff
+ Other Stuff + You are here
Statistics, Number Theory, Geometry, Other requests?