DISCRETE MATH EXAM QUESTIONS
WITH CORRECT DETAILED ANSWERS
Relatively Prime - Answer-Two integers a and b are said to be relatively prime if
gcd(a,b) = 1.
Lemma 3.1 - Answer-If a, b , q and r are integers, and a = bq + r, then gcd(a,b) =
gcd(b,r).
Euclidean Algorithm - Answer-Used to find the greatest common divisor of a and b. It is
the last nonzero number.
Theorem 3.6 - Answer-If a and b are positive integers, then gcd(a,b) can be written as
an integral linear combination of a and b. in other words, tehre exists integers s and t
such that gcd(a,b) = sa + tb.
a modulo n (a mod n) - Answer-If n is a positive integer and a is any integer, then the
remainder we get when using the division algorithm to divide a by n is calld a modulo n.
and is denoted a mod n
Congruent modulo n - Answer-Let n be a positive integer. Two integers a and b are said
to be congruent modulo n if n | (b - a). We write a ≡ b (mod n) to denote a is congruent
to b modulo n, and write a ≠ b (mod n) to indicate that this is not the case.
Congruence Modulo n. - Answer-Let n be a positive integer, and a and b any integers.
Then a ≡ b (mod n) if and only if the leave the same remainder when divided by n using
the division algorithm, that is if and only if
a mod n = b mod n.
Properties of Modular Arithmetic - Answer-Let a, b, c, d, and n be integers with n > 1,
and suppose a ≡ b (mod n) and c ≡ d (mod n). Then,
1) (a + c) ≡ (b + d) ( mod n)
2) (a - c) ≡ ( b - d) ( mod n)
3) ac ≡ bd (mod n)
Inverse of a modulo n. - Answer-If a is an integer and ā a ≡ 1( mod n), then we say ā isan
inverse of a modulo n.
Codomain - Answer-Let f : A → B be a function from A to B. The set B is called the
codomain of f.
, Chinese Remainder Theorem - Answer-Suppose n1,n2, ... ,nk are integers which are
pairwise relatively prime. Then for any integers a1, a2,... ,ak, there is a solution x to the
system of equations
x ≡ a1 (mod n1)
x≡ a2(mod n2).......
x≡ ak(mod nk)
x = a1• N1•x1 + a2•N1•xd mod N
where,
N = n1•n2
N1= N/n1
N2=N/n2
x1= inverse of N1 mod n1
x2 = inverse of N2 mod n2
Divides - Answer-If a and b are integers and there is an integer c such that b = a • c,
then we say a divides b or b is divisible by a, and write a|b. In this case, we say that a is
a factor or divisor of b and that b is a multiple of a. If a does not divide b, we write a ł b.
Properties of Divisibility - Answer-For all integers a, b and c, the following properties
hold.
1) If a | b and b | c, then a | c
2) if a | b and a | c, then a | ( b + c)
3) if a | b, then a | bc
Corollary 3.1 - Answer-If a, b and c are integers, and a | b and a | c, then for any
integers m and n, a | ( mb + nc),
Prime Number - Answer-A prime Number is an integer greater than 1 whose only
positive divisors are 1 and itself. An integer greater than 1 that is not prime is called a
composite number.
Test for Primality - Answer-If n is a compiste number, then n has a prime divisor that is
less than or equal to √n.
The Division Algorithm - Answer-Given any integer a and positive integer d, there exists
unique integers q and r such that
a = dq + r with 0 ≤ r < d.
Greatest Common Divisor - Answer-Let a and b be integers that are not both 0. The
greatest common divisor of a and b, denoted gcd(a,b), is the largest integer d such that
d | a and d | b.
