Factors and multiples in the set of integers
Factors and multiples
Example: 6 is a factor of 18 and -6 is a factor of - 18 ( in those cases, t =3). Also, 6 is a factor of -18, and -6 is a factor of 18 (in those cases, t = -3).
For integers m, n, if a number t exists such that m × t = n, that t is unique. If for some t' occurs that m × t' = n, then m × t = m × t' and t = t', except if m = 0.
If m = 0, m × t = m × t' and it is not necessary that t = t'
For any integer n, 0 × n = 0. It can be stated that 0 is a factor of 0, even if n is not unique.
Also, n × 0 = 0. It can be stated that any integer n is a factor of 0.
In general, a is a factor of b means the same as, b is a multiple of a.
Examples: 7 is a factor of 21, and 21 is a multiple of 7;
5 is a factor of 0, and 0 is a multiple of 5.
0 is a factor of 0, and 0 is a multiple of 0
For any integer n, 1 is a factor of n, and n is a multiple of 1
Examples: 11 ≥ 7, -3 ≥ -12, 17 ≥ 17, 4 ≥ -5
If a and b are nonegative integers and a is a factor of b, then a ≤ b.
This is true, since a × k = b, means that a + a.(k - 1) = b
Examples:
6 is a factor of 18. In fact, 6 × 3 = 18; 6 + 6 × 2 = 18. Then, 6 ≤ 18.
13 is a factor of 13. In fact, 13 × 1 = 13; 13 + 13 × 0 = 13. Then, 13 ≤ 13
For integers m, n, if a number t exists such that m × t = n, that t is unique. If for some t' occurs that m × t' = n, then m × t = m × t' and t = t', except if m = 0.
If m = 0, m × t = m × t' and it is not necessary that t = t'
For any integer n, 0 × n = 0. It can be stated that 0 is a factor of 0, even if n is not unique.
Also, n × 0 = 0. It can be stated that any integer n is a factor of 0.
In general, a is a factor of b means the same as, b is a multiple of a.
Examples: 7 is a factor of 21, and 21 is a multiple of 7;
5 is a factor of 0, and 0 is a multiple of 5.
0 is a factor of 0, and 0 is a multiple of 0
For any integer n, 1 is a factor of n, and n is a multiple of 1
Order, factors and multiples
In the set of integers it is defined an order relation. If a and b are integers, to affirm that a is less or equal to b means that there is an integer k, positive or zero, such that a + k = b.
a is less or equal to b is symbolized a ≤ b
Examples:
7 ≤ 11, since 7 + 4 = 11.
-12 ≤ -3, since -12 + 9 = -3
17 ≤ 17, since 17 + 0 = 17
a is less or equal to b is equivalent to b is greater or equal to a, symbolized as b ≥ a.
Examples: 11 ≥ 7, -3 ≥ -12, 17 ≥ 17, 4 ≥ -5
If a and b are nonegative integers and a is a factor of b, then a ≤ b.
This is true, since a × k = b, means that a + a.(k - 1) = b
Examples:
6 is a factor of 18. In fact, 6 × 3 = 18; 6 + 6 × 2 = 18. Then, 6 ≤ 18.
13 is a factor of 13. In fact, 13 × 1 = 13; 13 + 13 × 0 = 13. Then, 13 ≤ 13
Multiples and quotients
If b is a multiple of a, then there is an integer k such that b = a × k . This number k is called the quotient between b and a. The number b is the dividend and the number a is the divisor. The corresponding operation is an exact division between b and a: b/a = k. Also b ÷ a = k.
Examples:
12/4 = 3, since 12 = 3 × 4
-35/7 = -5, since -35 = -5 × 7
56/-8 = -7, since 56 = (-7) × (-8)
In exact division operation,the divisor cannot be zero even if the dividend were zero.
The expression 0/a has arithmetical meaning, if a ≠ 0. (0 is multiple of any integer n)
0/a = 0, since 0 × a = 0
The expresion b/0, for b ≠ 0, has not arithmetical meaning as b/0 = k would mean k × 0 = b.
The expresion b/0, for b = 0, has not arithmetical meaning as 0/0 = k would be true for any integer k. The operation would give any integer as a result.
Examples:
0 ÷ 235 = 0
0 ÷ -75 = 0
3 ÷ 0 has not arithmetical meaning.
0 ÷ 0 has not arithmetical meaning.
Examples:
12/4 = 3, since 12 = 3 × 4
-35/7 = -5, since -35 = -5 × 7
56/-8 = -7, since 56 = (-7) × (-8)
In exact division operation,the divisor cannot be zero even if the dividend were zero.
The expression 0/a has arithmetical meaning, if a ≠ 0. (0 is multiple of any integer n)
0/a = 0, since 0 × a = 0
The expresion b/0, for b ≠ 0, has not arithmetical meaning as b/0 = k would mean k × 0 = b.
The expresion b/0, for b = 0, has not arithmetical meaning as 0/0 = k would be true for any integer k. The operation would give any integer as a result.
Examples:
0 ÷ 235 = 0
0 ÷ -75 = 0
3 ÷ 0 has not arithmetical meaning.
0 ÷ 0 has not arithmetical meaning.
Greatest common factor of two (or more) positive integers
The themes of gratest common factor (gcf) and least common multiple (lcm) have been relevant in number theory from antiquity. They can be found in Euclid's Elements.
gcf(a, b) = max[F(a) ∩ F(b)]
Example: For 432 and 388, F(432) = {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 36, 48, 54, 72, 108, 144, 216, 432}; F(388) = {1, 2, 4, 97, 194, 388}. F(a) ∩ F(b) = {1, 2, 4}. max[F(a) ∩ F(b)] = 4.
gcf(432, 388) = 4.
The concept of greatest common factor can be extended for more than two integers:
gcf(432, 388) = 4.
The concept of greatest common factor can be extended for more than two integers:
gcf (a1,
a2, a3, …, an) = max[
Example: For 270, 180, 306,
F(270) = {1, 2, 3, 5, 6, 9, 10, 15, 18, 27, 30, 45, 54, 90, 135, 270},
F(180) = {1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180},
F(306) = {1, 2, 3, 6, 9, 17, 18, 34, 51, 102, 153, 306}
F(270) ∩ F(180) ∩ F(306) = {1, 2, 3, 6, 9, 18}
max[F(270) ∩ F(180) ∩ F(306)] = 18
gtf(270, 180, 306) = 18
General division for positive integers
In above described exact division, b = a × k, where b is the dividend and a is the divisor. In this case, b - (a × k) = 0. To generalize the division operation for any pair of positive integers a, b, it is necessary to consider cases where b - (a × k) ≠ 0.
Let's consider the following example:
There are 168 eggs and 37 boxes. The eggs must be put in the boxes with the condition that each box will contain the same number of eggs. A way to do this can consist in putting one egg at a time in each box, verify that there are more eggs to put in the boxes, repeat the operation until possible, according with the given condition. Every share means to take 37 eggs from the pile. The following table describes the process.
share
|
result
|
rest
|
1
|
168 - 37
|
131
|
2
|
131 - 37
|
94
|
3
|
94 - 37
|
57
|
4
|
57 - 37
|
20
|
It can be seen that this process deals with searching the greatest multiple of 37 which is not greater than 168. In this case, 4 × 37 is the right multiple. For 5 × 37 = 185 is greater that the number of eggs in the pile.
To generalize the division operation, this example shows a case in which b - (a × k) ≠ 0.
The general situation is b - (a × k) = r where r ≥ 0 and r ⋖ b.
If r = 0, the situation is the same as that of exact division.
The following schemas show the more general situation of division between two positive integers b (dividend) , a (divisor). q is the quotient and r is the reminder or rest. Also is shown the particular eggs and boxes case.
Given two positive integers b, a. it is always possible to find one or more multiples of a not greater than b, The greatest of such multiples is the reminder of b divided by a.
Example: If b = 456 and a = 87, then multiples of 87 not greater than 456 are: 0, 87, 174, 261, 348, 435. The greatest of these multiples is 435 ( = 87 × 5).
Then the quotient is 5 and the reminder is 456 - 435 = 21.
Example: If b = 456 and a = 87, then multiples of 87 not greater than 456 are: 0, 87, 174, 261, 348, 435. The greatest of these multiples is 435 ( = 87 × 5).
Then the quotient is 5 and the reminder is 456 - 435 = 21.
Euclid's algorithm
The gcf (s, t) can be obtained using the precedent definition. However, this is not the best way to perform the operation.
The so called Euclid´s algorithm is a way to determine the gcf for two positive integers a, b. The use of this algorithm requires of a new definition of gcf(a, b), equivalent to the precedent.
The integer d is the greatest common factor of two positive integers a, b, if and only if,
(1) d is a common factor of a and b
(2) every common factor of a and b is a factor of d.
The condition (1) means that d is in the intersection set of F(a) and F(b).
The condition (2) means that every number in F(a) ∩ F(b) is a factor of d. This means that for each c in F(a) ∩ F(b), c is a factor of d. This implies that c ≤ d, for each c in F(a) ∩ F(b). Conclusion: d is the maximum of F(a) ∩ F(b).
The so called Euclid's algorithm reiterates the above general division schema as it can be seen in the following schema:
q1
|
q2
|
q3
|
q4
|
. . .
|
|
a
|
b
|
r1
|
r2
|
r3
|
. . .
|
r1
|
r2
|
r3
|
r4
|
. . .
|
Above schema corresponds to this process: performing the division between a (dividend) and b (divisor) it results the quotient q1 and the remainder r1. If r1 = 0 the process stops here. In this case, b is a factor of a and gcf(a, b) = b.
If r1 ≠ 0, perform the division between b and r1; it results the quotient q2 and the remainder r2. If r2 = 0, the process stops here: r1 is a factor of b and gcf(b, r1) = r1 .
If r2 ≠ 0, perform the division between r1 and r2 ; it results the quotient q3 and the remainder r3.
If r3 = 0, the process stops here: r1 is a factor of r2 and gcf(r1, r2) = r1 .
If r3 ≠ 0, ...
The following equalities can be written:
If r1 ≠ 0, perform the division between b and r1; it results the quotient q2 and the remainder r2. If r2 = 0, the process stops here: r1 is a factor of b and gcf(b, r1) = r1 .
If r2 ≠ 0, perform the division between r1 and r2 ; it results the quotient q3 and the remainder r3.
If r3 = 0, the process stops here: r1 is a factor of r2 and gcf(r1, r2) = r1 .
If r3 ≠ 0, ...
The following equalities can be written:
r1 = a - b q1
In each case of division the reminder is strictly less than the divisor : r1 ⋖ b, r2 ⋖ r1 , r3 ⋖ r2 , ...
The sequence b, r1, r2, r3, r4, … decreases and consequently rn has to be 0 for some value of n, as there is a minimum in every set of integers .
The sequence b, r1, r2, r3, r4, … decreases and consequently rn has to be 0 for some value of n, as there is a minimum in every set of integers .
For instance, if r4 = 0, then r2 = r3 q4¸ and this implies that r3 is a factor of r2.
As r3 = r1 – r2 q3, then r1 = r3 + r2 q3, and this implies that r3 is a factor of r1.
As r2 = b – r1 q2, then b = r2 + r1 q2, and this implies that r3 is a factor of b.
As r1 = a – b q1, then a = r1 + b q1, and this implies that r3 is a factor of a.
The first condition of gcf definition has been accomplished: r3 is a factor of a and b.
To examine if the second condition is accomplished too, let's suppose that h is a factor of a and b. In this case, h is a factor of r1, since r1 = a - b q1.
But, in this case, h is a factor of r2 too, since r2 = b – r1 q2.
In the same way it can be deduced that h is a factor of r3.
Conclusion: for r4 = 0, gcf(a, b) = r3.
This reasoning can be extended for the case in which rn = 0, for any positive integer n.
Example: Find gcf(72, 45)
Using the euclidean algorithm,
1
|
1
|
1
|
2
| |
72
|
45
|
27
|
18
|
9
|
27
|
18
|
9
|
0
|
Then gcf (72, 45) = 9
Relatively prime numbers
If gcf(a, b) = 1, then a and b are said to be relative primes.
Example: 12 and 35 are relative primes.
If gcf(a, b) = 1, then a and b are said to be relative primes.
Example: 12 and 35 are relative primes.
Linear combination and gcf
From a theorem, not proved here, if gcf(a, b) = d then there exist integers s, t, such that d = sa + tb.
As a corollary of this theorem, it holds that the equation gx + hy = 1 has integer solutions, if a/d = g, b/d = h.
As a corollary of this theorem, it holds that the equation gx + hy = 1 has integer solutions, if a/d = g, b/d = h.
Example: As it has seen, gcf(72, 45) = 9.
To determine integers x, y such that 72x + 45y = 9 will be used the program Mathematica, the one used above to obtain lists of factors.
The equation 72x + 45y = 9 is equivalent to 8x + 5y = 1. Here the program Mathematica will be used:
FindInstance[8 x + 5 y == 1, {x, y}, Integers] . The result is, x = 2, y = -3
Substituting in the original equation, (72)(2) + (45)(-3) = 9.
One more example: Find gcf(2210, 1365)
From Euclid algorithm, or from Mathematica , GCD[2210, 1365] = 65
The equation 2210x + 1365y = 65 is equivalent to 34x + 21y = 1
From the named program,
FindInstance[34 x + 21 y == 1, {x, y}, Integers] x = 13, y = -21
Verifying, (13)(2210) + (-21)(1365) = 65.
From Euclid algorithm, or from Mathematica , GCD[2210, 1365] = 65
The equation 2210x + 1365y = 65 is equivalent to 34x + 21y = 1
From the named program,
FindInstance[34 x + 21 y == 1, {x, y}, Integers] x = 13, y = -21
Verifying, (13)(2210) + (-21)(1365) = 65.
Relatively prime numbers
If gcf(a, b) = 1, then a and b are said to be relative primes.
Example: 12 and 35 are relative primes.
The following is a notable property:
If c is a factor of a.b and gcf (a, c) = 1 then c is a factor of b.
To justify this assertion, use the fact that gcf (a, c) = 1 means that a.s + c.t = 1 for some integers s, t.
Then, b.a.s + b.c.t = b. That is, c is a factor of b.
Example: 4 1s a factor of (12)(15). Then 4 is a factor of 12 since gcf (4, 15) = 1.
Least common multiple for two positive integers
In a similar way, the least common multiple between two numbers a, b, is the minumum of the intersection set between the set of multiples of a, M(a) and the set of multiples of b, M(b).
lcm(a, b) = min[M(a) ∩ M(b)]
It must be noted that in the set of multiples of an integer there are an infinite number of elements.
Example: For 6 and 8,
M(6) ={6, 12, 18, 24, 30, 36, 42, 48, 54, 60, ...};
M(8) = {8, 16, 24, 32, 40, 48, 56, 64, 72, ...}.
M(6) ∩ M(8) = {24, 48, ...}.
min[M(6) ∩ M(8)] = 24.
lcm(6, 8) = 24.
The concept of least common multiple can be extended for more than two integers:
lcm (a1, a2, a3, …, an) = min[
Example: for 6, 7 and 8,
M(2) = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ...}
M(3) = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...}
M(6) ={6, 12, 18, 24, 30, 36, 42, 48, 54, 60, ...};
M(2) ∩ M(3) ∩ M(6) = {6, 12, 18, ...}
min[M(2) ∩ M(3) ∩ M(6)] = 6
lcm(2, 3, 6) = 6
As in the case of gcf, the above described method to find the lcm of two or more integers is not the best .
The following is a useful definition for lcm (a, b):
m is the least common multiple of the integers a, b if and only if the following conditions are fulfilled:
(1) m is a common multiple of a and b.
(2) Every common multiple of a and b is multiple of m.
There is a useful property which links gcf and lcm for two integers a, b.
If d = gcf (a, b) then a = da’, b = db’, and gcf (a’, b’) =1. Otherwise, d wouldn't be gcf (a, b).
If gcf(a', b') = g then a' = gs, b' = gt. Then a = dgs and b = dgt. This implies that dg is a common factor of a and b and dg is grater than d which had to be the greatest.
Example:
gcf(72, 45) = 9; 72 = (9)(8), 45 = (9)(5); gtf (8, 5) = 1. Otherwise, 9 wouldn't be gcf (72, 45)
Given that d = gcf (a, b), a = da’, b = db’, let m = da'b'. Then m = ab’ and m = a’b. That is, m is a common multiple of a and b.
If k is another common multiple of a and b, then k = ha = tb. Then k = hda’ = tdb’.
It follows that ha’ = tb’. As gcf(a’, b’) = 1, and b' is a factor of ha', then b' is a factor of h and b'.s = h, for some integer s.
Replacing h in a former equation, b'.sa’ = tb’. And then, k = hda’ = b'sda' = sm. that is, k is a multiple of m.
Conclusion: m = da’b’ is the least common multiple of a, b.
From above equations, a = da’, b = db’ it follows that ab = da’db’ and ab/d = da’b’ = m.
Finally, ab = dm. That is, gcf (a, b) × lcm (a, b) = a × b.
Example: From above result, gcf (72, 45) = 9. Then, lcm(72, 45) = (72)(45)/9 = 360.
No hay comentarios:
Publicar un comentario