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 n on each day d that is a factor of n. For example, 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 n always 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 “composite,” 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 factortree 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 2x
2 – x – 1, since 2x
2 – x
– 1 = (2x + 1)(x – 1). It is generally agreed that the factors of a polynomial should themselves be nonconstant
polynomials with coefficients that are real numbers.
A polynomial that cannot be factored is called irreducible. For example, x
2 + 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: x
2 + 1 = (x + i)(x – i). The FUNDAMENTAL 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 n is a natural number, then the symbol n!
(read as “n factorial”) denotes the product of all positive 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 immaterial. (We have that 6! also equals 6·5·4·3·2·1.)
Factorials naturally arise when counting the numbers of ways a collection of objects can be arranged.
Given n objects, there are n choices for which object we
wish to regard as “first.” Once this selection is made,
n – 1 choices remain for which object to select as second, 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 PERMUTATIONs (or arrangements, or orders) of n objects.
If one wishes to arrange just r objects chosen from a
collection of n different things, there are n choices 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 r objects selected
from n. This formula can be more compactly written as:
n!
––—
(n – r)!
186 factorial
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 n on each day d that is a factor of n. For example, 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 n always 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 “composite,” 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 factortree 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 2x
2 – x – 1, since 2x
2 – x
– 1 = (2x + 1)(x – 1). It is generally agreed that the factors of a polynomial should themselves be nonconstant
polynomials with coefficients that are real numbers.
A polynomial that cannot be factored is called irreducible. For example, x
2 + 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: x
2 + 1 = (x + i)(x – i). The FUNDAMENTAL 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 n is a natural number, then the symbol n!
(read as “n factorial”) denotes the product of all positive 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 immaterial. (We have that 6! also equals 6·5·4·3·2·1.)
Factorials naturally arise when counting the numbers of ways a collection of objects can be arranged.
Given n objects, there are n choices for which object we
wish to regard as “first.” Once this selection is made,
n – 1 choices remain for which object to select as second, 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 PERMUTATIONs (or arrangements, or orders) of n objects.
If one wishes to arrange just r objects chosen from a
collection of n different things, there are n choices 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 r objects selected
from n. This formula can be more compactly written as:
n!
––—
(n – r)!
186 factorial