How do we compute $50a^2\pmod{30000}$?

Question

I have difficulty computing the $\rm mod$ for $a ={1,2,3\ldots50}$. Is there a quick way of doing this?

Answer 1

Given $x = 50a^2$, you want to find $r$ such that $50x = 30000q + r$. Then $r$ must be divisible by 50, right? Explain to yourself why that must be the case.

So try to find $a^2 \mod 600$ first. Then express $50a^2 \mod 300000$ in terms of $a^2 \mod 600$. That will help you for all $a$.

Next, notice that if $a^2 < 600$, then $a^2 \mod 600$ is just $a^2$. Use that to save work. For which $a$ do you actually have to compute something?

As the comment by @EuYu says, do the rest by hand.

Answer 2

Hint: note that $50(a+1)^2=50a^2+100a+50$

Example: $50\cdot34^2\equiv27800\pmod{30000}$ so $$ \begin{align} 50\cdot35^2 &\equiv27800+34\cdot100+50\\ &\equiv27800+3450\\ &\equiv31250\\ &\equiv1250\pmod{30000} \end{align} $$