Discrete Mathematics Answers

Q1. Let {1,2,3,4,6,9} with the partial order of divisibility. Draw its Hasse Diagram

Q2. [{1,2,3,4,5}, s], Draw its Hasse Diagram

Determine an, the number of words of length n on the alphabet {a, b, c} which

do not contain the substring ab. For instance, a3 = 21 since there are 21 such words

with 3 letters, namely:

aaa aac aca acb acc baa bac

bba bbb bbc bca bcb bcc caa

cac cba cbb cbc cca ccb ccc.

Let α, β be roots of the equation x^2− 3x − 1 = 0. For each nonnegative integer n,

let y_n = α^n + β^n

. Show that gcd(y_n, y_(n+1)) = 1 for each nonnegative integer n.

Use the Well Ordering Principle to prove that any integer greater than or equal to 23 can be represented as the sum of nonnegative integer multiples of 6, 7 and 17.

Encrypt the message ATTACK using the RSA cryptosystem with n = 43 · 59 and

e = 13, translating each letter into integers and grouping together pairs of integers, as

done in example 11 in the textbook and in the classnotes.

(a) Use Fermat’s little theorem to compute: 4101 mod 5, 4101 mod 7, 4101 mod 11.

(b) Use your results from part (a) and the Chinese Remainder Theorem to compute

4

101 mod 385. (note that 385 = 5 × 7 × 11).

(a) Find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm.

Show your steps.

(b) Solve the congruence 19x ≡ 7 (mod 141), by specifying all the integer solutions x

that satisfy the congruence.

≡

Let R={1,1),(1,2),(2,1), (2,1), (3,3), (4,1), (5,1)} define on set A= {2,3,4,5,6}

1. Consider the K-Maps given below. For each K- Map

i. Write the appropriate standard form (SOP/POS) of Boolean expression.

ii. Design the circuit using AND, NOT and OR gates.

iii. Design the circuit only by using

• NAND gates if the standard form obtained in part (i) is SOP.

• NOR gates if the standard form obtained in pat (i) is POS.

AB/C

0

1

00

1

0

01

1

1

11

1

0

10

0

1

2. Produce truth tables for given Boolean expressions.

i. |A|.|B|.C + A.|B|.|C| + A.B.C + |A|.B.|C|

ii. (A+|B|+C).(A+B+C).(|A|+B+|C|)