A problem by Bogdan Simeonov

Let us take a=1 as 1 is a natural no. not divisble by 5.

Now, $a^{100}=1^{100}=1$

The answer is= mod(a,125) = $\boxed{1}$

Funny Approach : Since the question must have a fixed answer, we consider the most advantageous value of $a$ i.e. $a=1$ since $5\nmid 1$ , and get...

$1^{100}=1\equiv \fbox{1} \pmod{125}$

Formal Approach : Let $a=5b+r$ , for $b\in\mathbb{N}_{0}$ and $r\in\left\{1,2,3,4\right\}$ . So we have...

$(5b+r)^{100}=\sum_{i=0}^{100} \dbinom{100}{i} (5b)^{i} r^{100-i}$

Since, $5^3=125$ , for $i\geq 3$ , the terms in the expansion will be divisible by $125$ , Hence...

$\sum_{i=0}^{100} \dbinom{100}{i} (5b)^{i} r^{100-i}\equiv \sum_{i=0}^{2} \dbinom{100}{i} (5b)^{i} r^{100-i}\pmod{125}$

$\sum_{i=0}^{2} \dbinom{100}{i} (5b)^{i} r^{100-i}=\dbinom{100}{0} (5b)^{0} r^{100-0}+\dbinom{100}{1} (5b)^{1} r^{100-1}+\dbinom{100}{2} (5b)^{2} r^{100-2}$

$=r^{100}+100\cdot 5b\cdot r^{99}+4950\cdot 25b^2\cdot r^{98}\equiv r^{100} \pmod{125}$

Now note that, $\gcd(1,125)=\gcd(2,125)=\gcd(3,125)=\gcd(4,125)=1$ , and $\varphi(125)=100$ . So we have from Euler's Theorem, for $r\in \left\{1,2,3,4\right\}$ ...

$r^{100}=r^{\varphi(125)}\equiv 1\pmod{125}$

And so, all in all, for $b\in\mathbb{N}_{0}$ and $r\in\left\{1,2,3,4\right\}$ , we get...

$(5b+r)^{100}\equiv \fbox{1}\pmod{125}$

I will provide two solutions - one is easier, but longer and the other is more complicated, but shorter.