18
$\begingroup$

In my math notes it shows this example:

Example: Compute the square root of $3 \pmod{143}$. We have $143=11\cdot 13$. (Then he jumps to this:) $$ \sqrt{3}\equiv \pm 5 \pmod{11} $$ $$ \sqrt{3}\equiv \pm 4 \pmod{13}. $$ Using the Chinese Remainder Theorem, we can calculate the four square roots as $82, 126, 17$ and $61$.

The lecturer never makes anything clear even though it is our first encounter with modular arithmetic. I don't know were the $4$ or the $5$ come from or the $\sqrt{3}$. Can anyone explain to me how he got the solutions above?

And also how does he use this information in conjunction with the Chinese Remainder Theorem in order to arrive at the square roots? I would really appreciate if anyone could help me out here.

$\endgroup$
0

4 Answers 4

30
$\begingroup$

There are actually several different concepts here, so I'll try to address all of them. I'll get to the modular arithmetic in just a moment, but first a review:

SQUARE ROOTS

We should know that 25 has two square roots in ordinary arithmetic: 5 and -5.

MODULAR ARITHMETIC SQUARE ROOTS

IF the square root exists, there are 2 of them modulo a prime. To continue our example, 25 has the two square roots 5 and -5.

We can check this:

$$(-5)^2 = 25 \equiv 3\bmod 11$$ $$(5)^2 = 25 \equiv 3\bmod 11$$

To find the square roots sometimes takes a bit of trial and error. Often you have to go through each value $v$ and square it (to get $v^2$) to check if it's equivalent to $n \bmod p$, where $n$ is the number whose square root you want to find.

MULTIPLE PRIMES

Again, if a square root exists, there are two square roots modulo each prime. So if we are using multiple primes, there can be more square roots. For example, with two primes, there are 2 square roots modulo the first prime and two square roots modulo the second prime. This gives us $2 \cdot 2 = 4$ square roots.

In general, if we can find a square root modulo each prime, there are a total of $2^n$ square roots modulo $n$ primes.

RETURNING TO YOUR EXAMPLE

We can first calculate 3 modulo 11 and 13:

$$3 \equiv 3 (\bmod 11)$$ $$3 \equiv 3 (\bmod 13)$$

So, modulo 11, we are looking to find a number that, when squared, is equivalent to 3. If we find one, we know that there will be another. So we check the numbers: $1^2 \equiv 1$, $2^2 \equiv 4$, $3^2 \equiv 9, \dots$ and find that

$$5^2 = 25 \equiv 3 (\bmod 11)$$

...so we know that there will also be another square root modulo 11. Continuing on our quest, we check

$$6^2 = 36 \equiv 3 (\bmod 11)$$

...so we've found the square roots modulo 11. We then continue this modulo 13 to find that:

$$4^2 = 16 \equiv 3 (\bmod 13)$$ $$9^2 = 81 \equiv 3 (\bmod 13)$$

So we know that our square root is either 5 or 6 modulo 11, and either 4 or 9 modulo 13. This gives us 4 possibilities. We can then find that:

$$82 \equiv 5 (\bmod 11), 82 \equiv 4 (\bmod 13)$$ $$126 \equiv 5 (\bmod 11), 126 \equiv 9 (\bmod 13)$$ $$17 \equiv 6 (\bmod 11), 17 \equiv 4 (\bmod 13)$$ $$61 \equiv 6 (\bmod 11), 61 \equiv 9 (\bmod 13)$$

$\endgroup$
6
  • 3
    $\begingroup$ Modulo a prime, there will be at most two square roots, because unique factorization holds in $\Bbb F_p[x]$ (so that $x^2 - a$ has at most two roots for $a\in\Bbb F_p$). Modulo a composite, there can be more. Your mistake comes because $5\equiv -6\pmod {11}$, and $6\equiv-5\pmod{11}$, so you really only found two unique square roots. $\endgroup$
    – Stahl
    Jan 10, 2014 at 0:06
  • $\begingroup$ @Stahl: You're right. I will fix my answer. $\endgroup$
    – Matt Groff
    Jan 10, 2014 at 0:16
  • $\begingroup$ Also, $5$ is not two different values modulo $11$, and $5\not\equiv 6\pmod{11}$: as I said in my above comment, $-5\equiv 6\pmod{11}$. $-5\equiv 6\pmod{11}$ doesn't mean that there are two different values of 6; it means we have two ways of writing the same thing, just like $.99\ldots = 1$ as real numbers. When we write $a\equiv b\pmod n$, we're really saying that when we work in $\Bbb Z/(n)$, $a + n\Bbb Z = b + n\Bbb Z$ (this is one way of defining modular arithmetic). They represent the same element, or value, in the system we're working with, they're simply written differently. $\endgroup$
    – Stahl
    Jan 10, 2014 at 0:16
  • 1
    $\begingroup$ @MattGroff Hi I am learning about the same topic discussed in this post. Can you please explain why we know that our square root is either 5 or 6 modulo 11, and either 4 or 9 modulo 13. Also where do we get the 4 possibilities from. E.g. where do we get 82,126,17 and 61. $\endgroup$
    – Jed
    May 2, 2015 at 18:10
  • $\begingroup$ @Jed: Perhaps the easiest way to see what we're trying to explain is to think of inverses. We can state the additive inverse of $x$ as $y$, and then we have $x \equiv (-1)y$. But if we square $x$, and rewrite this in terms of the inverse $y$, we have $(x)^2 \equiv ((-1)y)^2$, which equals $(-1)^2 y^2$, which, of course, is $y^2$. So we have just shown that the squares of $x$ and its inverse $y$ are the same value. So if we can find any square root, we can call it $x$. Then its inverse, $y$, when squared, is the same value. If we find one square root, its inverse is also a square root. $\endgroup$
    – Matt Groff
    May 4, 2015 at 21:50
3
$\begingroup$

Consider: x≡√3(mod11); x²≡3(mod11); x²≡3+22(mod11); x²≡25(mod11); x≡±5(mod11); So, x=+-5 You can do something similar mod 13.

Let x≡5(mod11);
x≡-5(mod11);
x≡4(mod13);
x≡-4(mod13)

Then use the Chinese Remainder Theorem to find the four values of x (mod 143)

$\endgroup$
2
$\begingroup$

suppose you want to find (x)^(1/2) mod p(prime) then simply calculate (x)^((p+1)/4) mod p. as in your case x=3 and p=11, 3^((11+1)/4)=27= 5 mod 11. similarly -5 will be a root.

$\endgroup$
1
  • 1
    $\begingroup$ This is incomplete. $x^{(p+1)/4}$ is only a square root mod $p$ of $x$ if $p\equiv 3\pmod{4}$ and hence is only applicable in the case $p=11$. This does not work with $p=13$ $\endgroup$ Jun 12, 2023 at 13:52
1
$\begingroup$

Working modulo $11$, using numbers from $0$ to $10$, which ones have the property that their squares are of the form $11k+3$ ? Similarly, modulo $13$, using numbers from $0$ to $12$, which ones have the property that their squares are of the form $13k+3$ ?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .