Fermat’s Little Theorem
Let pbe a prime number. Then for every nonzero num-
ber aless 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:
ap–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 P
IERRE DE
F
ERMAT
(1601–65):
For any prime number p, ap–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 2p–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, 2340 –1 is divisible by 341, even though 341 is
composite. (We have 341 = 11 ×31.) Composite num-
bers 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θ= reiθ, then its modu-
lus is r.
In the study of
LOGARITHM
s, the number by which
logarithms of one base are multiplied to give loga-
rithms of a different base is called the modulus. For
example, the equation:
logax×logba= logbx
shows that multiplication by the modulus logbacon-
verts logarithms of base ato ones of base b. (To see
why this works, note that if y= logax, then ay= x.
Consequently, logb(ay) = logbx, yielding y×logba=
logbx.) In particular, multiplication by the number
log10e≈0.434294 converts natural logarithms into
common logarithms.
In
MODULAR ARITHMETIC
, the number by which
quantities are divided is called the modulus of the sys-
tem. For example, in “clock math,” the modulus of the
system is 12.
monomial Any algebraic expression consisting of a
single term, such as 5x3y2, is called a monomial.
See also
BINOMIAL
;
POLYNOMIAL
;
TRINOMIAL
.
Monte Carlo method Pioneered by J
OHN VON
N
EU
-
MANN
(1903–57) and the Polish mathematician Stanislav
Ulam, the Monto Carlo method is a simple probabilistic
method that is sometimes employed by applied mathe-
maticians 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 per-
form 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 tech-
nique 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 pho-
tograph, say a 4-by-5-km rectangle. The photograph is
then digitized and fed into a computer, which is pro-
grammed to select, at random, a large number of points
√a2+ b2
1
––
p –1
1
–
3
1
–
2
342 modulus