Discrete Math for Computer Science  Assignment # 3

CS201: Discrete Math for Computer Science
 Assignment # 3

Q.1 What are the prime factorizations of
(a) 511
(b) 8085
(c) 12!
Q.2
(a) Use Euclidean algorithm to find gcd(267, 79).
(b) Find integers s and t such that gcd(267, 79) = 79s + 267t.
(c) Use Euclidean algorithm to find gcd(561, 234).
(d) Find integers s and t such that gcd(561, 234) = 234s + 561t.
Q.3 Prove the following statements.
(a) If c|(a · b), then c|(a · gcd(b, c)).
(b) Suppose that gcd(a, y) = d1 and gcd(b, y) = d2. Prove that
gcd(gcd(a, b), y) = gcd(d1, d2).
(c) Suppose that gcd(b, a) = 1. Prove that gcd(b + a, b − a) ≤ 2.
Q.4
(a) State Fermat’s little theorem.
(b) Show that Fermat’s little theorem does not hold if p is not prime.
(c) Computer 302302 (mod 11), 47625367 (mod 13), 239674 (mod 523).
1
Q.5 Given an integer a, we say that a number n passes the “Fermat primality
test (for base a)” if a
n−1 ≡ 1 (mod n).
(a) For a = 2, does n = 561 pass the test?
(b) Did the test give the correct answer in this case?
Q.6 Solve the following modular equations.
(a) 267x ≡ 3 (mod 79).
(b) 778x ≡ 10 (mod 379).
(c) 312x ≡ 3 (mod 97).
Q.7 Let a and b be positive integers. Show that gcd(a, b) + lcm(a, b) = a + b
if and only if a divides b, or b divides a.
Q.8 Prove that if a and m are positive integer such that gcd(a, m) = 1 then
the function
f : {0, . . . , m − 1} → {0, . . . , m − 1}
defined by
f(x) = (a · x) mod m
is a bijection.
Q.9∗ Prove that if a and m are positive integers such that gcd(a, m) 6= 1 then
a does not have an inverse modulo m.
Q.10∗ Prove that if m is a positive integer of the form 4k + 3 for some nonnegative integer k, then m is not the sum of the squares of two integers.
Q.11 Find counterexamples to each of these statements about congruences.
(a) If ac ≡ bc (mod m), where a, b, c, and m are integers with m ≥ 2, then
a ≡ b (mod m).
(b) If a ≡ b (mod m) and c ≡ d (mod m), where a, b, c, d, and m are
integers with c and d positive and m ≥ 2, then a
c ≡ b
d
(mod m).
2
Q.12 Convert the decimal expansion of each of these integers to a binary
expansion.
(a) 321 (b) 1023 (c) 100632
Q.13 Show that log2 3 is an irrational number. Recall that an irrational
number is a real number x cannot be written as the ratio of two integers.
Q.14 Prove that there are infinitely many primes of the form 4k + 3, where
k is a nonnegative integer. [Hint: Suppose that there are only finitely many
such primes q1, q2, . . . , qn, and consider the number 4q1q2 · · · qn − 1.]
Q.15 Solve the system of congruence x ≡ 3 (mod 6) and x ≡ 4 (mod 7)
using the methods of Chinese Remainder Theorem or back substitution.
Q.16 Find all solutions, if any, to the system of congruences x ≡ 5 (mod 6),
x ≡ 3 (mod 10), and x ≡ 8 (mod 15).
Q.17 Show that we can easily factor n when we know that n is the product
of two primes, p and q, and we know the value of (p − 1)(q − 1).
3