S2.html

Math 342 Assignment 2, Solutions

Maximum mark 30

1. Here is a proof that that 4^(1/2) is irrational.

4 marks

Proof: Let a/b=4^(1/2) , where a and b are integers and a/b is in lowest terms so that gcd(a,b)=1. Multiply the equation by b to obtain a=4^(1/2)*b. Square the equation to obtain a^2=4*b^2. From this equation we see that a^2 must be a multiple of 4, thus a must be a multiple of 4. Since a is a multiple of 4 let a=4*m, where m is an integer. Then we have (4*m)^2=4*b^2. This expands to 16*m^2=4*b^2 . Now divide by 4 to find 4*m^2=b^2. Now we see that b^2 must be a multiple 4, so b is a multiple of 4, But now we have that both a and b are multiples of 4, so a/b would not be in lowest terms. This contradicts our initial assumption that a/b was in lowest terms. This contadiction proves that 4^(1/2) must be irrational.

Which steps were valid and which steps were invalid in the above proof?

Everything is okay up to a^2 must be a multiple of 4. The next step is a must be a multiple of 4. This is not valid. a only needs to be a multiple of 2.

Similarly the b nust be a multiple of 4 , is also invalid. The other steps were okay. So the proof is not valid. We also know that 4^(1/2)=2 .

2. A baseball player's batting average is .213 . What is the least number of hits that this player could have, and what is the corresponding least number of times at bat. Note: for non baseball fans, the batting average of a player is defined to be the number of hits divided by the number of times at bat, rounded to 3 decimal places to the right of the decimal point.

4 marks

Use continued fractions to find nearby rational approximations.

> convert(.213,confrac);

> lower := convert(.2125,confrac);

> upper := convert(.2135,confrac);

> with(numtheory,cfrac):

> ans := cfrac([0,4,1,2,3]);

> hits := numer(ans);

> at_bat := denom(ans);

Therefore the minimum number of hits is 10, and the corresponding minimum number of times at bat is 47 .

> check := evalf(ans,3);

>

We could also do it by a brute force search. checking every rational number until one rounds to .213

> c := true:
for d from 2 while c do
for n to d-1 while c do
r := evalf(n/d,3);
if r=.213 then c := false; Hits := n; At_bat := d; fi;
od;
od:
Hits, At_bat;

3. Prove that the extended Euclidean algorithm works.

First of all the algorithm terminates since by the division equation thereom, the remainders form a decreasing sequence of non-negative integers.

We will proof it by induction on the number n of division steps required. If b | a then the gcd is b and 0*a+1*b=b , so s=0 and t=1 and the algorithm works for n=1 division step. Now we assume that the algorithm works for n=k division steps. Let us proof that it also works for n=k+1 division steps. After the first step of the Euclidean algorithm we have that

r[-1]=r[0]*q[1]+r[1] where q[1] is the first quotient and r[1] is the first remainder, r[-1]=a and r[0]=b. The other divison steps in the Eucldean algorithm may be written as

r[0]=r[1]*q[2]+r[2]

r[1]=r[2]*q[3]+r[3]

...

r[k-2]=r[k-1]*q[k]+r[k]

r[k-1]=r[k]*q[k+1]+0.

Since these equations form a k-step Eucldean algorithm for inputs r[0] and r[1], use the induction assumption to assume that they can be back-solved for the integers x and y satiifying the equation x*r[0]+y*r[1]=r[k]=g=gcd(r[0],r[1]). Now we back solve our first divison equation to obtain r[1]=r[-1]-r[0]*q[1] . We plug this into our k-step extended Euclidean algorithm equation to find that

x*r[0]+y*(r[-1]-r[0]*q[1])=g. We rewrite this as:

r[-1]*y + r[0]*(x-q[1]*y)=g. Recall that r[-1]=a and r[0]=b . This becomes:

a*y+b*(x-q[1]*y)=g. Therefore g is also the gcd(a,b) and we may choose s=y and t=x-q[1]*y to complete the proof.

4. Find g= gcd(177,111) and integers x and y such that 177*x+111*y=g, by using the extended Euclidean algorithm by hand.

3 marks

177=111*1+66

111=66*1+45

66=45*1+21

45=21*2+3

21=3*7+0,

Therefore g=3. Now back solve.

3=45-2*21

=45-2*(66-45)=3*45-2*66

=3*(111-66)-2*66=3*111-5*66

=3*111-5*(177-111)=-5*177+8*111 .

Therefore x=-5 and y=8.

Check 8*111=888, 5*177=885. 888-885=3 =g. Yes it checks.

5. (a) Find all integer solutions to the equation 61*x+89*y=22873 .

(b) Which of the integer solutions to part (a) are non-negative?

Notes: A solution is non-negative if both x and y are non-negative. A solution is positive if both x and y are positive.

> s5 := isolve(61*x+89*y=22873);

part (b)

> x5 := subs(s5,x);

> y5 := subs(s5,y);

> s5b := solve({x5>=0,y5>=0},_N1);

> non_neg_sol := {seq(s5,_N1=0..4)};

part c

> pos_sol := non_neg_sol minus {{y=257,x=0}};

6. Find all integer solutions of the following system of two linear equations in {x,y,z} by hand calculations:

{4*x-7*x+5*z=19, 9*x+3*y-8*z=14}

Use the matrix method. I will use Maple has a calculator to do row and column operations. First we fix the typo in the first equation , where the second x should be a y.

> e1 := 4*x-7*y+5*z=19;

> e2 := 9*x+3*y-8*z=14;

> with(linalg):

> a := array([[4,-7,5,1,0],[9,3,-8,0,1],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0]]);

> a := addcol(a,1,2,2);

> a := addcol(a,1,3,-1);

> a := swapcol(a,1,3);

> a := addcol(a,1,2,-1);

> a := addcol(a,1,3,-4);

> a := addcol(a,2,3,-2);

> a := addcol(a,3,1,17);

> a := addcol(a,3,2,-38);

> a := swapcol(a,2,3);

We did not need to do any row operations, so we can skip some steps.

> soly := array([19,14,n]);

> v := submatrix(a,[3,4,5],[1,2,3]);

> sol := evalm(v &* soly);

> ans := {x=sol[1],y=sol[2],z=sol[3]};

Check

> subs(ans,[e1,e2]);

> other_ans := subs(n=m+9,ans);

> another_ans := subs(n=-k+8,ans);

Note: There are many other solutions.

>

7. Consider the following system of two linear equations to be solved for integer variables {x1,x2,x3,x4}:

{93*x1+43*x2-62*x3-77*x4=65, 19*x1-50*x2+89*x3-53*x4=-87}

and the following 3 possible solution sets S1,S2,S3 , where n1,n2, n3,n4, n5,n6 are integer parametrers.

S1: {x1 = -7*n1+13*n2-5,x2 = 10760*n1-17086*n2-4467,

x3 = 6502*n1-10324*n2-2703, x4 = 765*n1-1213*n2-325} .

S2: {x1 = -146+91*n3-133*n4, x2 = 174611+2232646*n3-3263098*n4,

x3 = 105501+1349660*n3-1972580*n4, x4 = 12384+160173*n3-234099*n4}.

S3: {x1 = 2414-309*n5-276*n6, x2 = -7195894-2511643*n5-2151201*n6,

x3 = -6158104-860559*n5-724890*n6, x4 = -537361-171784*n5-146983*n6}.

Which values of the parameters satisfy the equations? Which solution sets yield the general solution? Why?

4 marks

> with(linalg):

Warning, new definition for norm

Warning, new definition for trace

> eq:={93*x1+43*x2-62*x3-77*x4=65, 19*x1-50*x2+89*x3-53*x4=-87}:

> S1:={x1 = -7*n1+13*n2-5,x2 = 10760*n1-17086*n2-4467,x3 = 6502*n1-10324*n2-2703, x4 = 765*n1-1213*n2-325}:

> S2:={x1 = -146+91*n3-133*n4, x2 = 174611+2232646*n3-3263098*n4,x3 = 105501+1349660*n3-1972580*n4, x4 = 12384+160173*n3-234099*n4}:

> S3:={x1 = 2414-309*n5-276*n6, x2 = -7195894-2511643*n5-2151201*n6,x3 = -6158104-860559*n5-724890*n6, x4 = -537361-171784*n5-146983*n6}:

> subs(S1,eq);

S1 is a solution for all integer values of its parameters n1 and n2.

> subs(S2,eq);

S2 is a solution for all integer values of its parameters n3 and n4.

> ss3 := subs(S3,eq);

> ps3 := isolve(ss3);

We see that S3 is only a solution for the above values of its parameters n5, and n6, so it is not a general solution.

Find a general solution.

> ss := isolve(eq);

> p1 := solve(subs(ss,S1),{n1,n2});

Since fractions appear in the above, S1 is not a general solution.

> one_sol := subs(_N1=1,_N2=1,ss);

> solve(subs(S1,one_sol));

Since we did use non-integer values of the parameters n1,n2 to create one of the solutions, we have shown that S1 does not include all the solutions for integer values of its parameters n1 and n2. Therefore S1 is not a general solution.

What if we solved it the other way?

> pp1 := solve(subs(S1,ss),{_N1,_N2});

> M1 := array([[-7,13],[5,-9]]);

> det(M1);

This is another reason , we did not get the general solution from S1, the above determinant was not one of the units {1,-1}.

> p2 := {solve(subs(ss,S2),{n3,n4})};

Since we can't solve for {n3,n4}, S2 is not a general solution.

Can we solve the other way?

> pp2 := solve(subs(S2,ss),{_N1,_N2});

> coeff_matrix := array([[91,-133],[169,-247]]);

> linalg[det](coeff_matrix);

That is another reason we did not have a general solution, but only a disguised one parameter family of solutions.

8. Perform a modulo 9 hand calculation to check the following multiplication: 8973*5876=52726348

3 marks

8973*5876 (mod 9) = (8+9+7+3)*(5+8+7+6) (mod 9) = (27)*(26) (mod 9)=(2+7)*(2+6) (mod 9)=9*8 (mod 9) = 72 (mod 9) = (7+2) (mod 9)=9 (mod 9) = 0 (mod 9).

52726348 (mod 9) = (5+2+7+2+6+3+4+8) (mod 9) = 37 (mod 9) = (3+7) mod 9 = 10 (mod 9) = (1+0) (mod 9) = 1 (mod 9).

Since 0 does not equal 1 (mod 9) there is an error in the calculation.

9. Find the last 4 base 16 digits of 4567^6789 which is given in base 10. Use A,B,C,D,E,F for digits 10,11,12,13,14,15 respectively. You may use a computer.

> ans := power(4567,6789) mod 16^4;

> ans_hex := convert(ans,hex);

>

10. Find all integer solutions of 37*x-48*y=7 by hand calculations.

4 marks

We use the extended Euclidean algorithm on 48 and 37.

48=37*(1)+11

37=11*(3)+4

11=4*(2)+3

4=3*(1)+1

3=1*(3)+0

Now back solve.

1=4-3

=4-(11-2*4)=3*4-11

=3*(37-3*11)-11=-10*(11)+3*37

=-10*(48-37)+3*37=13*37-10*48=1.

Now multiply this by 7 to find one solution.

(7*13)*37+(10*7)*(-48)=7.

Therefore one solution is x=91, y=70.

The homogeneous linear equation is 37*x-48*y=0. The general solution of this is x=48*n, y=37*n, for arbitrary integer parameter n. So the general solution to the original equation is the sum of the particular solution plus the homogeneous solution which is

{x=91+48*n, y=70+37*n}. This can also be expressed as

{x=43+48*m, y=33+37*m}, by letting n=m-1.

11. How many positive integer solutions does the following equation have?

6521981871*x+4177436519*y=28190271884295130476773 . You may use a computer.

> eq11 := 6521981871*x+4177436519*y=28190271884295130476773;

> s11 := isolve(eq11);

> eq_n := {subs(s11,x)>0, subs(s11,y)>0};

> n11 := solve(eq_n,_N1);

> f11 := evalf(n11);

From the above we see that 0<=_N1<=1033 . Therefore there are 1034 positive integer solutions.

12. Find Gaussian integers x,y and g , such that g=a*x+b*y=gcd(a,b) where a=47+59*i and b=37-43*i . Make Re(g)>0 and Im(g)>=0. You may use a computer.

4 marks

> r[-1] := 47+59*I;

> r[0] := 37-43*I;

> q[1] := r[-1]/r[0]; q[1] := round(q[1]);

> r[1] := r[-1]-r[0]*q[1];

> q[2] := r[0]/r[1]; q[2] := round(q[2]);

> r[2] := r[0]-r[1]*q[2];

> q[3] := r[1]/r[2]; q[3] := round(q[3]);

> r[3] := r[1]-r[2]*q[3];

> q[4] := r[2]/r[3]; q[4] := round(q[4]);

> r[4] := r[2]-r[3]*q[4];

> q[5] := r[3]/r[4]; q[5] := round(q[5]);

> r[5] := r[3]-r[4]*q[5];

Now back solve.

> z := evalm([[0,1],[1,-q[5]]] &* [[0,1],[1,-q[4]]]);

> z := evalm(z &* [[0,1],[1,-q[3]]]);

> z := evalm(z &* [[0,1],[1,-q[2]]]);

> z := evalm(z &* [[0,1],[1,-q[1]]]);

> x := z[1,1];

> y := z[1,2];

Check

> x*r[-1]+y*r[0];

Multiply by a unit to put the gcd in the first quadrant.

> g := I*r[4];

> x := I*x;

> y := I*y;

Check

> x*r[-1]+y*r[0];

13. Find the worst case of the Euclidean algorithm. This means that given a bound B, such that the inputs (a,b) are constrained by : 1<=a<=B and 1<=b<=B . Find the inputs a and b to the Euclidean algorithm, such that the Euclidean algorithm performs the maximum number of division steps, and find the maximum number of division steps. Use a computer to vary the bound B from 1 to 32 , then for each value of the bound, generate all possible input ordered pairs (a,b) , then run the Euclidean algorithm on each ordered pair (a,b), keeping track of how many division steps k, each ordered input pair (a,b) required . Then record which ordered pairs needed the maximum number of division steps, for each value of the bound B. Do you recognize these numbers? Now double the bound B to 64, and guess which ordered pairs (a,b) would take the maximum number of division steps and the number of division steps.

> EAd := proc (a, b) local r, i, q; description `The input is a and b which are integers.`, `The output is the gcd(a,b).`, `It uses the Euclidean algorithm.`; r[-1] := abs(a); r[0] := abs(b); userinfo(1,EA1,evaln(r[-1]) = r[-1]); userinfo(1,EA1,evaln(r[0]) = r[0]); for i while r[i-1] <> 0 do q[i] := iquo(r[i-2],r[i-1],evaln(r[i])); userinfo(1,EA1,cat(`step `,i),cat(r[i-2],`=`,r[i-1],`*`,q[i],`+`,r[i])); userinfo(2,EA1,evaln(q[i]) = q[i],evaln(r[i]) = r[i]) od; i-1; end;

> for B to 64 do
M := 0;
for i to B do
for j to B do
d := EAd(i,j);
if d>M then
k := 1;
M := d;
Mij[k] := [i,j];
elif d=M then
k := k+1;
Mij[k] := [i,j];
fi;
od;
od;
print(bound=B,max_div=M,worst_cases=[seq(Mij[n],n=1..k)]);
od:

> with(combinat):

Warning, new definition for Chi

> for i to 11 do 'fibonacci'(i)=fibonacci(i) od;

Sometimes there is more than one worst case for a given bound, We don't see a pattern for the larger numbers in these cases. We see that the smallest worst case inputs are consecutive increasing Fibonacci numbers as long as the second one is less than or equal to the bound. The maximum number of division steps is equal to the index of smaller Fibonacci number.

If we increase the bound to 64, then the smallest worst case input should be EA1(34,55) which would take 9 division steps. This was confirmed by the above program when we doubled the bound from 32 to 64.

>

14 (a) What is the exact probability that 2 randomly chosen positive integers bounded by 9 are relatively prime? Also find the approximate probabilty to 8 signifigant digits. (b) Same as part (a) , except increase the bound to 99. (c) Same as part (a), except increase the bound to 999.

Hints: two integers a and b are relatively prime if gcd(a,b)=1. You could use a computer to generate all possible ordered pairs of integers (a,b) such that 1<=a<=B and 1<=b<=B where B is the bound. Then compute g=gcd(a,b) . If g=1 then add 1 to a counter variable k. The exact probability would be k/B^2 .

> for B in [9,99,999] do
k := 0;
for i to B do
for j to B do
g := igcd(i,j);
if g=1 then k := k+1; fi;
od;
od;
pe := k/B^2;
p8 := evalf(pe,8);
print(bound=B, exact_prob=pe, approx_prob=p8);
od:

Note: This probability should approach as the bound goes to .

> evalf(6/Pi^2,8);

15. Let K={a+b*(-1/2+1/2*(-3)^(1/2)) : both a and b are integers} .

(a) Which elements of K are algebraic numbers?

(b) Which elements of K are algebraic integers?

4 marks

(a) Let x=a+b*(-1/2+1/2*(-3)^(1/2)) . Then (x-a+1/2*b)^2=(1/2*b*(-3)^(1/2))^2 . This expands to x^2+(-2*a+b)*x+a^2-a*b+b^2/4 = 1/4*b^2*(-3). Therefore x^2 + (-2*a+b)*x +a^2-a*b+b^2 = 0 . Since a and b are arbitrary integers , this degree=2 polynomomial in x ,has integer coefficients. Therefore every element of K is an algebraic number.

(b) We see that the above polynomial is monic, so every element of K is also an algebraic integer.

> w := -1/2+1/2*sqrt(-3);

> x := a+b*w;

> x1 := evalc(1/x);

> den := (a-1/2*b)^2+3/4*b^2;

> z1 := (a-b)/den;

> z2 := -b/den;

> z := z1+z2*w1;

> zero := normal(x1-z);

Therefore both z1 and z2 must be integers, if x is to be a unit. Let z3=z1-z2, then z3 must also be an integer.

> z3 := ((a-b)-(-b))/den;

if abs(b)>1 then the denominator den=(a-b/2)^2+3/4*b^2>=3/4*b^2, and abs(z2)<=abs(b)/(3/4*b^2)<=4/(3*abs(b))<=4/(3*2)<=2/3 . Recall that z2 is an integer so abs(b)<=1 or b is one of {1,0,1} . Since den = (a-b/2)^2+3/4*b^2=a^2-a*b+b^2=(b-a/2)^2+3/4*a^2 . We see that from z3 if abs(a)>1 then abs(z3)<=abs(a)/(3/4*a^2)<=4/(3*abs(a))<=4/(3*2)<=2/3 . So abs(a)<=1 and a must also be one of {-1,0,1} . We have only 9 cases to check.

a=-1, b=-1, z3=-1, z2=1, yes, a unit since both z's are integers

a=-1, b=0, z3=-1, z2=0, yes, a unit

a=-1, b=1, z3=-1/3 , no, z3 is not an integer

a=0, b=-1, z3=0, z2=1, yes

a=0, b=0, no, since this yields 0

a=0, b=1, z3=0, z2=-1, yes

a=1,b=-1, z3=1/3, no

a=1,b=0, z3=1, z2=0, yes

a=1,b=1, z3=1, z2=-1, yes

Therefore there are 6 units . They are :

{1, -1, w, -w, 1+w, 1-w} =

{1,-1, -1/2+1/2*(-3)^(1/2), 1/2-1/2*(-3)^(1/2), 1/2+1/2*(-3)^(1/2), 1/2-1/2*(-3)^(1/2)}