relatively prime (coprime) Two integers a and b
are relatively prime if their GREATEST COMMON FACTOR is 1. Consequently, the only factor the two numbers have in common is 1. For example, 15 and 28 are
relatively prime. Any two consecutive numbers are
relatively prime.
Relatively prime numbers play a key role in the
famous postage-stamp problem:
Which postage values can be obtained using 5cent and 7-cent stamps only?
For example, one can compose a postage value of 22
cents with three 5-cent stamps, and one 7-cent stamp,
but the quantity 23 cents cannot be so obtained. One
can check that each quantity 24, 25, 26, 27, and 28 is
possible. Adding multiples of 5 to each of these numbers then shows that any quantity greater than 24 is
obtainable. (Below this, one can check that only the
values 5, 7, 10, 12, 14, 15, 17, 19, 20, 21, and 22 can
be composed.)
In general, given two stamp values a and b, with
values a and b relatively prime, one can prove that
there is always a number N so that every quantity N
and above can be composed as a combination of
stamps of each type. This result is not true if a and b
are not relatively prime.
Mathematicians have shown that the PROBABILITY
that two integers chosen at random are relatively prime
is
≈ 0.61.
See also COMMON FACTOR; FACTOR; JUG-FILLING
PROBLEM.
remainder theorem The process of LONG DIVISION
shows that if a POLYNOMIAL p(x) of degree n is divided
by a second polynomial q(x) of degree m, one obtains,
apart from a QUOTIENT term Q(x), a remainder polynomial R(x) of degree strictly smaller than m:
p(x) = Q(x)q(x) + R(x)
For instance, dividing p(x) = x
4 – x
3 + 2x
2 + x + 4 by
the degree-2 polynomial q(x) = x
2 + 1 yields a remainder R(x) = 2x + 1 of degree 1:
In particular, if a polynomial p(x) is divided by a linear term x – a for some constant a, the result remainder
must be a polynomial of degree zero, that is, a constant:
p(x) = Q(x) (x – a) + b
Setting x = a into this equation shows that p(a) = 0 + b.
Thus the remainder term b is simply the value of the
polynomial at x = a. This observation is called the
remainder theorem:
If a polynomial p(x) is divided by the term
x – a, for some constant a, then the remainder term is p(a):
p(x) = (x – a)Q(x) + p(a)
For example, if p(x) = x
3 – 7x
2 + 2x + 4 is divided by
x + 1 = x – (–1), the remainder will be p(–1) = – 1 – 7
– 2 + 4 = –6.
The remainder theorem is useful for finding the
factors of a polynomial. For instance, for the polynomial p(x) = x
3 – 7x
2 + 2x + 4, we have p(1) = 1 – 7 + 2
+ 4 = 0, indicating that (x – 1) is a factor: x
3 – 7x
2 + 2x
+ 4 = (x – 1)Q(x) + p(1) = (x – 1)Q(x).
See also FACTOR THEOREM; FUNDAMENTAL THEOREM OF ALGEBRA.
removable discontinuity See CONTINUOUS FUNCTION.
Reuleaux’s triangle See CONSTANT WIDTH.
Rhind papyrus (Ahmes papyrus) This famous document is the oldest written mathematical text known to
exist. Currently housed in the British Museum, this 18ft long roll of papyrus, 13 in. wide, dates back to ca.
1650 B.C.E. The document was discovered buried in the
Egyptian desert sands, near the Valley of the Kings, in
the mid-1800s by an unknown Egyptian citizen. Visiting Scotsman Alexander Henry Rhind (1833–63), who
had an interest in antiquities, bought the papyrus and
transported it to Britain.
The papyrus is a copy of a work that dates back at
least 200 years earlier. Although the text consists
mainly of numerical problems and solutions, with an
emphasis on practical application, it is clear that the
x x
x x
x x
x
x
p x
Q x
q x
R x
4
3
2
2
2
2
4
1
1
2
3
− +
+ + =
+ +
(
) +
( ) + +
(
)
( )
( )
( )
( )
6
––
π
2
446 relatively prime
are relatively prime if their GREATEST COMMON FACTOR is 1. Consequently, the only factor the two numbers have in common is 1. For example, 15 and 28 are
relatively prime. Any two consecutive numbers are
relatively prime.
Relatively prime numbers play a key role in the
famous postage-stamp problem:
Which postage values can be obtained using 5cent and 7-cent stamps only?
For example, one can compose a postage value of 22
cents with three 5-cent stamps, and one 7-cent stamp,
but the quantity 23 cents cannot be so obtained. One
can check that each quantity 24, 25, 26, 27, and 28 is
possible. Adding multiples of 5 to each of these numbers then shows that any quantity greater than 24 is
obtainable. (Below this, one can check that only the
values 5, 7, 10, 12, 14, 15, 17, 19, 20, 21, and 22 can
be composed.)
In general, given two stamp values a and b, with
values a and b relatively prime, one can prove that
there is always a number N so that every quantity N
and above can be composed as a combination of
stamps of each type. This result is not true if a and b
are not relatively prime.
Mathematicians have shown that the PROBABILITY
that two integers chosen at random are relatively prime
is
≈ 0.61.
See also COMMON FACTOR; FACTOR; JUG-FILLING
PROBLEM.
remainder theorem The process of LONG DIVISION
shows that if a POLYNOMIAL p(x) of degree n is divided
by a second polynomial q(x) of degree m, one obtains,
apart from a QUOTIENT term Q(x), a remainder polynomial R(x) of degree strictly smaller than m:
p(x) = Q(x)q(x) + R(x)
For instance, dividing p(x) = x
4 – x
3 + 2x
2 + x + 4 by
the degree-2 polynomial q(x) = x
2 + 1 yields a remainder R(x) = 2x + 1 of degree 1:
In particular, if a polynomial p(x) is divided by a linear term x – a for some constant a, the result remainder
must be a polynomial of degree zero, that is, a constant:
p(x) = Q(x) (x – a) + b
Setting x = a into this equation shows that p(a) = 0 + b.
Thus the remainder term b is simply the value of the
polynomial at x = a. This observation is called the
remainder theorem:
If a polynomial p(x) is divided by the term
x – a, for some constant a, then the remainder term is p(a):
p(x) = (x – a)Q(x) + p(a)
For example, if p(x) = x
3 – 7x
2 + 2x + 4 is divided by
x + 1 = x – (–1), the remainder will be p(–1) = – 1 – 7
– 2 + 4 = –6.
The remainder theorem is useful for finding the
factors of a polynomial. For instance, for the polynomial p(x) = x
3 – 7x
2 + 2x + 4, we have p(1) = 1 – 7 + 2
+ 4 = 0, indicating that (x – 1) is a factor: x
3 – 7x
2 + 2x
+ 4 = (x – 1)Q(x) + p(1) = (x – 1)Q(x).
See also FACTOR THEOREM; FUNDAMENTAL THEOREM OF ALGEBRA.
removable discontinuity See CONTINUOUS FUNCTION.
Reuleaux’s triangle See CONSTANT WIDTH.
Rhind papyrus (Ahmes papyrus) This famous document is the oldest written mathematical text known to
exist. Currently housed in the British Museum, this 18ft long roll of papyrus, 13 in. wide, dates back to ca.
1650 B.C.E. The document was discovered buried in the
Egyptian desert sands, near the Valley of the Kings, in
the mid-1800s by an unknown Egyptian citizen. Visiting Scotsman Alexander Henry Rhind (1833–63), who
had an interest in antiquities, bought the papyrus and
transported it to Britain.
The papyrus is a copy of a work that dates back at
least 200 years earlier. Although the text consists
mainly of numerical problems and solutions, with an
emphasis on practical application, it is clear that the
x x
x x
x x
x
x
p x
Q x
q x
R x
4
3
2
2
2
2
4
1
1
2
3
− +
+ + =
+ +
(
) +
( ) + +
(
)
( )
( )
( )
( )
6
––
π
2
446 relatively prime