# Find $X^2 \equiv 9 \pmod {13}$ without consulting table?

Find $X^2 \equiv 9 \pmod {13}$ without consulting table?

The answer is given as $3, 10$, but without consulting tables it would mean :

$X^2 - 9 \equiv 0 \pmod {13}$
So, either $(X-3)$ or $(X+3)$ is divisible by $13$, as difference between the two is $6$, and $(6,13)=1$.

\begin{align} (X-3) \equiv 0\pmod{13} & \ ======(X+3) \equiv 0\pmod{13}\\ X \equiv 3\pmod{13} & \ ====== X \equiv 10\pmod{13}\\ \end{align}

Issue is answer does not say that either $3$ or $10$ is a root, and I have stated only one is a root.

Addendum Have second question and am unable to be solve (as per the answer given) by working on the lines of Q.1.

1. Find $X^2 \equiv 1 \pmod {8}$ without consulting table?

The answer is given as : $1, 3 , 5,7$.

But, am able to get only the two values: $1, 7$ by following the approach followed in Q.1.

It is possible to get these 4 values by verification/substitution of each of the 8 values to be substituted for $X$, but what about by formula?

• Just note that in $\mathbb{R}$, $3^2=9$. So the solution to your equation is $3,-3$ modulo $13$ Jan 16 '18 at 7:08
• Don't worry about divisibility by $13$. Just say $(X-3)$ or $(X+3)$ is $0$. Then $X=3$ or $X=-3 \equiv 13-3 = 10$. Jan 16 '18 at 7:08
• This means that X-3=0(mod 13) or X+3=0(mod 13). Solve from there.
– SQB
Jan 16 '18 at 7:10
• @jiten You can't use the same approach literally since $8$ is not a prime, and $2,4$ are divisors of $0 \bmod 8\,$. So for example any $x$ such that $\{x-1,x+1\}=\{2,4\}$ will satisfy $(x-1)(x+1)=0\,$.
– dxiv
Jan 16 '18 at 8:06
• @jiten -- In general, modular arithmetic is best done with a prime modulus; the system is then an algebraic "field", in which every element except $0$ has a unique multiplicative inverse. Then the "zero product property" applies: if a product is zero, then a factor is zero. Jan 16 '18 at 8:21

Not much else to do (in fact, you are at the point of citing seemingly irrelevant facts, such as $6$ being coprime with $13$), except remembering the definition of prime element of a ring (in this case, the ring would be $\Bbb Z$). You know that $13\mid x^2-9=(x-3)(x+3)$. Since $13$ is prime in $\Bbb Z$, and it divides $(x-3)(x+3)$, it must divide either $x-3$ or $x+3$. Equivalently, either $x\equiv 3\pmod {13}$ or $x\equiv -3\pmod {13}$. Perhaps, if you so desire, you may observe that $-3\equiv 10\pmod{13}$.
• I am unable to understand why it is irrelevant to consider the difference between the roots as being co-prime to $13$. May be more help is needed, by elaboration. As it is modular arithmetic, so this thought comes to mind, i.e. difference between roots being important w.r.t. the modulus. Table lookup will not give any clue theoretically. Jan 16 '18 at 7:20
• Please see the second question, and tell me how 4 values can be obtained by formula approach to solve $X^2 - 1 \equiv 0\pmod 8$. Jan 16 '18 at 7:53