Hey Gang, let's solve problem  #2.31P46  from Prof. William Stein's text
   "Elem. Number Theory: Primes, Congruences and Secrets"!

   /------------------------------------\
    Let  
            M := 113

    and let == mean =M= here.
      Find all residues b in Zed_M
    satisfying

    *1:     102^{70} + 1  ==  b^{37}.
   \____________________________________/



/----- Solution, Step 1 ---------------------------------\
  Let == denote =113=, henceforth.

The only primes whose square is less-equal 113
are 2,3,5,7; evidently none divide 113, so

        M =recall= 113  is prime, and thus
        F := phi(M)  = 112.
\________________________________________________________/


/---- Step 2 --------------------------------------------\
  Define L, for "LefthandSide", by

        L := 102^{70} + 1 .

Note that

          L^3  ==  b^{3*37}
                =  b^{111}  =note=  b^{F - 1}.
Thus 

*2:  IF WE KNEW that  [L cop M], then we could apply EFThm to
     reduce the exponent mod F, i.e, mod 112, and conclude that

          L^3  ==  <1/b>_M ,
i,e
          b    ==  < 1/[L^3] >_M .

This last, we could easily compute via LBolt.   

  NOTE:  If  [L cop M], then the above argument shows that
         there is a /UNIQUE/ soln b to (*1).
\________________________________________________________/


/---- Step 3 --------------------------------------------\
  To compute L, note

        102^2  ==  [-11]^2  =  121  ==  8.

Hence  [L - 1] equals

        102^{70}  ==  8^{35}  =  2^{3*35}
                              =  2^{105}.

Since [2 cop M], our EFT applies to tell us that

        L - 1  ==  2^{105 - 112}
                =  2^{-7}
               ==  <1/128>_M.

Since

        128  ==  15,

LBolt tells us

      n:   r_n   q_n     t_n
    /------------------------\
      0:   113    --       0
      1:    15     8       1
      2:    -7    -2      -8
      3:     1    -7     -15
      4:     0 Infty    -113
    \________________________/

that  

        <1/15>_M  ==  -15 .

Hence

        L == -15 + 1  =  -14.

Seeing that L is is coprime to M, we may apply our "Step 2".
\________________________________________________________/


/---- Step 4 --------------------------------------------\
Since
        L^2  ==  196  ==  83  == -30,
nec.
        L^3  ==  -14*[-30]  
              =  4*7*15  =  4*105  
                        ==  4*[-8]  =  -32.

Our "Step 2" says to mod-M reciprocate this,

      n:   r_n   q_n     t_n
    /------------------------\
      0:   113    --       0
      1:   -32    -4       1
      2:   -15     2       4
      3:    -2     8      -7
      4:     1    -2      60
      5:     0 Infty     113
    \________________________/

giving that 

        b   ==   < 1/[L^3] >_M   ==  60.

Nice!   [But we're not finished until the Paperwork is Done!]
\________________________________________________________/



        ::::::::::::::::::
        :::: Checking ::::
        ::::::::::::::::::
  We use Repeated-Squaring.   Note

     /--------------------- Mod 113 ----\
      N:      2^N |     Accum | 102^[2^N]
    ---+----------+-----------+-------------
      0:        1 |         1 |       102
      1:        2 |         1 |         8 <<
      2:        4 |         8 |       -49 <<
      3:        8 |       -53 |        28
      4:       16 |       -53 |        -7
      5:       32 |       -53 |        49
      6:       64 |       -53 |        28 <<
    All:     done |       -15 |          
     \--------------------- Mod 113 ----/

     So  102^{70}  is mod-113 congruent 
     to the product of the << marked values.
     Their mod-113 product is -15. 

Hence  L  indeed is mod-M congruent to  -15+1,
i.e
            L  ==  -14.


    OTOHand, let's compute  b^{37}:

     /--------------------- Mod 113 ----\
      N:      2^N |     Accum |  60^[2^N]
    ---+----------+-----------+-------------
      0:        1 |         1 |        60 <<
      1:        2 |       -53 |       -16
      2:        4 |       -53 |        30 <<
      3:        8 |        -8 |        -4
      4:       16 |        -8 |        16
      5:       32 |        -8 |        30 <<
    All:     done |       -14 |          
     \--------------------- Mod 113 ----/

     So  60^{37}  is mod-113 congruent 
     to the product of the << marked values.
     Their mod-113 product is -14. 

And -14 is mod-M congruent to -14.


/---- Alternative Step 4 --------------------------------\
  We could have avoided the first LBolt by computing <8^{35}>
using RS [Repeated-Squaring].

More importantly, we can convert the task of taking s 37th-root, 
to computing a power [via RS].

Why?  How?  We'll use that exponent 37 is coprime to exponent 112.


A Bézout pair for (37, 112) is (-3, 1), as shown in

            1  =  [37]*[-3] + [112]*[1] .

And indeed, we raised L to the -3 to compute our b.
Alternatively, we can use a Bézout pair that gives positive
weight to 37.  I.e, defin a new Bézout pair 

        (S,T)  :=  (-3, 1)  +  (112, -37).

Hence  S =  -3 + 112  =  109.  

  Since [b cop M], our b equals

  b^1   =  b^{S*37 + T*112}
        =  [b^{37}]^S  *  [b^{112}]^T
       ==  [b^{37}]^S  *  1^T
        =  [b^{37}]^S .

Hence

	b  == [-14]^{109}.

And

     /--------------------- Mod 113 ----\
      n:      2^n |     Accum | -14^[2^n]
    ---+----------+-----------+-------------
      0:        1 |         1 |       -14 <<
      1:        2 |        99 |        83
      2:        4 |        99 |       109 <<
      3:        8 |        56 |        16 <<
      4:       16 |       105 |        30
      5:       32 |       105 |       109 <<
      6:       64 |        32 |        16 <<
    All:     done |        60 |          
     \--------------------- Mod 113 ----/

     So  -14^{109}  is mod-113 congruent 
     to the product of the << marked values.
     Their mod-113 product is 60. 
\________________________________________________________/

What Fun!
			Cheers,  Prof.K
================================================================