Question

Please answer question 3

Find all (infinitely many) solutions of the system of congruence's: Use Fermata little theorem to find 8^223 mod 11. (You are not allowed to use modular exponentiation.) Show that if p f a, then a^y-2 is an inverse of a modulo p. Use this observation to compute an inverse 2 modulo 7. What is the decryption function for an affine cipher if the encryption function is 13x + 17 (mod 26)? Encode and then decode the message ''happy". How many positive integers are there less than 500000 that are divisible by 3 or 4? How many bit strings of length 6 are there that contain 2 consecutives Is? You are given a set of numbers S = {17.19, 15, 11, 13, 7, 9, 1, 3, 5}. Let T be an arbitrary subset of S. What is the smallest number n such that if |T*| greaterthanorequalto n, then there are two numbers x and y in T such that x + y = 20?

Answer 1

3)

A.

given encryption function (ax+b)mod m = (13x+17)

mod m

Hence a=13 b=17 m=26

Decryption function = a^-1 *(x-b)mod m

Modular multiplicative inverse of a mod m is

i.e x = 13^-1(mod 26)

13x = 1(mod 26)

there is no inverse for above function since for any x the function doesnt give remainder one.

Hence the decryption is not possible.

B.

Given word = happy = 7 0 15 15 24

Apply y = (13x+17)mod 26

Then y0=91+17 mod 26=108 mod 26= 4

y1=17 mod 26=17

y2= 195+17 mod 26= 212 mod 26=4

y3= 195+17 mod 26=4

y4= 312+17 mod 26 =17

Hence y = 4 17 4 4 17