Hi,

Can you help me with the part b and part c of problem 4? Thanks in advance!!!

 

 

Homework 2
CSE/MATH 467 Due: 02 September, 2016 1. Preview Problem from HW1. Implement the script which is Bressoud’s Alogrithm 1.7 (Algorithm 1 in our pseudocode available at http:/www.math.psu.edu/wdb/467/pseudocode.
pdf) and test it on the following pairs of numbers:
• 34 126, 2718
• 21 377 104, 12 673 234
• 355 876 536, 319 256 544
• 84187 85375, 78499 11069
In particular you should define a function and then evaluate the function on the pairs given
above. Do not use a screen prompt. In your final project, you will have various functions
calling up and using values of other functions, and requiring prompts for the interior functions
would be worse than useless.
What to hand in: Print out your script and print out a record of the session showing how
you initialize the script and evaluate the function it defines on the given pairs.
2. One formulation of the Principle of Mathematical Induction is the following:
Every non-empty set of positive integers has a least element.
Use this formulation to prove the validity of the
Division Algorithm for positive integers. If a ∈ Z≥0 and b ∈ N, then there exist
q, r ∈ Z≥0 with
a=b·q+r
0 ≤ r < b.
3. [Based on Bressoud 1.09] a) Using the Euclidean Algorithm and hand calculation, find
gcd(34126, 2718).
b) Use the calculation of the first part to express gcd(34126, 2718) as an integral linear
combination of 34126 and 2718. 4. [Bressoud 1.19]
a) Find integers m, n such that
1947 × m + 264 × n = 33.
b) For arbitrary a, b ∈ Z, show how to always find infinitely many k, l ∈ Z, depending on
a, b with ka + lb = 0.
c) Show that there are infinitely many integral solutions of
1947 × m + 264 × n = 33.
This illustrates that the coefficients produced by the Euclidean Algorithm are far from being
the only ones giving a linear combination equal to gcd(a, b). 2 5. a) Let x, y ∈ Z not both be zero. We have used in the class the principle that, for any
a, b ∈ Z, gcd(x, y) | ax + by. Give that proof here again.
b) Deduce that for any a, b, c, d ∈ Z, since similarly gcd(x, y) | cx + dy, we must have that
gcd(x, y) | gcd(ax + by, cx + dy).
c) Finally conclude that if, in addition, ad − bc = ±1, then
gcd(x, y) = gcd(ax + by, cx + dy).
The fact that gcd(x, y) = gcd(x + ky, y) that we used for the Euclidean Algorithm is a very
special case of this exercise.
Hint: Recall from linear algebra that under these conditions the linear map
  

 
 0 
a b
x
ax + by
x
x
=
=
7→
c d
y
cx + dy
y
y0
 
x
is invertible. What is the inverse matrix and what does that say about the vector
in
y
 0
x
?
terms of
y0

Attachments:

• 1492652038-hw02.pdf