Unit 1 notes
Discrete Mathematics 8 t h Edition
4.1
THEOREM 1:
Let a, b, and c be integers, where a ≠ 0. Then:
i. If a ∣ b and a ∣ c, then a ∣ (b + c);
ii. If a ∣ b, then a ∣ bc for all integers c;
iii. If a ∣ b and b ∣ c, then a ∣ c.
Then,
Direct proof of (i): Suppose that a ∣ b and a ∣ c. Then, from the definition of divisibility, it follows that
there are integers s and t with b = as and c = at. Hence,
b + c = as + at = a(s + t).
Therefore, a divides b + c. This establishes part (i) of the theorem.
COROLLARY: 1 If a, b, and c are integers, where a ≠ 0, such that a ∣ b and a ∣ c, then a ∣ mb + nc
whenever m and n are integers.
Proof: We will give a direct proof. By part (ii) of Theorem 1 we see that a ∣ mb and a ∣ nc whenever m
and n are integers. By part (i) of Theorem 1 it follows that a ∣ mb + nc.
THEOREM 2 THE DIVISION ALGORITHM:
Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 ≤ r < d, such
that a = dq + r.
4.1.4 Modular Arithmetic
What are the quotient and remainder when −11 is divided by 3?
Solution: We have
−11 = 3(−4) + 1.
Hence, the quotient when −11 is divided by 3 is −4 = −11 div 3, and the remainder is
1 = −11 mod 3.
Note that the remainder cannot be negative. Consequently, the remainder is not −2, even though
−11 = 3(−3) − 2,
because r = −2 does not satisfy 0 ≤ r < 3.
This number line shows the
remainders of dividing by 4.
2 is congruent to 6(mod 4) if the remainders are the same. The easy way to find this is by finding the
difference between 6 and 2 and dividing it by 4. If it is divisible it is congruent.
Textbook Definition:
If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a − b.
We use the notation a ≡ b (mod m) to indicate that a is congruent to b modulo m. We say that a ≡ b
(mod m) is a congruence and that m is its modulus (plural moduli). If a and b are not congruent modulo
m, we write a ≢ b (mod m).
THEOREM 3
Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only if
a mod m = b mod m.
This is simply saying, if the remainders are equal, then they are congruent.
Therefore 2 is congruent to 6(mod 4).
THEOREM 4
Let m be a positive integer. The integers a and b are congruent modulo m, (a ≡ b (mod m)); if and only if
there is an integer k such that a = b + km.
Proof:
Definition of Congruence: If a and b are integers and m is a positive integer, then a is congruent to b
modulo m if m divides a – b.
Then by definition of congruence m|(a − b)
Then a-b =km for some k ∈ Z. We know this by definition of divisibility below:
DEFINITION OF DIVISIBILITY:
If a and b are integers with a ≠ 0, we say that a divides b if there is an integer c such that b = ac. When a
divides b we say that a is a factor or divisor of b, and that b is a multiple of a. The notation a|b denotes
that a divides b. We write a ̸| b when a does not divide b.
We can then add b to a-b = km.
This allows us to prove there is an integer k such that a = b + km.
THEOREM 5
Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m),
then a + c ≡ b + d (mod m)
and ac ≡ bd (mod m).
4.3.8 GCDs as Linear Combinations
An important result we will use throughout the remainder of this section is that the greatest common
divisor of two integers a and b can be expressed in the form
sa+tb ,where s and t are integers. In other words, gcd (a , b) can be expressed as a linear combination
with integer coefficients of a and b . For example, gcd (6 , 14)=2 , and 2=(−2)⋅6 +1⋅14 . We state this
fact as Theorem 6.
THEOREM 6 BEZOUT’S THEOREM
If a and b are positive integers, then there exist integers s and t such that, gcd (a , b)=sa+tb .
Definition 6: If a and b are positive integers, then integers s and t such that gcd (a , b)=sa+tb are
called Bezout coefficients of a and b (after Etienne Bezout, a French mathematician of the eighteenth
century). Also, the equation gcd (a , b)=sa+tb is called Bezout’s identity.
