CS 6104 : Solutions to Homework Assignment 2
June 9, 1998

Problem 1. [Solution Courtesy of Yizhong Wang]

Chapter 4, Problem 14. You may assume the result in Problem 2.22. Use Mathematicato calculate the actual probability for

Put those results in a table that also gives the relative error if the probability is taken to be .

We only need to show that

where is defined to be 1 if , and 0 otherwise.
But,

Clearly

and for ,

hence,

From exercise 2.22, we know that

So,

This leads to

Use the following Mathematicacode,

y={0,0,0,0,0,0,0,0,0,0};
Do[Do[If[GCD[i,j]==1,y[[k]]++],{i,1,k*100},{j,1,k*100}],{k,1,10}];
Do[y[[i]]=y[[i]]/((i*100)^2),{i,1,10}];
k=10;e=6/(Pi^2);
TableForm[Table[{i*100,N[y[[i]],4],100*N[Abs[y[[i]]-e]/e]},{i,1,k}]]

get the table:

Problem 2. [Solution Courtesy of Lynn Jones]

Implement the Extended Euclidean algorithm in Mathematica. (Mathematicahas the Euclidean and Extended Euclidean algorithms built in, but do not use those in your implementation.)

Let

Show how your implementation can be used to find a solution to the equation

Give the Mathematicasteps to obtain one such solution.

Here is my Mathematicafunction definition for the Extended Euclidean algorithm as listed on page 72 of Bach & Shallit:

extEuclid[u_,v_] := {                             \
uVar = u;                                         \
varV = v;                                         \
matr = {{1,0},{0,1}};                             \
n = 0;                                            \
q = 0;                                            \
While[((uVar  != varV  ) && (varV  != 0)), {      \
    q = Floor[uVar /varV ];                       \
    matr = Dot[matr,{{q,1},{1,0}}];               \
    tempU = uVar ;                                \
    uVar =varV ;                                  \
    varV  = tempU-(q*varV);                       \
    n++;                                          \
}];                                               \
divisor = uVar ;                                  \
ufactor = (-1)^n*matr[[2,2]];                     \
vFact = (-1)^(n+1)*matr[[1,2]];                   \
answers = {divisor, ufactor, vFact} }

The function returns a list whose first (and only) member is a list whose members are the divisor d and multipliers a and b, such that d is the greatest common divisor of inputs u and v and au + bv = d. The only modifications to the algorithm that were made for the Mathematicaimplementation are the addition of the test for v==0 in the While loop condition, and the creation of variable copies for the inputs (Mathematicatreats the inputs as constants and won't assign to their identifiers).

We can use results of this function to solve the given equation. Let's examine the right side of the equation:

Setting the coefficients of each c equal to the other, we solve for

Here is one way to find a solution with Mathematica:

• Set values for variables, , , and .

  In[5]:= cOne = 1717424330343597918506415;               \
          cTwo = 1514122986729833684874188480781;         \
          cThree = 244480356564695980335975744122413;

• Call extEuclid( ) and name the output resultOne.

  In[6]:= resultOne = extEuclid[cTwo,cThree]
  Out[6]= {{19429427, -4224791771747356826449601, 26165105555451677148416}}

• Extract the greatest common divisor, d, from resultOne and call extEuclid( ), naming the output resultTwo (You could also pass in ( ), but this is the same result!).

  In[7]:= resultTwo = extEuclid[cOne,resultOne[[1,1]]]
  Out[7]= {{19429427, 0, 1}}

• Set x, y, and z as indicated above.

  In[8]:= x = resultTwo[[1,2]];                     \
          y = resultTwo[[1,3]] * resultOne[[1,2]];  \
          z = resultTwo[[1,3]] * resultOne[[1,3]];  \
  {x,y,z}
  Out[8]= {0, -4224791771747356826449601, 26165105555451677148416}

• Verify the answer.

  In[9]:= cOne x + cTwo y + cThree z
  Out[9]= 19429427