On the third day, starting with door number
3, he will turn the key of every third door. This
will leave a mixture of doors locked and
unlocked.
On the fourth day he will turn the key of
every fourth door, on day five the key of every
fifth door, and so on, all the way until day 100,
when he will turn the key of every 100th door,
namely, just the final door. At this time, any
prisoner who finds his door open will be
allowed to go free.
Which doors will be left unlocked as a result
of this experiment?
Observe that the warden will turn the key to door
number non each day dthat is a factor of n. For exam-
ple, the key of door number 39 will be turned on days
1, 3, 13, and 39 only, and the key of door number 25
on days 1, 5, and 25. For a door to be left unlocked at
the end of the experiment its key must be turned an
odd number of times. As only the square numbers have
an odd number of factors we have that prisoners 1, 4,
9, 16, 25, 36, 49, 64, 81, and 100 are set to go free.
Any number nalways has 1 and itself as factors.
These are called “improper factors.” Any other factor
of n, if there is one, is called a “proper factor.” For
example, 1 and 12 are improper factors of 12, and 2,
3, 4, and 6 are proper factors. A number, different
from 1, that possesses proper factors is called “com-
posite,” or a
COMPOSITE NUMBER
, and one that does
not is called
PRIME
. For example, the number 25 has a
proper factor, namely 5, and so is composite; whereas 7
has only two factors, both of which are improper, and
so is prime.
Any proper factor of a composite number, if not
itself prime, can be written as a product of two smaller
factors. Repeated application of this process shows that
any number different from 1, if not already prime, can
be written as a product of prime numbers. For example:
180 = 30 ×6 = (6 ×5) ×(2 ×3) = 2 ×3 ×5
×2 ×3.
The
FUNDAMENTAL THEOREM OF ARITHMETIC
asserts
that every integer greater than 1 factors into primes in
only one way (up to the order of the primes). A factor-
tree is a diagram that describes this factoring process
pictorially. Two students drawing different factor trees
for the same number will arrive at the same list of
primes at the bases of their trees.
In algebra, a factor is a
POLYNOMIAL
that divides
another given polynomial exactly. For example, 2x+ 1
and x– 1 are both factors of 2x2– x– 1, since 2x2– x
– 1 = (2x+ 1)(x– 1). It is generally agreed that the fac-
tors of a polynomial should themselves be nonconstant
polynomials with coefficients that are real numbers.
A polynomial that cannot be factored is called irre-
ducible. For example, x2+ 1 cannot be factored over
the real numbers and so is irreducible. If one permits
COMPLEX NUMBERS
as coefficients, then the situation
changes: we can write: x2+ 1 = (x+ i)(x– i). The
FUN
-
DAMENTAL THEOREM OF ALGEBRA
asserts that every
polynomial factors in the realm of complex numbers.
See also
COMMON FACTOR
;
DIVISIBILITY RULES
;
FACTOR THEOREM
;
GREATEST COMMON DIVISOR
;
LONG
DIVISION
;
PERFECT NUMBER
;
PRIME
.
factorial If nis a natural number, then the symbol n!
(read as “nfactorial”) denotes the product of all posi-
tive integers from 1 to n:
n! = 1 · 2 · 3·…·n
For example, 6! = 1·2·3·4·5·6 = 720. The order in
which the terms of the product are multiplied is imma-
terial. (We have that 6! also equals 6·5·4·3·2·1.)
Factorials naturally arise when counting the num-
bers of ways a collection of objects can be arranged.
Given nobjects, there are nchoices for which object we
wish to regard as “first.” Once this selection is made,
n– 1 choices remain for which object to select as sec-
ond, and after the first and second are chosen, there
remain n– 2 choices for third. This process continues
until two objects remain, yielding two choices for which
to regard second-to-last, and just one object to select as
last. By the
MULTIPLICATION PRINCIPLE
, there are thus
n· (n– 1) · (n– 2) · … · 2 · 1 = n! different
PERMUTA
-
TION
s (or arrangements, or orders) of nobjects.
If one wishes to arrange just robjects chosen from a
collection of ndifferent things, there are nchoices for
which object to regard as first, n– 1 choices for which to
regard as second, and so on, to n– r+ 1 choices for
which object to deem rth, yielding a total of n· (n– 1)·
… ·(n– r+ 1) different arrangements of robjects selected
from n. This formula can be more compactly written as:
n!
––—
(n– r)!
186 factorial