0
$\begingroup$

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?

$\endgroup$
11
  • 2
    $\begingroup$ Just note that in $\mathbb{R}$, $3^2=9$. So the solution to your equation is $3,-3$ modulo $13$ $\endgroup$
    – pisco
    Jan 16 '18 at 7:08
  • 1
    $\begingroup$ 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$. $\endgroup$
    – mr_e_man
    Jan 16 '18 at 7:08
  • 1
    $\begingroup$ This means that X-3=0(mod 13) or X+3=0(mod 13). Solve from there. $\endgroup$
    – SQB
    Jan 16 '18 at 7:10
  • 2
    $\begingroup$ @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\,$. $\endgroup$
    – dxiv
    Jan 16 '18 at 8:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – mr_e_man
    Jan 16 '18 at 8:21
2
$\begingroup$

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}$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – jiten
    Jan 16 '18 at 7:20
  • $\begingroup$ 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. $\endgroup$
    – user228113
    Jan 16 '18 at 7:27
  • $\begingroup$ 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$. $\endgroup$
    – jiten
    Jan 16 '18 at 7:53
  • $\begingroup$ No, I won't. I'd rather delete this answer, since it's outdated. @jiten $\endgroup$
    – user228113
    Jan 16 '18 at 7:56
  • $\begingroup$ Please don't do that. I will re-edit the title. $\endgroup$
    – jiten
    Jan 16 '18 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.