Question 27146
Hi,

This is quite easy if you know how. The first thing you need to know is the identity.

*[tex (ab)\%m = (a\%m)(b\%m)\%m]

If your not comfortable with this then try proving it. This identity means we can take the remainder at any time during the multiplication without effecting the result.

We could quite naivly proceed to evalute *[tex x_{300}] given *[tex x_{i+1}=23x_i \% 40]. That would take you ages though so I'm going to do some repeated squaring. Google for 'repeated squaring' if you want more information.

{{{x^300=(x^150)^2}}}
{{{x^150=(x^75)^2}}}
{{{x^75=x*x^74}}}
{{{x^74=(x^37)^2}}}
{{{x^37=x*x^36}}}
{{{x^36=(x^18)^2}}}
{{{x^18=(x^9)^2}}}
{{{x^9=x*x^8}}}
{{{x^8=(x^4)^2}}}
{{{x^4=(x^2)^2}}}

I'm going to take modulus 40 after every multiplication. Subbing {{{x=23}}} into this (from bottom up) gives.

{{{x^2=9}}}
{{{x^4=1}}}
{{{x^8=1}}}
{{{x^9=23}}}
{{{x^18=9}}}
{{{x^36=1}}}
{{{x^37=23}}}
{{{x^74=9}}}
{{{x^75=7}}}
{{{x^150=9}}}
{{{x^300=1}}}

So there ya go. *[tex 23^{300} \% 40=1]

Hope that helps,

Kev