[SOLVED] Cs215: discrete math (h) written assignment # 3

Q.1 What are the prime factorizations of
(a) 8085
(b) 10!
Q.3 For three integers a, b, y, suppose that gcd(a, y) = d1 and gcd(b, y) = d2.
Prove that
gcd(gcd(a, b), y) = gcd(d1, d2).
Q.4 Prove the following statement. If c|(a · b), then c|(a · gcd(b, c)).
Q.5 Solve the following modular equation.
312x ≡ 3 (mod 97).
Q.6 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).
Q.7 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.8 Convert the decimal expansion of each of these integers to a binary
expansion.
(a) 231 (b) 4532
1
Q.9 Let the coefficients of the polynomial f(n) = a0 + a1n + a2n
2 + · · · +
at−1n
t−1+n
t be integers. We now show that no non-constant polynomial can
generate only prime numbers for integers n. In particular, let c = f(0) = a0
be the constant term of f.
(1) Show that f(cm) is a multiple of c for all m ∈ Z.
(2) Show that if f is non-constant and c > 1, then as n ranges over the
nonnegative integers N, there are infinitely many f(n) ∈ Z that are
not primes. [Hint: You may assume the fact that the magnitude of any
non-constant polynomial f(n) grows unboundedly as n grows.]
(3) Conclude that for every non-constant polynomial f there must be an
n ∈ N such that f(n) is not prime. [Hint: Only one case remains.]
Q.10 Show that if a and m are relatively prime positive integers, then the
inverse of a modulo m is unique modulo m.
Q.11 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.12
(1) Show that if n is an integer then n
2 ≡ 0 or 1 (mod 4).
(2) Show 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.13
(a) State Fermat’s little theorem.
(b) Show that Fermat’s little theorem does not hold if p is not prime.
(c) Compute 302302 (mod 11), 47625367 (mod 13), 239674 (mod 523).
Q.14 Let m1, m2, . . . , mn be pairwise relatively prime integers greater than
or equal to 2. Show that if a ≡ b (mod mi) for i = 1, 2, . . . , n, then a ≡ b
(mod m), where m = m1m2 · · · mn.
2
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 For a collection of balls, the number is not known. If we count them
by 2’s, we have 1 left over; by 3’s, we have nothing left; by 4, we have 1
left over; by 5, we have 4 left over; by 6, we have 3 left over; by 7, we have
nothing left; by 8, we have 1 left over; by 9, nothing is left. How many balls
are there? Give the details of your calculation.
Q.17 Recall how the linear congruential method works in generating pseudorandom numbers: Initially, four parameters are chosen, i.e., the modulus
m, the multiplier a, the increment c, and the seed x0. Then a sequence of
numbers x1, x2, . . . , xn, . . . are generated by the following congruence
xn+1 = (axn + c) (mod m).
Suppose that we know the generated numbers are in the range 0, 1, . . . , 10,
which means the modulus m = 11. By observing three consecutive numbers
7, 4, 6, can you predict the next number? Explain your answer.
Q.18 Recall that Euler’s totient function ϕ(n) counts the number of positive
integers up to a given integer n that are coprime to n. Prove that for all
integers n ≥ 3, ϕ(n) is even.
Q.19 Recall the RSA public key cryptosystem: Bob posts a public key (n, e)
and keeps a secret key d. When Alice wants to send a message 0 < M < n
to Bob, she calculates C = Me
(mod n) and sends C to Bob. Bob then
decrypts this by calculating C
d
(mod n). In class we learnt that in order to
make this scheme work, n, e, d must have special properties.
For each of the three public/secret key pairs listed below, answer whether
it is a valid set of RSA public/secret key pairs (whether the pair satisfies
the required properties), and explain your answer.
(a) (n, e) = (91, 25), d = 51
(b) (n, e) = (91, 25), d = 49
(c) (n, e) = (84, 25), d = 37
3
Q.20 Consider the RSA system. Let (e, d) be a key pair for the RSA. Define
λ(n) = lcm(p − 1, q − 1)
and compute d
′ = e
−1 mod λ(n). Will decryption using d
′
instead of d still
work? (prove C
d
′ mod n = M)
4