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

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

-
The numbers are not large by any standards. I can't see this taking anymore than a two or three minutes even by hand with a calculator. Tedious maybe, but certainly not difficult. What exact difficulties are you having? – EuYu Nov 23 '12 at 15:09

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.

-

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}

-