Fermat’s Little Theorem
Let p be a prime number. Then for every nonzero number a less than p, all the digits zero through p – 1
appear in the ath row of the product table for mod-p
arithmetic. Ignoring the zeroth multiple of a, this
asserts that all the multiples of a, namely, a × 1, a × 2,
…, a × (p – 1), correspond, in some order, to the list of
digits 1, 2, …, p – 1. Consequently, the product of the
numbers in each list must be the same:
a × 1 × a × 2 ×…× a × (p – 1) = 1 × 2 ×…× (p – 1)
Rewriting yields:
a
p–1
× 1 × 2 ×…× (p – 1) = 1 × 2 ×…× (p – 1)
Multiplying through by the fractions , , up to
(which exist in prime-clock math) gives the famous
result first discovered by French lawyer and amateur
mathematician PIERRE DE FERMAT (1601–65):
For any prime number p, a
p–1
≡ 1 (mod p) for
all nonzero values a < p.
Applying this observation to the specific value a = 2
provides a useful method for testing the primality of
numbers: if p is prime, then 2
p–1 –1 is divisible by p. If
not, then the number p is not prime. Unfortunately,
some numbers pass the test without being prime. For
instance, 2
340 –1 is divisible by 341, even though 341 is
composite. (We have 341 = 11 × 31.) Composite numbers of this type are called pseudo-primes.
See also CONGRUENCE.
modulus (plural, moduli) The ABSOLUTE VALUE of a
quantity, without consideration of its sign or direction,
is sometimes called the modulus of the quantity. For
example, the numbers –3 and 3, although of opposite
parity, have the same modulus of 3. The modulus of a
VECTOR is its length, and the modulus of a COMPLEX
NUMBER is the length of the vector that represents that
complex number. Specifically, if z = a + ib is a complex
number, then its modulus, written |z|, is the nonnegative
real number
. If the complex number is written
in polar form, z = rcosθ + irsinθ = re
iθ , then its modulus is r.
In the study of LOGARITHMs, the number by which
logarithms of one base are multiplied to give logarithms of a different base is called the modulus. For
example, the equation:
log a x × log b a = log b x
shows that multiplication by the modulus log b a converts logarithms of base a to ones of base b. (To see
why this works, note that if y = log a x, then a
y = x.
Consequently, log b (a
y ) = log b x, yielding y × log b a =
log b x.) In particular, multiplication by the number
log 10 e ≈ 0.434294 converts natural logarithms into
common logarithms.
In MODULAR ARITHMETIC, the number by which
quantities are divided is called the modulus of the system. For example, in “clock math,” the modulus of the
system is 12.
monomial Any algebraic expression consisting of a
single term, such as 5x
3
y
2
, is called a monomial.
See also BINOMIAL; POLYNOMIAL; TRINOMIAL.
Monte Carlo method Pioneered by JOHN VON NEUMANN (1903–57) and the Polish mathematician Stanislav
Ulam, the Monto Carlo method is a simple probabilistic
method that is sometimes employed by applied mathematicians to analyze processes that are too complicated
to analyze otherwise. Named after the famous gambling
casino, the Monte Carlo method simply uses the LAW OF
LARGE NUMBERS to estimate the probability of a desired
event occurring. For example, to estimate the probability
that five letters chosen at random from the alphabet spell
a word in the English language, one could simply perform the experiment a large number of times (that is,
have a computer select five letters at random 1,000 times,
say) and count the proportion of times an English word
is obtained. This proportion gives an estimate of the
probability one seeks. Many casinos employ this technique to determine the payout ODDS for many of their
complicated games.
The Monte Carlo method is also used to estimate
the area of a plane figure with an irregular outline. For
example, to estimate the area of an oil spill over the
ocean, scientists take an aerial photograph of the entire
spill, taking note of the dimensions covered by the photograph, say a 4-by-5-km rectangle. The photograph is
then digitized and fed into a computer, which is programmed to select, at random, a large number of points
√a
2 + b
2
1
––
p –1
1
–
3
1
–
2
342 modulus
Let p be a prime number. Then for every nonzero number a less than p, all the digits zero through p – 1
appear in the ath row of the product table for mod-p
arithmetic. Ignoring the zeroth multiple of a, this
asserts that all the multiples of a, namely, a × 1, a × 2,
…, a × (p – 1), correspond, in some order, to the list of
digits 1, 2, …, p – 1. Consequently, the product of the
numbers in each list must be the same:
a × 1 × a × 2 ×…× a × (p – 1) = 1 × 2 ×…× (p – 1)
Rewriting yields:
a
p–1
× 1 × 2 ×…× (p – 1) = 1 × 2 ×…× (p – 1)
Multiplying through by the fractions , , up to
(which exist in prime-clock math) gives the famous
result first discovered by French lawyer and amateur
mathematician PIERRE DE FERMAT (1601–65):
For any prime number p, a
p–1
≡ 1 (mod p) for
all nonzero values a < p.
Applying this observation to the specific value a = 2
provides a useful method for testing the primality of
numbers: if p is prime, then 2
p–1 –1 is divisible by p. If
not, then the number p is not prime. Unfortunately,
some numbers pass the test without being prime. For
instance, 2
340 –1 is divisible by 341, even though 341 is
composite. (We have 341 = 11 × 31.) Composite numbers of this type are called pseudo-primes.
See also CONGRUENCE.
modulus (plural, moduli) The ABSOLUTE VALUE of a
quantity, without consideration of its sign or direction,
is sometimes called the modulus of the quantity. For
example, the numbers –3 and 3, although of opposite
parity, have the same modulus of 3. The modulus of a
VECTOR is its length, and the modulus of a COMPLEX
NUMBER is the length of the vector that represents that
complex number. Specifically, if z = a + ib is a complex
number, then its modulus, written |z|, is the nonnegative
real number
. If the complex number is written
in polar form, z = rcosθ + irsinθ = re
iθ , then its modulus is r.
In the study of LOGARITHMs, the number by which
logarithms of one base are multiplied to give logarithms of a different base is called the modulus. For
example, the equation:
log a x × log b a = log b x
shows that multiplication by the modulus log b a converts logarithms of base a to ones of base b. (To see
why this works, note that if y = log a x, then a
y = x.
Consequently, log b (a
y ) = log b x, yielding y × log b a =
log b x.) In particular, multiplication by the number
log 10 e ≈ 0.434294 converts natural logarithms into
common logarithms.
In MODULAR ARITHMETIC, the number by which
quantities are divided is called the modulus of the system. For example, in “clock math,” the modulus of the
system is 12.
monomial Any algebraic expression consisting of a
single term, such as 5x
3
y
2
, is called a monomial.
See also BINOMIAL; POLYNOMIAL; TRINOMIAL.
Monte Carlo method Pioneered by JOHN VON NEUMANN (1903–57) and the Polish mathematician Stanislav
Ulam, the Monto Carlo method is a simple probabilistic
method that is sometimes employed by applied mathematicians to analyze processes that are too complicated
to analyze otherwise. Named after the famous gambling
casino, the Monte Carlo method simply uses the LAW OF
LARGE NUMBERS to estimate the probability of a desired
event occurring. For example, to estimate the probability
that five letters chosen at random from the alphabet spell
a word in the English language, one could simply perform the experiment a large number of times (that is,
have a computer select five letters at random 1,000 times,
say) and count the proportion of times an English word
is obtained. This proportion gives an estimate of the
probability one seeks. Many casinos employ this technique to determine the payout ODDS for many of their
complicated games.
The Monte Carlo method is also used to estimate
the area of a plane figure with an irregular outline. For
example, to estimate the area of an oil spill over the
ocean, scientists take an aerial photograph of the entire
spill, taking note of the dimensions covered by the photograph, say a 4-by-5-km rectangle. The photograph is
then digitized and fed into a computer, which is programmed to select, at random, a large number of points
√a
2 + b
2
1
––
p –1
1
–
3
1
–
2
342 modulus