**Order Management**Login // <![CDATA[ orderSysUser(); function orderSysUser(){ var url = 'https://essayheroes.us/orders/api/is_loggedin'; jQuery.get(url,null,function(response){ var user = JSON.parse(response); if(user){ jQuery("#ordersys_user").slideDown(); jQuery("#orderssys_user_name").html('<a href="https://essayheroes.us/orders/user/profile">'+user.name+'</a>'); jQuery("#ordersys_login").slideUp(); }else{ jQuery("#ordersys_login").slideDown(); jQuery("#ordersys_user").slideUp(); } }); } function ordersysLogin(){ var url = 'https://essayheroes.us/orders/api/login'; var data = jQuery("#ordersys_login").serialize(); jQuery.get(url,data,function(response){ console.log(response); }); return false; } // ]]>

## Algorithms & Data Structures course

**Exercise 1.9**. Suppose we run Algorithm ExtEuclid on input (117,67). Show the steps of the computation by giving the data corresponding to that shown in in the table in Example 1.2.

**Exercise 1.10**. Show that if a ≥ b > 0, then the values s and t computed by ExtEuclid(a, b) satisfy |s| ≤ b/d and |t| ≤ a/d.

Hint: prove by induction on b—be careful, you have to stop the induction before b gets to zero, so the last step to consider is when b | a.

**Exercise 1.11.** Suppose that a, b are integers with d := gcd(a, b) ̸= 0.

### (a) Show that a/d and b/d are relatively prime.

### (b) Show that if s and t are integers such that as + bt = d, then s and t are relatively prime.

**Exercise 1.12**. Let n be an integer. Show that if a, b are relatively prime integers, each of which divides n, then ab divides n.

**Exercise 2.7.** Let n be a positive integer. For x ∈ {0, . . . , 2n −1}, let x ̃ denote the integer obtained by inverting the bits in the n-bit, binary representation of x (note that x ̃ ∈ {0, . . . , 2n − 1}). Show that x ̃ + 1 ≡ −x (mod 2n). This justifies the usual rule for computing negatives in 2’s complement arithmetic.

### Hint: what is x + x ̃?

**Exercise 2.11.** For each of the following congruences, determine all the integer solutions z ∈ {0, . . . , 999}. To so this, you should first put the congruence in the form az = b (mod 1000), as we did in going from (2.2) to (2.3) in Example 2.3. Then follow the steps outlined in §2.2.3. Show all your steps (but you may use a calculator to help with the multiplications). Use the extended Euclidean algorithm to compute modular inverses, where necessary.

### (a) 100z + 200 ≡ 93z + 171 (mod 1000)

### (b) 115z + 130 ≡ 100z + 165 (mod 1000)

### (c) 115z + 132 ≡ 100z + 140 (mod 1000)

### (d) 119z + 132 ≡ 113z + 140 (mod 1000)

**Exercise 2.25. **Calculate the order of 9 mod 100. Show your work by building a table of powers 9^i mod 100. In addition, from this table, identify the multiplicative inverse of 9 mod 100.

**Exercise 2.30.** Compute 399 mod 100 using the repeated squaring algorithm. Show your work.

**Exercise 3.3. **Consider the field F = Z5. Let f = X3 +X+[1] ∈ F[X], g = [2]X2 +[3]X+[4] ∈ F[X], and h = [3]X2 + [2]X + [1] ∈ F [X]. Compute (gh) mod f . Show your work. That is, you should compute the product polynomial P = gh ∈ F [X], and then use polynomial division with remainder to compute P mod f. Along the way, you the coefficients of any polynomials you compute should be reduced mod 5.

**Exercise 3.4. **Consider the field F = Z5. Use the Lagrange interpolation formula to compute the coefficients of the polynomial g ∈ F [X] of degree less than 3 such that g([1]) = [3], g([2]) = [4], g([3]) = [1].

### Show your work.

DETAILED ASSIGNMENT