<s>[INST] How to solve for x in modular arithmetic when the equation has exponent? Say I have the following equation-->
$x^2=180345$ and modulo is $8$. I am using an online calculator to solve this equation, and the answer comes out to be $x=1$ or $3$ or $5$ or $7$.
I am not getting the maths behind this. It will be very helpful if someone can refer to some materials where these kind of equations are solved or atleast show me the algorithm for solving this equaions. Thank you.
 [/INST] First thing get that $180345$ to something reasonable.  $180345 \equiv 1$ so we have
$x^2\equiv 1 \pmod 8$ so $x^2 -1 = \equiv 1 \pmod 8$.  Now we can just test them one after another as there are just $7$ of them....
But let's be clever.  $x^2 \equiv 1 \pmod 8$
$x^2 -1 \equiv \pmod 8$
$(x+1)(x-1) \equiv 0 \pmod 8$.
So $x\equiv \pm 1\pmod 8$ are two immediate answers.
Any other solutions must relate to the zero divisors of $8$.
$(x+1)(x-1)= 8k$ for some integer $k$. and $x+1, x-2$ are both even.  So we have $x-1, x+1 = 2,4$ or $4,6$ or $6,8\equiv 0$ or $0,2$.
So $x = 3,5, 7\equiv -1, $ or $1$.
=======
Also as player3236 stated in the comments, for any odd number $n = 2k+1$ we have $n^2 \equiv 4k^2 + 4k + 1\equiv 4(k^2+k)+ 1\pmod 8$.  And as $k^2 + k$ is always even....
$n^2 \equiv 4(k^2+k) + 1 \equiv 8\frac {k^2 + k}2 + 1\equiv 1\pmod 8$.
So every odd number is a solution.  $x\equiv 1,3,5,7$
And clearly $x$ even is not a solution so... that's it.
</s>