Remainder of a Big Quotient

$\begin{array}{l l l l} 3^{45} & = (3^5)^9 &\equiv (-7)^9 & \pmod{125} \\ & \equiv -(7^3)^3 & \equiv 32^3 & \pmod{125} \\ &\equiv 2^{15} &\equiv (2^7)^2 \times 2 & \pmod{125} \\ &\equiv 3^2 \times 2 &\equiv 18 & \pmod{125}\\ \end{array}$

Hence, the required remainder is: 18.

Solution 1: We use the fact that $3 \equiv 128 \equiv 2^7 \pmod{125}$ . Also, $\phi(125) = \frac {4}{5} \times 125 = 100$ , so by Euler's Theorem, $2^{100}\equiv 1 \pmod{125}$ . Hence, $3^{45} \equiv (2^7)^{45} \equiv 2^{315} \equiv 2^{15} \equiv 2^7 \times 2^7 \times 2 = 3 \times 3 \times 2 \equiv 18 \pmod{125}$ .

Solution 2: We have $3^5 \equiv 243 \equiv -7 \pmod{125}$ , and $7^4 \equiv 2401 \equiv 26 \pmod{125}$ . So $3^{45} \equiv 3^{5 \times 9} \equiv (-7)^9 \equiv -7^9 \equiv - 26 \times 26 \times 7 \equiv 18 \pmod{125}$ .

\­(3^45\­)=\­(3^40 \times 3^5\­) \­(3^5 \equiv 118 \pmod{125}\­) \­(3^10 \equiv 49 \pmod{125}\­) ----------\­(\frac {118 \times 118}{125}\­) \­(3^20 \equiv 26 \pmod{125}\­) ----------\­(\frac {49 \times 49}{125}\­) \­(3^40 \equiv 51 \pmod{125}\­) ----------\­(\frac {26 \times 26}{125}\­) \­(3^45 \equiv 18 \pmod{125}\­) ----------\­(\frac {51 \times 118}{125}\­)

Hence answer is remainder of \­(\frac {51 \times 118}{125}\­), which is equal to 18.

3^4=1+5k, k=16 raise both sides to power 11 to get 3^44=1+(11)(5k)+other terms using binomial thm. other than 1st two terms contain 125, so 3^44=881mod(125). multiply by 3 and reduce mod 125

3^3=25+2,

Using Binomial expansion, 3^{45}=(3^3)^{15}=(2+25)^15=2^15+15.2^{14}.25+...(mod 125)≡2^{15},

Now 2^7≡3(mod 125) , 2^15=2.(2^7)^2≡2.3^2

I have a strange way to answer this one:

We know $\phi(125)=100$ , and $45=(100/2)-5$ , so $3^{45}=3^{100/2-5}\equiv$

If 3 is a primitive root: $(-1)(3^{-1})^5,$

Else: $(3^{-1})^5.$

Since $(125+1)=3(42)$ we get:

$(42)^5 = ((2)(3)(7))^5=(32)(243)(16807) \equiv (32)(-7)(57) \equiv -18.$ Therefore, we get 18 if 3 is primitive, or 107 otherwise.

Edit: You can find 3 to be primitive as $3^{2+4n}\equiv 4 mod 5$ , and $3^{4n}\equiv 1 mod 5$ . Since $3^{50} = 3^{2+4(12)} \equiv 4 mod 5$ , it is primitive. So the answer is simply 18.