ASSIGNMENT-2
CS 2214: DISCRETE STRUCTURES FOR COMPUTING
Instructions: Please submit a single pdf file in gradescope.
1. (25 points) Let p be a prime number and a an integer not divisible by p. Prove that
there exists an integer b such that ab ≡ 1 (mod p). Conclude that every non-zero
element in Zp has a multiplicative inverse.
Hint: Use Bezout’s identity.
2. (25 points) Let x be an integer such that x leaves a remainder 3 when divided by 5,
leaves a remainder 7 when divided by 12 and it leaves a remainder 8 when divided
by 13. Find the remainder when you divide x by 780 using the Euclidean algorithm.
Hint: Chinese remainder theorem and the example following it in textbook.
3. (25 points) Let n be a positive integer. Prove that if 2n − 1 is a prime number then
n is a prime number.
4. (25 points) Prove that there does not exist integers any a and b such that the function
p(n) = n
2 + an + b is a prime number for every positive integer n.
Hint: First prove that if such a polynomial exists then b = 1. Then use modular
arithmetic to conclude the result.
1
