Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 309 EXAM

You must not discuss any aspect of this exam with anyone other than the instructor until you have submitted the exam, which must be submitted in-parson at the start of class Tuesday next week. You will have to use a computer for some computations, but make sure you explain clearly what computer commands and programs have been used.

1.    For this problem you may use a computer. Find two random integers, each of  length at least 10 digits- call them a and b. Let p and q be the smallest primes larger than a and b, respectively, and let m = p q. Find a 10-digit integer e with GCD(e,(p-1)(q-1))=1. We will encrypt a message x by computing y = xe  mod m. Deter- mine the encryption when x =2,when x = 3, and when x = 6. What is the relationship  among these three? How will you decrypt messages? In particular, if y =3, determine the original message x.

2.    Find the GCD of 1260 and 1234, by hand, and find integers x andy so that 1260 x + 1234 y = GCD(x,y). Is i possible to find integers u and v so that 1260 u + 1234 v = 10? Either find them or explain why it is not possible.

3     If n is a non-negative integer, let F(n) be the number of subsets of {1,2,3,...,n} that do not contain consecutive integers. (The empty set is included). For instance, when n = 3 there are five such subsets:

。, {1}, {2], {3], {1,3}.

The other three subsets of {1,2,3} contain consecutive integers; {1,2}, {2,3{, {1,2,3}.

Show that if n is a positive integer then

F(n+2) = F(n+1) + F(n).

Note that F(0)=1 and F(1)=2. Use this to compute (with the aid of a computer) F(1000). Do you recognize this as a familiar function? (Hint: the letter F..)

4.    Let p= 173. This number is a prime. We are interested in solving congruences of the form xk = a mod 173. Show that when   k = 5 the congruence has a unique solu-tion mod 173 for every value of a. On the other hand, show that when k = 4 the congru- ence either has no solutions or 4 solutions,depending on a. In particular, the congru-   ence xk = 1 mod 173 has 4 solutions      , two of which should be obvious.

5.    Suppose the probability space ：has four elements- a, b, c andd- of respective    probabilities .1, .2, .3 and .4. Suppose the random variable X is given by X(a)=1, X(b)=2, X(c)=3 and X(d) =4. Compute the expected value and variance of X. Suppose X(10000)  is the sum of 10000 independent repetitions of X. Compute the expected value and variance of X(10000). Find, to at least two decimal places, the probability that X(10000)> 30000,that X(10000)>30100,and that 29900< X(10000) < 30200. (You may use some tables for this calculation.

6.    Suppose we have four “cards” in a deck, numbered 1, 2, 3 4. We pick a card at random and let X be the number. Find the expected value and variance.Suppose we pick two cards, at random, without replacing the first card, and add the two numbers. Find the expected value and variance.Do the same for three cards. (Note that the first  card and the second card and the third card are not independent since we cannot draw the same card twice.)     If you do this correctly you should find the variance for one card should be the same as for the sum of three cards. Explain why this is.

7.   Suppose we wish to transmit the message a, b, c, d with some error-correction  and detection built-in. To do this we find a polynomial f of degree at most three, with f(0)=a, f(1) = b, f(2) =c andf(3) = d, and transmit the message

f(-2), f(-1), f(0), f(1), f(2), f(3).

Suppose the received message is 2, 0 ,1, 2, 6, 12.  Assuming that either the received message is correct or that there is exactly one error, determine what the message was supposed to have been.

8.    Prove that if n is a non-negative integer then

(n-2) 2n-1=：k(n)=0 (k(n) ) (k-1) .

(The symbol is the binomial coefficient.)

9.    Suppose we have two coins- C1 and C2. One of the coins, C1, is “fair”, while the  other one, C2, has a probability of getting a head when flipped of .9. We pick one of   the coins, at random, and flip that one coin 100 times. Suppose the number of heads is 50. Which coin was the most likely? Suppose the number of heads is 74.Which coin is the more likely? You must justify your answers.

10.   (i)    A bridge hand is 13 cards from a deck of 52. The order in which the cards are dealt does not matter. How many bridge hands are there? (You may use a calculator    to get an exact numerical answer.) How many bridge hands are there that have exactly two aces?

(ii)   A pinochle deck has 48 cards, but there are only 24 distinct cards, the deck hav-  ing two of each of the 24 distinct cards. If a “hand” can be any number of cards, but the order in which cards are dealt is immaterial, how many distinguishable hands are possible with a pinochle deck? The point is that, for instance there are two queens of diamonds, indistinguishable- a hand might have none of them, or both, but if it has    exactly one there is no way of telling which of the two queens it has.