Nov:05(Thu)

MTH 225[M] Exercise-Set #8

Due November 12 (Thursday)

• In our textbook, read Chapter 3 from the beginning through Section 3.6.

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:

               1001
   
             1 0011
   
            10 0000
   
           101 1010
   
          1100 1110
   
          1111 1111
   
       11 0101 0111
   

   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:
   • 34
   • 61
   • 223
   • 400
   • 1024
   Try to do this without using a calculator.
   Show intermediate steps/explanations for obtaining answers.
   In your final answers, write spaces between blocks of up to four bits, starting from the right; e.g. write "11 0101 0111" rather than "1101010111" (and also not "1101 0101 11".

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 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 #7's Exercise N, 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
      

      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 a Lecture-Module showed determination of φ(9): obtain gcd() for 10 with every integer between 1 and 10, and then count how many of these integers are relatively prime to 10.

   
   

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.   60, 90
   2.   77, 105,
   3.   110, 273
   4.   5, 25
   5.   220, 1400
   Try to do this without using a calculator.