...H.G.Hasler
During the Second World ar, a general in an order of the day, issued the following statement: "This was a bad day for Nippon. The number of Jap Prisoners taken in the present drive can be easily found from the following simple addition:
N I P S
Q U I T
= Q U I C K
To help you along I'll tell you that S=5, P=4 and T=3." How many Jap Prisoners did the general take?
Suppose you need to measure exactly 1 cup of water. All that you have in your kitchen are two smaller container holds 3 cups and the larger holds 5 cups. How can you use these two containers to measure exactly one cup of water?
1.1 Sets of Numbers and Interval Notation
1.2 Operations on Real Numbers
1.3 Simplifying Expressions
1.4 Linear Equations in One Variable
1.5 Applications of Linear Equations in One Variable
1.6 Literal Equations and Applications to Geometry
1.7 Linear Inequalities in One Variable
1.8 Properties of Integer Exponents and Scientific Notation
2.1 The Rectangular Coordinate System and Midpoint Formula
2.2 Linear Equations in Two Variables
2.3 Slope of a Line
2.4 Equations of a Line
2.5 Applications of Linear Equations and Graphing
3.1 Solving Systems of Linear Equations by Graphing
3.2 Solving Systems of Equations by Using the Substitution Method
3.3 Solving Systems of Equations by Using the Addition Method
3.4 Applications of Systems of Linear Equations in Two Variables
3.5 Systems of Linear Equations in Three Variables and Applications
3.6 Solving Systems of Linear Equations by Using Matrices
3.7 Determinants and Cramer�s Rule
4.1 Introduction to Relations
4.2 Introduction to Functions
4.3 Graphs of Functions
4.4 Variation
5.1 Addition and Subtraction of Polynomials and Polynomial Functions
5.2 Multiplication of Polynomials
5.3 Division of Polynomials Problem Recognition Exercises�Operations on Polynomials
5.4 Greatest Common Factor and Factoring by Grouping
5.5 Factoring Trinomials
5.6 Factoring Binomials
5.7 Additional Factoring Summary
5.8 Solving Equations by Using the Zero Product Rule
6.1 Rational Expressions and Rational Functions
6.2 Multiplication and Division of Rational Expressions
6.3 Addition and Subtraction of Rational Expressions
6.4 Complex Fractions Problem Recognition Exercises�Operations on Rational Expressions
6.5 Rational Equations
6.6 Applications of Rational Equations and Proportions
7.2 Rational Exponents
7.3 Simplifying Radical Expressions
7.4 Addition and Subtraction of Radicals
7.5 Multiplication of Radicals
7.6 Rationalization
7.7 Radical Equations
7.8 Complex Numbers
8.2 Quadratic Formula
8.3 Equations in Quadratic Form
8.4 Graphs of Quadratic Functions
8.5 Vertex of a Parabola and Applications
9.2 Polynomial and Rational Inequalities
9.3 Absolute Value Equations
9.4 Absolute Value Inequalities Problem Recognition Exercises�Equations and Inequalities
9.5 Linear Inequalities in Two Variables
| Please let us know what you think to our NEW WEBSITE! |
|---|
1.3.6. Theorem. [Chinese Remainder Theorem] Let n and m be positive integers, with (n,m)=1. Then the system of congruences
x a (mod n) x b (mod m) has a solution. Moreover, any two solutions are congruent modulo mn.
1.4.1. Definition. Let a and n>0 be integers. The set of all integers which have the same remainder as a when divided by n is called the congruence class of a modulo n, and is denoted by [a]n, where
[a]n = { x Z | x a (mod n) }.
The collection of all congruence classes modulo n is called the set of integers modulo n, denoted by Zn.
1.4.2 Proposition. Let n be a positive integer, and let a,b be any integers. Then the addition and multiplication of congruence classes given below are well-defined:
[a]n + [b]n = [a+b]n , [a]n[b]n = [ab]n.
1.4.3. Definition. If [a]n belongs to Zn, and [a]n[b]n = [0]n for some nonzero congruence class [b]n, then [a]n is called a divisor of zero, modulo n.
1.4.4. Definition. If [a]n belongs to Zn, and [a]n[b]n = [1]n, for some congruence class [b]n, then [b]n is called a multiplicative inverse of [a]n and is denoted by [a]n-1. In this case, we say that [a]n and [b]n are invertible elements of Zn, or units of Zn.
1.4.5. Proposition. Let n be a positive integer.
(a) The congruence class [a]n has a multiplicative inverse in Zn if and only if (a,n)=1.
(b) A nonzero element of Zn either has a multiplicative inverse or is a divisor of zero.
1.4.6. Corollary. The following conditions on the modulus n > 0 are equivalent:
(1) The number n is prime.
(2) Zn has no divisors of zero, except [0]n.
(3) Every nonzero element of Zn has a multiplicative inverse.
1.4.7. Definition. Let n be a positive integer. The number of positive integers less than or equal to n which are relatively prime to n will be denoted by (n). This function is called Euler's phi-function, or the totient function.
1.4.8. Proposition. If the prime factorization of n is n = p1m1 p2m2 � � � pnmn , then
(n) = n(1-1/p1)(1-1/p2) � � � (1-1/pk).
1.4.9. Definition. The set of units of Zn, the congruence classes [a]n, such that (a,n)=1, will be denoted by
Zn�.
The following theorem shows that raising any congruence class in Zn� to the power (n) yields the congruence class of 1. It is possible to give a purely number theoretic proof at this point, but in Example 3.2.12 there is a more elegant proof using elementary group theory.
1.4.11. Theorem. [Euler] If (a,n)=1, then a (n) 1 (mod n).
1.4.12 Corollary. [Fermat] If p is prime, then ap a (mod p), for any integer a.
2.1.1. Definition. Let S and T be sets. A function from S into T is a subset F of S � T such that for each element x S there is exactly one element y T such that (x,y) F. The set S is called the domain of the function, and the set T is called the codomain of the function.
The subset { y T | (x,y) F for some x S } of the codomain is called the image of the function.
Example 2.1.1. Let S = { 1,2,3 } and T = { u,v,w }.
The subsets
F1 = { (1,u), (2,v), (3,w) } and
F2 = { (1,u),(2,u),(3,u) }
of S � T both define functions since in both cases each element of S occurs exactly once among the ordered pairs. The subset
F3 = { (1,u),(3,w) }
does not define a function with domain S because the element 2 S does not appear as the first component of any ordered pair.
Note that F3 is a function if the domain is changed to the set { 1,3 }.
Unlike the conventions used in calculus, the domain and codomain must be specified as well as the ``rule of correspondence'' (list of pairs) when you are presenting a function. The subset
F4 = { (1,u),(2,u),(2,v),(3,w) }
does not define a function since 2 appears as the first component of two ordered pairs. When a candidate such as F4 fails to be a function in this way, we say that it is not ``well-defined.''
2.1.2. Definition. Let f:S->T and g:T->U be functions. The composition g � f of f and g is the function from S to U defined by the formula (g � f)(x) = g(f(x)) for all x S.
2.1.3. Proposition. Composition of functions is associative.
2.1.4. Definition. Let f:S->T be a function. Then f is said to map S onto T if for each element y T there exists an element x S with f(x) = y.
If f(x1) = f(x2) implies x1 = x2 for all elements x1, x2 S, then f is said to be a one-to-one function.
If f is both one-to-one and onto, then it is called a one-to-one correspondence from S to T.
2.1.5. Proposition. Let f:S->T be a function. Suppose that S and T are finite sets with the same number of elements. Then f is one-to-one if and only if it is onto.
2.1.6. Proposition. Let f:S->T and g:T->U be functions.
(a) If f and g are one-to-one, then g � f is one-to-one.
(b) If f and g are onto, then g � f is onto.
2.1.7. Definition. Let S be a set. The identity function 1S:S->S is defined by the formula
1S(x) = x for all x S.
If f:S->T is a function, then a function g:T->S is called an inverse for f if
g � f = 1S and f � g = 1T.
2.1.8. Proposition. Let f:S->T be a function. If f has an inverse, then it must be one-to-one and onto. Conversely, if f is one-to-one and onto, then it has a unique inverse.
2.2.1. Definition. Let S be a set. A subset R of S � S is called an equivalence relation on S if
(i) for all a S, (a,a) R;
(ii) for all a,b S, if (a,b) R then (b,a) R;
(iii) for all a,b,c S, if (a,b) R and (b,c) R, then (a,c) R.
We will write a b to denote the fact that (a,b) R.
2.2.2. Definition. Let be an equivalence relation on the set S. For a given element a S, we define the equivalence class of a to be the set of all elements of S that are equivalent to a.
We will use the notation [a]. In symbols,
[a] = { x S | x a }.
The notation S/ will be used for the collection of all equivalence classes of S under .
Example. (S/f) 2.2.2. Let f:S->T be any function. For x1, x2 S we define
x1 x2 if f(x1) = f(x2). Then for all x1, x2, x3 S we have
(i) f(x1) = f(x1);
(ii) if f(x1) = f(x2), then f(x2) = f(x1);
(iii) if f(x1) = f(x2) and f(x2) = f(x3), then f(x1) = f(x3).
This shows that we have defined an equivalence relation on the set S. The proof of this is easy because the equivalence relation is defined in terms of equality of the images f(x), and equality is the most elementary equivalence relation. The collection of all equivalence classes of S under will be denoted by S/f.
2.2.3. Proposition. Let S be a set, and let be an equivalence relation on S. Then each element of S belongs to exactly one of the equivalence classes of S determined by the relation .
2.2.4. Definition. Let S be any set. A family P of subsets of S is called a partition of S if each element of S belongs to exactly one of the members of P.
2.2.5. Proposition. Any partition P of a set S determines an equivalence relation.
2.2.6. Theorem. If f:S->T is any function, and is the equivalence relation defined on S by letting
x1 x2 if f(x1) = f(x2), for all x1, x2 S, then there is a one-to-one correspondence between the elements of the image f(S) of S under f and the equivalence classes S/f of the relation .
If f:S ->T is a function and y belongs to the image f(S), then the inverse image of y is
f -1(y) = { x S | f(x) = y } .
The inverse images of elements of f(S) are the equivalence classes in S/f. (Note carefully that we are not implying that f has an inverse function.)