I have difficulty computing the $\rm mod$ for $a ={1,2,3\ldots50}$. Is there a quick way of doing this?
How do we compute $50a^2\pmod{30000}$?
-1
$\begingroup$
discrete-mathematics
-
1The 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? – 2012-11-23
2 Answers
0
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} $
0
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.