Question 1137583
Applying Euler's Theorem:
{{{  4^phi(255) = 1 }}} (mod 255) 

<br>
{{{ phi(255) = 128}}}

so
{{{ 4^(128) = 1 }}} (mod 255)

sorry ... pressed Post Answer too soon <br>


I had hoped to use Euler's Theorem to reduce the exponent to something small.  However for this problem one ends up with  {{{ 4^119 }}} (mod 255)  
(119 = 503-128*3), and now the computation of {{{ 4^119 }}} is still too large.
<br>

<pre>
Just to finish the thought...  the method to reduce {{{ 4^119 }}} (mod 255)
 is to factor 255 into 3*5*17 and then apply Euler's Theorem to each of these.
Once that is done, you will have a set of three modulo congruences which may be solved using the Chinese Remainder Theorem.

Phi(3) = 2  [ Phi(prime) = prime - 1, always ]
{{{ 4^119 }}} (mod 3) = {{{ (4^2)^59 * 4 }}} (mod 3) = {{{ 1^59 * 4 }}} (mod 3) = 4 (mod 3) = 1 (mod 3)

{{{ 4^119 }}} (mod 5) = {{{ (4^4)^29 * 4^3 }}} (mod 5) = 64 (mod 5) = 4 (mod 5)
{{{ 4^119 }}} (mod 17) = {{{ (4^16)^7 * 4^7 }}} (mod 17) = 13 (mod 17)

This leads to the set of congruences
13+17n = 13 (mod 17) = 4 (mod 5) = 1 (mod 3)

This can be solved piecewise, algebraically, but since modulus is only 255, you can just list remainder values  (mod 255) starting with the largest prime factor to make the list shorter:

     13, 30, 47, 64, 81, 98, 115, 132, 149, 166, 183, 200, 217, 234, 251
 
then list the mod 5 values for these:
      3,  0,  2,  4,  1,  3,   0,   2,   4,   1,   3,   0,  2,    4,   1

then list the mod 3 values:
      1   0   2,  1,  0,  2,   1,   0,   2,   1,   0,   2,  1,    0,   2


Then notice 64 is the only value satisfying all 3 conditions.   The solution is unique, so in practice, if you were listing out the 13 (mod 17) values in the first row, you could check the (mod 5) and (mod 3) values then stop at 64.
------------