Mar:23(Mon)

MTH 225(M) Exercise-Set #7

Due March 30 (Monday)


Please do exercises in teams of two. Doing so garners 5% extra credit.

Show intermediate steps/explanations for obtaining answers.

  1. [4 homework points]   For each of the following binary numbers, express it in decimal: Try to do this without using a calculator.
    Show intermediate steps/explanations for obtaining answers.

  2. [4 homework points]   For each of the following decimal numbers, express it in binary: Try to do this without using a calculator.
    Show intermediate steps/explanations for obtaining answers.

  3. [6 homework points]   Here is how processing goes with the basic repeated squaring version of exponentiation(a,e) for the invocation exponentiation(3,11): 
    int exponentiation(int a, int e) {      // a := , e := 
    int result = 1;                     // result := 
    int sqrrep = a;                     // sqrrep := 
    while ( e > 0 ) {                   // ( > 0)  :=  
        if ( e % 2 == 1 )               // ( % 2 == 1)  :=  ( == 1)  :=  
            result = result * sqrrep;   // result :=  ( * )  :=  

        sqrrep = sqrrep * sqrrep;       // sqrrep :=  ( * )  :=  
        e = e/2;                        // e :=  ⌊/2⌋  :=  ⌊⌋  :=  
        }
    while ( e > 0 ) {                   // ( > 0)  :=  
        if ( e % 2 == 1 )               // ( % 2 == 1)  :=  ( == 1)  :=  
            result = result * sqrrep;   // result :=  ( * )  :=  

        sqrrep = sqrrep * sqrrep;       // sqrrep :=   *   :=  
        e = e/2;                        // e :=  ⌊/2⌋  :=  ⌊⌋  :=  
        }
    while ( e > 0 ) {                   // ( > 0)  :=  
        if ( e % 2 == 1 )               // ( % 2 == 1)  :=  ( == 1)  :=  
            result = result * sqrrep;

        sqrrep = sqrrep * sqrrep;       // sqrrep :=  ( * )  :=  
        e = e/2;                        // e :=  ⌊/2⌋  :=  ⌊⌋  :=  
        }
    while ( e > 0 ) {                   // ( > 0)  :=  
        if ( e % 2 == 1 )               // ( % 2 == 1)  :=  ( == 1)  :=  
            result = result * sqrrep;   // result :=  ( * )  :=  

        sqrrep = sqrrep * sqrrep;       // sqrrep :=  ( * )  :=  
        e = e/2;                        // e :=  ⌊/2⌋  :=  ⌊⌋  :=  
        }
    while ( e > 0 ) {                   // ( > 0)  :=  

    return  result;                     // return 
    }
    Show an 'algorithm trace' like that for the invocation exponentiation(10,13).  (Feel free to simply copy the above material (HTML) and change details such as what numbers are in the spaces.  If you do this, you might need to adjust the sizes of the spaces.)
    Please use commas when writing numbers such as 1,000 and 10,000 and 100,000,000 etc.
    Try to do this without using a calculator.


  4. [6 homework points]   Show an 'algorithm trace' like in lectures and like in the preceding exercise (C) with the second repeated squaring version of modular_exponentiation(a,e,m) for the invocation modular_exponentiation(7,13,17).
    Try to do this without using a calculator.


    Acknowledgement: Some of the following exercises are derived from Richard Johnsonbaugh.

  5. A condition for the correctness or validity of modular_exponentiation() is the fact that for any integers x and y, and for any positive integer m, (x*y) mod m == ((x mod m)*(y mod m)) mod m.  Similarly, (x+y) mod m == ((x mod m)+(y mod m)) mod m (for any integers x and y and for any positive integer m). 
    Check these equalities by doing the following:
    1. [8 points] Confirm that x*y mod m == ((x mod m)*(y mod m)) mod m for a few values of x, y, and m as follows:
      1. Calculate 10 mod 7, 100 mod 7, 1000 mod 7, and 10000 mod 7, and check whether 10*10 mod 7 =?= ((10 mod 7)*(10 mod 7)) mod 7,  10*100 mod 7 =?= ((10 mod 7)*(100 mod 7)) mod 7,  10*1000 mod 7 =?= ((10 mod 7)*(1000 mod 7)) mod 7,  and 100*100 mod 7 =?= ((100 mod 7)*(100 mod 7)) mod 7.
      2. Calculate 8 mod 5, 64 mod 5, 512 mod 5, and 4096 mod 5, and check whether 8*8 mod 5 =?= ((8 mod 5)*(8 mod 5)) mod 5,  8*64 mod 5 =?= ((8 mod 5)*(64 mod 5)) mod 5,  8*512 mod 5 =?= ((8 mod 5)*(512 mod 5)) mod 5,  and 64*64 mod 5 =?= ((64 mod 5)*(64 mod 5)) mod 5.
      Show intermediate steps here such as each intermediate product  x*y  and  (x mod m)*(y mod m)  etc.

    2. [4 points] For Exercise-Set #6's Exercise K, redo your calculations of each f13(y) as follows: 
          f13(y)  :=  ((y mod 7) + (⌊(y-1)/4⌋ mod 7) - (⌊(y-1)/100⌋ mod 7) + (⌊(y-1)/400⌋ mod 7))  mod 7
    
      
    i.e.
    f13(y)  :=  ((y mod 7) + (|_(y-1)/4_| mod 7) - (|_(y-1)/100_| mod 7) + (|_(y-1)/400_| mod 7))  mod 7
      Show all those intermediate values mod 7.  For example for next year, 2010: 
          f13(2010)  :=  ((2010 mod 7) + (⌊(2010-1)/4⌋ mod 7) - (⌊(2010-1)/100⌋ mod 7) + (⌊(2010-1)/400⌋ mod 7))  mod 7
               :=  ((2010 mod 7) + (     502     mod 7) - (      20       mod 7) + (        5      mod 7))  mod 7
               :=  (       1     +                5     -                  6     +                  5    )  mod 7
               :=  (                                            5                                        )  mod 7
               :=                                                                                            5
      For this exercise, remember to redo all of the calculations of f13(y) which you did previously, i.e. for all of the years specified previously.

    Try to do all this work without using a calculator.


  6. [2 homework points]   Exhibit three positive integers d, a, and b such that  d|(a·b),  d < a,  d < b,  a ≠ b,  d ∤ a  (i.e. d does not evenly divide a), and  d ∤ b  (i.e. d does not evenly divide b).
    With your answer, include showing the value of a·b.
    Suggestion from Mr. Cobb (Fall 2008): guess and check.


  7. [4 homework points]   Consider our textbook's Exercise 3.5.17 (and its solution in the back of the book ;-) . Show determination of φ(10) the same way Lecture-Module #3 showed determination of φ(9): obtain gcd() for 10 with every integer between 1 and 10, and then count how many are relatively prime.


  8. [3 homework points]   Determine  3φ(10) mod 10,  7φ(10) mod 10, and  9φ(10) mod 10.
    Show the intermediate steps of work such as the values of 3φ(10), 7φ(10), and 9φ(10).
    Try to do this without using a calculator.
    Suggestion: if you want, use the facts that  49 == (50 - 1)  and  81 == (80 + 1).


  9. [10 homework points]   Here is one way to obtain gcd(a,b) specified in lectures:
    if complete/thorough prime factorization of a is  2e2 * 3e3 * 5e5 * 7e7 * ...
    and complete/thorough prime factorization of b is  2f2 * 3f3 * 5f5 * 7f7 * ...
    then  gcd(a,b) := 2min(e2,f2) * 3min(e3,f3) * 5min(e5,f5) * ...
    Determine the greatest common divisor of each of the following pairs of integers (a,b), explicitly using the above scheme. In each case, you'll need to give the complete/thorough prime factorization of each number (a and b as well as gcd(a,b)).
    1.   90, 60
    2.   105, 77
    3.   273, 110
    4.   25, 5
    5.   1400, 220
    Try to do this without using a calculator.


  10. [3 homework points]   Do our textbook's Exercise 3.5.24 .
    Try to do this without using a calculator.
    Show intermediate steps of work, such as the complete/thorough prime factorizations of 1000 and 625, and the values of gcd(1000,625) and lcm(1000,625) obtained from the prime factorizations.


  11. [10 homework points]   Show the sequence of values that the variables x and y have (and the results) during performance of the Euclidean algorithm for gcd(x,y) applied to the five pairs of integers specified in Exercise I above:
    1.   90, 60
    2.   105, 77
    3.   273, 110
    4.   25, 5
    5.   1400, 220

    Try to do this without using a calculator.
    For examples: 
    * for gcd(56,16): 56, 16, 8, 0;  result: 8
* for gcd(65,50): 65, 50, 15, 5, 0;  result: 5

Rem. show intermediate steps for your work, for all exercises.