Just to finish the thought...  the method to reduce  (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 ]

 (mod 3) =  (mod 3) =  (mod 3) = 4 (mod 3) = 1 (mod 3)



 (mod 5) =  (mod 5) = 64 (mod 5) = 4 (mod 5)

 (mod 17) =  (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.

------------                   



 

Answer by Edwin McCravy(20054)   (Show Source): You can put this solution on YOUR website!
 
The above solution is incorrect.



      Observe that the sequence of exponents 998,990,... is an arithmetic
      sequence with common difference -8, and smallest positive term 6.
      
      
      
      
      
      
      The 125th term is 
      













So the remainder is 64.

Edwin
 

Answer by ikleyn(52780)   (Show Source): You can put this solution on YOUR website!
 .





            I have much more simple solution.







First, notice that 255 = 256 - 1 = ,  so   = 255 + 1.


Second, notice that   =  = .


Therefore,   = .


Apply the Newton's binomial formula to present   as the sum of degrees of the number 255 with integer coefficients.

All the terms of this binomial expansion will have the number 255 in positive degrees, except the last term, which is 1.


So, all the terms of this binomial expansion are divisible by 255, except the last term 1.


It means that when you multiply this expansion by 64, all the terms of this new expansion are divisible by 255, 
except the last term, which is 64.


It proves that the reminder of   is 64, when it is divided by 255.




Solved.





-------------





By the way, it is a STANDARD method for solving such problems.





It works smoothly in many other similar problems.







 

Answer by AnlytcPhil(1806)   (Show Source): You can put this solution on YOUR website!
 
I think the straight-forward way, i.e., 
"divide it out and see what the remainder is"
is the best way:



          4⁴⁹⁹ + 4⁴⁹⁵ + ... + 4⁷ + 4³
4⁴-1)4⁵°³
     4⁵°³-4⁴⁹⁹
          4⁴⁹⁹ 
          4⁴⁴⁹ - 4⁴⁹⁵     
                 4⁴⁹⁵
                        ...   
                              4⁷
                              4⁷ - 4³
                                   4³ = R
Edwin



 

RELATED QUESTIONS

find the remainder when 7^12 is divided by... (answered by tommyt3rd)

Find the remainder when 40^{13} is divided by... (answered by MathLover1,ikleyn)

k divided by 4 has a remainder off 3. What is the remainder when k+3 is divided by... (answered by richwmiller)

If m is divided by 5 leaves a remainder is 2, while n is divided by 5 leaves a remainder... (answered by richwmiller)

What is that number , when that number is divided by 9 the remainder is 8 , when that... (answered by AnlytcPhil)

I am thinking of a number, when divided by 9 the remainder is 4. When divided by 5 the... (answered by MathLover1,greenestamps)

When a is divided by 7, the remainder is 5; and when b is divided by 7, the remainder is... (answered by rapaljer)

Find the quotient and the remainder when 3x^4 - 5x^3 + 7x^2 -6x - 8 is divided by (x +... (answered by stanbon)

When f(x)is divided by x-1, the remainder is -1; when it is divided by {{{x^2}}}, the... (answered by robertb)