1

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.

Turing101
  • 201
  • 1
    All odd squares $\equiv 1 \pmod 8$, and $180345 \equiv 1 \pmod 8$. We can only say that $x$ is odd. – player3236 Feb 13 '21 at 06:12
  • but there should be a proper approach right? to solve these problems. Like, say an algorithm.. – Turing101 Feb 13 '21 at 06:18
  • "All odd squares ≡1(mod8)" and "We can only say that x is odd." I think what player3236 is saying is that $x=$odd is a always a solution. So $x \equiv 1,3,5,7$ are the solutions. – fleablood Feb 13 '21 at 06:28

2 Answers2

1

$$x^2 = 180345 \bmod 8 = 1 \bmod 8$$

Now, $x$ can have only the following set of values $\bmod 8$:

$\{0, 1, 2, 3, 4, 5, 6, 7\}$

You can verify that only $x = 1, 3, 5, 7$ satisfy $x^2 = 1 \bmod 8$ and the other values do not.

PTDS
  • 3,464
1

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.

fleablood
  • 124,253