[go: up one dir, main page]

0% found this document useful (0 votes)
75 views55 pages

Discrete Mathematics (12) Number Theory

Uploaded by

jsenwj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
75 views55 pages

Discrete Mathematics (12) Number Theory

Uploaded by

jsenwj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 55

Course : MATH6025 – Discrete Mathematics

Effective Period : September 2020

Number Theory
Session 12
Acknowledgement

These slides have been adapted from :

Kenneth H. Rosen, “ Discrete


Mathematics and its Applications”,
8th edition,2019, McGraw-Hill
Education, New York, ISBN 978-1-
259-67651-2

Chapter 4

2
Learning Objectives

On successful completion of this course, students will be


able to:

LO 2
Explain Set Theory, Fuzzy Set,
Counting method, Number Theory
and its applications
Sub Topics

• Divisibility and Modular Arithmetic


1
• Primes and Greatest Common Divisors
2
• Solving Congruences
3
• Applications of Congruences
4

4
Divisibility and Modular Arithmetic

5
Introduction

❑ Division of an integer by a positive integer produces a


quotient and a remainder.
❑ Working with these remainders leads to modular
arithmetic, which plays an important role in
mathematics and which is used throughout computer
science.
❑ Some important applications of modular arithmetic
including generating pseudorandom numbers,
assigning computer memory locations to files,
constructing check digits, and encrypting messages

6
Division

Definition 1
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 (or equivalently, if ba is an integer). 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.

Example 1 :
Determine whether 3 ∣ 7 and whether 3 ∣ 12.
Solution:
3 ∤ 7, because 7∕3 is not an integer.
3 ∣ 12 because 12∕3 = 4.

7
Division

Example 02 :
Let n and d be positive integers. How many positive integers not
exceeding n are divisible by d?

Solution:
The positive integers divisible by d are all the integers of the form dk,
where k is a positive integer.
Hence, the number of positive integers divisible by d that do not exceed n
equals the number of integers k with 0 < dk ≤ n, or with 0 < k ≤ n∕d.
Therefore, there are ⌊n∕d⌋ positive integers not exceeding n that are
divisible by d.

8
Division

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.

Integers divisible by the positive integer d.

9
Division

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.

10
The Division Algorithm

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.

Definition 2
In the equality given in the division algorithm, d is called the divisor, a is
called the dividend, q is called the quotient, and r is called the remainder.
This notation is used to express the quotient and remainder:
q = a div d, r = a mod d.

11
The Division Algorithm

Example 1:
What are the quotient and remainder when 11 is divided by 11?

Solution:
We have 11 = 11 ⋅ 9 + 2.
Hence, the quotient when 11 is divided by 11 is
9 = 11 div 11,
and the remainder is
2 = 11 mod 11.

12
Modular Arithmetic

Definition 3:
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.

13
Modular Arithmetic

Example :
Determine whether 17 is congruent to 5 modulo 6 and whether 24 and 14
are congruent modulo 6.

Solution:
Because 6 divides 17 − 5 = 12, we see that 17 ≡ 5 (mod 6).
However, because 24 − 14 = 10 is not divisible by 6,
we see that 24 ≢ 14 (mod 6).

14
Modular Arithmetic

Theorem 4
Let m be a positive integer. The integers a and b are congruent modulo
m if and only if there is an integer k such that a = b + km.

Proof:
If a ≡ b (mod m), we know that m ∣ (a − b).
There is an integer k such that a − b = km, so that a = b + km.
Conversely, if there is an integer k such that a = b + km, then km = a − b.
Hence, m divides a − b, so that a ≡ b (mod m).

15
Modular Arithmetic

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).

Proof: Example :
We use a direct proof. Because 7 ≡ 2 (mod 5)
Because a ≡ b (mod m) and c ≡ d (mod m), and 11 ≡ 1 (mod 5), it
are integers s and t with b = a + sm and d = c + follows from Theorem
tm. 5 that
Hence, 18 = 7 + 11 ≡ 2 + 1
b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) =3 (mod 5)
and and that
bd = (a + sm)(c + tm) = ac + m(at + cs + stm). 77 = 7 ⋅ 11 ≡ 2 ⋅ 1 = 2
Hence, (mod 5).
a + c ≡ b + d (mod m) and ac ≡ bd (mod m).
16
Modular Arithmetic

Corollary 2
Let m be a positive integer and let a and b be integers. Then
(a + b) modm = ((a modm) + (b modm)) modm
and
ab modm = ((a modm)(b modm)) modm.

Proof:
By the definitions of modm and of congruence modulo m, we know that
a ≡(a modm) (modm) and b ≡ (b modm) (modm).
Hence, Theorem 5 tells us that
a + b ≡ (a modm) + (b modm) (modm)
and
ab ≡ (a modm)(b modm) (modm).
The equalities in this corollary follow from these last two congruences by Theorem 3.
17
Modular Arithmetic

Example:
Find the value of (193 mod 31)4 mod 23.

Solution:
First evaluate 193 mod 31. Because 193 = 6859 and 6859 = 221 ⋅ 31 + 8,
we have 193 mod 31 = 6859 mod 31 = 8.
So, (193 mod 31)4 mod 23 = 84 mod 23.
Next, note that 84 = 4096.
Because 4096 = 178 ⋅ 23 + 2,
we have 4096 mod 23 = 2.
Hence,
(193 mod 31)4 mod 23 = 2.

18
Primes and Greatest Common
Divisors

19
Primes

Definition 1
An integer p greater than 1 is called prime if the only positive factors of p
are 1 and p. A positive integer that is greater than 1 and is not prime is
called composite.

Example :
The integer 7 is prime because its only positive factors are 1 and 7,
whereas the integer 9 is composite because it is divisible by 3.

20
Primes

Theorem 1 .
The Fundamental Theorem Of Arithmetic
Every integer greater than 1 can be written uniquely as a prime or as the
product of two or more primes, where the prime factors are written in
order of nondecreasing size

Example :
The prime factorizations of 100, 641, 999, and 1024 are given by
100 = 2 ⋅ 2 ⋅ 5 ⋅ 5 = 22 . 52 ,
641 = 641,
999 = 3 ⋅ 3 ⋅ 3 ⋅ 37 = 33 . 37 ,
1024 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 210 .

21
Trial Division

Theorem 2
If n is a composite integer, then n has a prime divisor less than or equal to
√n.
Proof:
If n is composite, by the definition of a composite integer, we know that it
has a factor a with 1 < a < n.
Hence, by the definition of a factor of a positive integer, we have n = ab,
where b is a positive integer greater than 1.
We will show that a ≤√n or b ≤√n. If a >√n and b >√n, then ab >√n ⋅
√n = n, which is a contradiction.
Consequently, a ≤√n orb ≤√n. Because both a and b are divisors of n, we
see that n has a positive divisor not exceeding √n.
This divisor is either prime or, by the fundamental theorem of arithmetic,
has a prime divisor less than itself. In either case, n has a prime divisor less
than or equal to √n.

22
Trial Division

Example :
Show that 101 is prime.

Solution:
The only primes not exceeding √101 are 2, 3, 5, and 7.
Because 101 is not divisible by 2, 3, 5, or 7
(the quotient of 101 and each of these integers is not an integer),
it follows that 101 is prime.

23
THE DISTRIBUTION OF PRIMES

Theroem 4.
Theprimenumbertheorem. The ratio of 𝜋(x), the number of primes not
exceeding x, and x ∕ ln x approaches 1 as x grows without bound.
(Here ln x is the natural logarithm of x.)

Approximating 𝝅(x) by x /𝐥𝐧 x.


24
Greatest Common Divisors and Least
Common Multiples

Definition 2
Let a and b be integers, not both zero. The largest integer d such that d ∣ a
and d ∣ b is called the greatest common divisor of a and b. The greatest
common divisor of a and b is denoted by gcd(a, b).

Example :
What is the greatest common divisor of 24 and 36?

Solution:

The positive common divisors of 24 and 36 are 1, 2, 3, 4, 6, and 12.


Hence, gcd(24, 36) = 12.

25
Greatest Common Divisors and Least
Common Multiples

Definition 3
The integers a and b are relatively prime if their greatest common divisor
is 1.
Example :
The integers 17 and 22 have no positive common divisors other than 1,
so that gcd(17, 22) = 1.
Hence that the integers 17 and 22 are relatively prime.

26
Greatest Common Divisors and Least
Common Multiples

Definition 4
The integers a1, a2,…, an are pairwise relatively prime if gcd(ai, aj) = 1
whenever 1 ≤ i <j ≤ n.

Example :
Determine whether the following integers are pairwise relatively prime
a. 10, 17, and 21
b. 10, 19, and 24

Solution:
a. Because gcd(10, 17) = 1, gcd(10, 21) = 1, and gcd(17, 21) = 1, we
conclude that 10,17, and 21 are pairwise relatively prime.
b. Because gcd(10, 24) = 2 > 1, we see that 10, 19, and 24 are not pairwise
relatively prime.

27
Greatest Common Divisors and Least
Common Multiples

Definition 5 :
The least common multiple of the positive integers a and b is the
smallest positive integer that is divisible by both a and b. The least
common multiple of a and b is denoted by lcm(a, b).

Example :
What is the least common multiple of 23 35 72 and 24 33
Solution:
We have
lcm(23 35 72 , 24 33 ) = 2max(3, 4) 3max(5, 3) 7max(2, 0) . = 243572.

Theorem 5
Let a and b be positive integers. Then ab = gcd(a, b) ⋅ lcm(a, b).

28
The Euclidean Algorithm

Lemma 1
Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r).

Proof:
If we can show that the common divisors of a and b are the same as the
common divisors of b and r, we will have shown that gcd(a, b) = gcd(b, r),
because both pairs must have the same greatest common divisor.
So suppose that d divides both a and b. Then it follows that d also
divides
a − bq = r .
Hence, any common divisor of a and b is also a common divisor of b and
r.
Likewise, suppose that d divides both b and r. Then d also divides bq + r
= a. Hence, any common divisor of b and r is also a common divisor of29a
The Euclidean Algorithm

Suppose that a and b are positive integers with a ≥ b. Let r0 = a and r1 = b. apply
the division algorithm, we obtain
r0 = r1 q1 + r2 0 ≤ r2 < r1,
r1 = r2 q2 + r3 0 ≤ r3 < r2,
⋅⋅⋅
rn−2 = rn−1qn−1 + rn 0 ≤ rn < rn−1,
rn−1 = rn qn.

Furthermore,
it follows from Lemma 1 that
gcd(a, b) = gcd(r0, r1) = gcd(r1, r2) = ⋯ = gcd(rn−2, rn−1)
= gcd(rn−1, rn) = gcd (rn, 0) = rn.

30
The Euclidean Algorithm

Example :
Find the greatest common divisor of 414 and 662 using the Euclidean
algorithm.

Solution:
Successive uses of the division algorithm give:
662 = 414 ⋅ 1 + 248
414 = 248 ⋅ 1 + 166
248 = 166 ⋅ 1 + 82
166 = 82 ⋅ 2 + 2
82 = 2 ⋅ 41.
Hence, gcd(414, 662) = 2, because 2 is the last nonzero remainder.

31
The Euclidean Algorithm

Pseudocode The Euclidean Algorithm

32
gcds as Linear Combinations

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 B´ezout, a French mathematician of the eighteenth
century). Also, the equation gcd(a, b) = sa + tb is called Bezout’s identity.

Example :
Express gcd(252, 198) = 18 as a linear combination of 252 and 198 by
working backwards through the steps of the Euclidean algorithm.

33
gcds as Linear Combinations

Solution:

To show that gcd(252, 198) = 18, the Euclidean algorithm uses these
divisions:
252 = 198 ⋅ 1 + 54
198 = 54 ⋅ 3 + 36
54 = 36 ⋅ 1 + 18
36 = 18 ⋅ 2 + 0.
We find that
18 = 54 − 1 ⋅ 36.
The second division tells us that
36 = 198 − 3 ⋅ 54.
18 = 54 − 1 ⋅ 36 = 54 − 1 ⋅ (198 − 3 ⋅ 54) = 4 ⋅ 54 − 1 ⋅ 198.
54 = 252 − 1 ⋅ 198.
18 = 4 ⋅ (252 − 1 ⋅ 198) − 1 ⋅ 198 = 4 ⋅ 252 − 5 ⋅ 198,
completing the solution.
34
gcds as Linear Combinations

Lemma 2
If a, b, and c are positive integers such that gcd(a, b) = 1 and a ∣ bc, then a ∣
c.

Proof:
Because gcd(a, b) =1, by Bezout’s theorem there are integers s and t such
that sa + tb = 1.
Multiplying both sides of this equation by c, we obtain sac + tbc = c.
By part (ii ) of that theorem, a ∣ tbc.
Because a ∣ sac and a ∣ tbc, by part (i ) of that theorem, we conclude that a
divides sac + tbc.
Because sac + tbc = c, we conclude that a ∣ c.

35
gcds as Linear Combinations

Lemma 3
If p is a prime and p ∣ a1a2⋯an, where each ai is an integer, then p ∣ ai
for some i.

Theorem 7 :
Let m be a positive integer and let a, b, and c be integers. If ac ≡ bc (mod
m) and
gcd(c,m) = 1, then a ≡ b (mod m).

Proof:
Because ac ≡ bc (mod m),m ∣ ac − bc = c(a − b). By Lemma 2, because
gcd(c,m) = 1, it follows that m ∣ a − b. We conclude that a ≡ b (mod m).

36
Solving Congruences

37
Linear Congruences

Linear congruence : a congruence of the form ax ≡ b (mod m), where m


is a
positive integer, a and b are integers, and x is a variable.
Theorem 1
If a and m are relatively prime integers and m > 1, then an inverse of a
modulo m exists. Furthermore, this inverse is unique modulo m. (That is,
there is a unique positive integer 𝑎ത less than m that is an inverse of a
modulo m and every other inverse of 𝑎ത modulo m is congruent to a
modulo m.)
Example 1 :
Find an inverse of 3 modulo 7 by first finding Bezout coefficients of 3 and
7. (Note that we have already shown that 5 is an inverse of 3 modulo 7 by
inspection.)

38
Linear Congruences

Solution:
Because gcd(3, 7) = 1, Theorem 1 tells us that an inverse of 3 modulo 7
exists. The Euclidean algorithm ends quickly when used to find the
greatest common divisor of 3 and 7:
7 = 2 ⋅ 3 + 1.
From this equation we see that
−2 ⋅ 3 + 1 ⋅ 7 = 1.
This shows that −2 and 1 are Bezout coefficients of 3 and 7.
We see that −2 is an inverse of 3 modulo 7.
Note that every integer congruent to −2 modulo 7 is also an inverse of 3,
such as 5, −9, 12, and so on.

39
Linear Congruences

Example 2
What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?

Solution:
By Example 1 we know that −2 is an inverse of 3 modulo 7.
Multiplying both sides of the congruence by −2 shows that
−2 ⋅ 3x ≡ −2 ⋅ 4 (mod 7).
Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7),
it follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7).
Assume that x ≡6 (mod 7).
Then, 3x ≡ 3 ⋅ 6 = 18 ≡ 4 (mod 7),
which shows that all such x satisfy the congruence.
We conclude that the solutions to the congruence are the integers x
such that x ≡ 6 (mod 7), namely, 6, 13, 20,… and −1, −8, −15,….
40
Fermat’s Little Theorem

Fermat’s Little Theorem


If p is prime and a is an integer not divisible by p, then
𝑎𝑝−1 ≡ 1 (mod p).
Furthermore, for every integer a we have
𝑎𝑝 ≡ a (mod p).

Example : Find 7222 mod 11.


Solution:
By Fermat’s little theorem we know that
710 ≡ 1 (mod 11),
so (710 )𝑘 ≡ 1 (mod 11) for every positive integer k.
To take advantage of this last congruence, we divide the exponent 222 by
10, finding that 222=22⋅10+2. We now see that
7222 = 722.10+2 = (710 )22 .72 ≡ (1)22 ⋅ 49 ≡ 5 (mod 11).
It follows that 7222 mod 11 = 5.
41
Pseudoprimes

Definisi 1
Let b be a positive integer. If n is a composite positive integer, and
𝑏 𝑛−1 ≡ 1 (mod n), then n is called a pseudoprime to the base b.

Definition 2
A composite integer n that satisfies the congruence 𝑏 𝑛−1 ≡ 1 (mod n) for
all positive integers b with gcd(b, n) = 1 is called a Carmichael number.
(These numbers are named after Robert Carmichael, who studied them
in the early twentieth century.)
42
Pseudoprimes

Example :
The integer 561 is a Carmichael number. Because
first 561 is composite because 561 = 3 ⋅ 11 ⋅ 17.
if gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) =gcd(b, 17) = 1.

Using Fermat’s little theorem we find that


𝑏2 ≡ 1 (mod 3), 𝑏10 ≡ 1 (mod 11), and 𝑏16 ≡ 1 (mod 17).
It follows that
𝑏560 =(𝑏 2 )280 ≡ 1 (mod 3),
𝑏560 = (𝑏10 )56 ≡ 1 (mod 11),
𝑏560 = (𝑏16 )35 ≡ 1 (mod 17).

it follows that 𝑏 560 ≡ 1 (mod 561) for all positive integers b with
gcd(b, 561) = 1. Hence, 561 is a Carmichael number.
43
Applications of Congruences

44
Applications of Congruences

➢ Congruences have many applications to discrete


mathematics, computer science, and many other
disciplines.
➢ Three applications in this section:
1. The use of congruences to assign memory
locations to computer files,
2. The generation of pseudorandom numbers, and
3. Check digits.

45
1. Hashing Functions

❑ The central computer at an insurance company maintains records for


each of its customers.
❑ Records are identified using a key, which uniquely identifies each
customer’s records. For instance, customer records are often identified
using the Social Security number of the customer as the key.
❑ A hashing function h assigns memory location h(k) to the record that has
k as its key.

The hashing function h(k) = k mod m, where m is the number of


available memory locations

❑ a hashing function is not one-to-one, more than one file may be


assigned to a memory location. When this happens, we say that a
collision occurs. One way to resolve a collision is to assign the first free
location following the occupied memory location assigned by the
hashing function.
46
1. Hashing Functions

Example :
Find the memory locations assigned by the hashing function h(k) = k mod
111 to the records of customers with Social Security numbers
a. 064212848
b. 107405723.

Solution:
a. The record of the customer with Social Security number 064212848 is
assigned to memory location 14, because
h(064212848) = 064212848 mod 111 = 14.
b. h(107405723) = 107405723 mod 111 = 14,
This location is already occupied (answer a) . But, because memory
location 15, the first location following memory location 14, is free, we
assign the record of the customer with Social Security number
107405723 to this location.
47
2. Pseudorandom Numbers

❑ Randomly chosen numbers are often needed for computer


simulations.
❑ Pseudorandom numbers : numbers generated by systematic
methods are not truly random,
❑ The most commonly used procedure for generating pseudorandom
numbers is the linear congruential method. We choose four
integers: the modulus m, multiplier a, increment c, and seed x0,
with 2 ≤ a < m,
0 ≤ generate
We c < m, anda 0sequence
≤ x0 < m of pseudorandom numbers {xn}, with 0 ≤ xn
< m for all n, by successively using the recursively defined function
xn+1 = (axn + c) mod m.

❑ Many computer experiments require the generation of pseudorandom numbers between


0 and 1. To generate such numbers, we use the numbers xn∕m.
48
2. Pseudorandom Numbers

Example :
Find the sequence of pseudorandom numbers generated by the linear
congruential method with modulus m = 9, multiplier a = 7, increment c =
4, and seed x0 = 3.

Solution:
We compute the terms of this sequence by successively using the
recursively defined function xn+1 = (7xn + 4) mod 9,
beginning by inserting the seed x0 = 3 to find x1. We find that
x1 = 7x0 + 4 mod 9 = 7 ⋅ 3 + 4 mod 9 = 25 mod 9 = 7,
x2 = 7x1 + 4 mod 9 = 7 ⋅ 7 + 4 mod 9 = 53 mod 9 = 8,
x3 = 7x2 + 4 mod 9 = 7 ⋅ 8 + 4 mod 9 = 60 mod 9 = 6,
x4 = 7x3 + 4 mod 9 = 7 ⋅ 6 + 4 mod 9 = 46 mod 9 = 1,
x5 = 7x4 + 4 mod 9 = 7 ⋅ 1 + 4 mod 9 = 11 mod 9 = 2,

49
2. Pseudorandom Numbers

Solution :
x6 = 7x5 + 4 mod 9 = 7 ⋅ 2 + 4 mod 9 = 18 mod 9 = 0,
x7 = 7x6 + 4 mod 9 = 7 ⋅ 0 + 4 mod 9 = 4 mod 9 = 4,
x8 = 7x7 + 4 mod 9 = 7 ⋅ 4 + 4 mod 9 = 32 mod 9 = 5,
x9 = 7x8 + 4 mod 9 = 7 ⋅ 5 + 4 mod 9 = 39 mod 9 = 3.

Because x9 = x0 and because each term depends only on the previous


term, we see that the sequence
3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3,…
is generated.
This sequence contains nine different numbers before repeating.

50
Check Digits

❖ Congruences are used to check for errors in digit strings.


❖ A common technique for detecting errors in such strings is to add an
extra digit at the end of the string.
❖ This final digit, or check digit, is calculated using a particular function.
Then, to determine whether a digit string is correct, a check is made
to see whether this final digit has the correct value

51
Check Digits

Example :
Retail products are identified by their Universal Product Codes (UPCs).
The most common form of a UPC has 12 decimal digits: the first digit
identifies the product category, the next five digits identify the
manufacturer, the following five identify the particular product, and the
last digit is a check digit. The check digit is determined by the
congruence
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10 + 3x11 + x12
≡ 0 (mod 10).

Answer these questions:


(a) Suppose that the first 11 digits of a UPC are 79357343104. What is
the check digit?
(b) Is 041331021641 a valid UPC?

52
Check Digits

Solution:
(a) We insert the digits of 79357343104 into the congruence for UPC
check digits. This gives
3 ⋅ 7 + 9 + 3 ⋅ 3 + 5 + 3 ⋅ 7 + 3 + 3 ⋅ 4 + 3 + 3 ⋅ 1 + 0 + 3 ⋅ 4 + x12
≡ 0(mod 10).
Simplifying, we have
21 + 9 + 9 + 5 + 21 + 3 + 12 + 3 + 3 + 0 + 12 + x12 ≡ 0 (mod 10).
Hence, 98 + x12 ≡ 0 (mod 10).
It follows that x12 ≡ 2 (mod 10),
so the check digit is 2.
(b) To check whether 041331021641 is valid, we insert the digits into the
congruence these digits must satisfy. This gives
3⋅0+4+3⋅1+3+3⋅3+1+3⋅0+2+3⋅1+6+3⋅4+1
≡ 0 + 4 + 3 + 3 + 9 + 1 + 0 + 2 + 3 + 6 + 12 + 1 ≡ 4 ≢ 0 (mod 10).
Hence, 041331021641 is not a valid UPC.
53
Reference

Kenneth H. Rosen, “ Discrete Mathematics and its


Applications”, 8th edition,219, McGraw-Hill
Education, New York, ISBN 978-1-259-67651-2

54
Thank You

You might also like