Gauss's lemma in number theory states that if we have a number $a$ which is coprime to a prime $p$ then if we consider the set $S=\{a,2a,3a,.....((p-1)/2)a\}$ then say that if the number of elements in this set who's remainder after division is strictly greater than $p/2$ is $t$ then $(\tfrac{a}{p})=(-1)^t$ where $(\tfrac{a}{p})$ is the Legendre symbol.
Now for small p this is a very easy to use method but for larger $p$ it seems to become essentially useless, because of the number of elements of $S$ you'd have to calculate. Is there a a clever way to speed up your work for large $p$ ?
$$71-9=2\cdot 31$$ So, minus 9 for each even value and alternate parity once it changes to less gives :
$$2a,4a,6a,9a,11a,13a,15a,18a,20a,22a,25a,27a,29a,31a,34a$$
Most of my calculation was at switching parity points. So your comments example, was solved by in effect, by one step of the Euclidean gcd algorithm. You can do the same for a lot of higher values.
In reality all you need is if t is odd or even ( parity) as that determines the right hand side.