0

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?

jiten
  • 4,524
  • 2
    Just note that in $\mathbb{R}$, $3^2=9$. So the solution to your equation is $3,-3$ modulo $13$ – pisco Jan 16 '18 at 07:08
  • 1
    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$. – mr_e_man Jan 16 '18 at 07:08
  • 1
    This means that X-3=0(mod 13) or X+3=0(mod 13). Solve from there. – SQB Jan 16 '18 at 07:10
  • @SQB 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$. – jiten Jan 16 '18 at 07:53
  • @mr_e_man 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$. – jiten Jan 16 '18 at 07:54
  • @pisco125 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$. – jiten Jan 16 '18 at 07:55
  • 2
    @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 08:06
  • 1
    @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. – mr_e_man Jan 16 '18 at 08:21
  • @dxiv Any good reference for the same is requested. – jiten Jan 16 '18 at 08:29
  • @mr_e_man Any good reference for the same is requested. – jiten Jan 16 '18 at 08:36
  • 1
    @jiten See quadratic residues and related MSE questions. – dxiv Jan 16 '18 at 08:38

1 Answers1

2

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. – jiten Jan 16 '18 at 07:20
  • I claim it to be irrelevant because the solution I thought of does not use it, nor one that does comes to mind. But if you know an argument that effectively uses it, feel free to use it: it's your exercise/question after all. –  Jan 16 '18 at 07:27
  • 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$. – jiten Jan 16 '18 at 07:53
  • No, I won't. I'd rather delete this answer, since it's outdated. @jiten –  Jan 16 '18 at 07:56
  • Please don't do that. I will re-edit the title. – jiten Jan 16 '18 at 07:57
  • @jiten the issue is that the difference between the roots being coprime to the modulus is not enough information to ensure that those are the only roots. For example, solving $n^2\equiv9$ mod $35$, you get $(n+3)(n-3)\equiv 0$ mod $35$ and $3-(-3)$ is coprime to $35$, but $n\equiv 17$ is also a solution. – Especially Lime Jan 16 '18 at 08:58