Square roots mod p -- Number Theory 25

Показать описание

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

Рекомендации по теме

Комментарии

17:40 Fun fact: An even stronger version of this holds. For any field of characteristic 2, everything is a quadratic residue.

Tehom

Spoiler alert.

For those who want to check their working on the warm-ups.

(1) Solve x^2 ≡ 12 (mod 15). We don't have a prime as a base, but we can see that we have to have x^2 ≡ 12 (mod 3) AND x^2 ≡ 12 (mod 5).
If you're not sure about that, then we can rewrite the congruence as x^2 = 12 + 15k. Reducing each side (mod 3) yields the first condition and reducing (mod 5) gives the second.
So we need x^2 ≡ 0 mod 3 (i.e. x is a multiple of 3) AND x^2 ≡ 2 (mod 5). So evaluate (2/5).
From previous work, we know (2/p) = { +1 if p ≡ ±1 (mod 8) OR -1 if p ≡ ±3 (mod 8) }. But 5 ≡ -3 (mod 8), so (2/5) = -1 and there are no solutions to x^2 ≡ 2 (mod 5).
Therefore there are no solutions to x^2 ≡ (12 mod 15).

(2) Solve x^2 ≡ 55 (mod 77). Again we don't have a prime as a base, but we can deduce that x^2 ≡ 55 (mod 11) and x^2 ≡ 55 (mod 7).
So x has to be a multiple of 11 AND x^2 ≡ 55 (mod 7). So x^2 ≡ -1 (mod 7) and we should evaluate (-1/7).
From previous work we know that (-1/p) = { +1 if p ≡ 1 (mod 4) OR -1 if p ≡ 3 (mod 4) }. But 7 ≡ 3 (mod 4), so (-1/7) = -1 and there are no solutions to x^2 ≡ -1 (mod 7).
Therefore there are no solutions to x^2 ≡ 55 (mod 77).

If anyone decided to evaluate (6/7), then it is equal to (2/7) * (3/7).
(2/7) = 1 because 7 ≡ -1 (mod 8).
(3/7) = (-1) * (7/3) by Quadratic Reciprocity because 3 and 7 are both ≡ 3 (mod 4). But (7/3) = (1/3) = 1 because 1 is a quadratic residue of any natural number.
Hence (6/7) = (2/7) * (3/7) = (1) * (-1) * (1) = -1 and there are no solutions to x^2 ≡ 6 (mod 7), as above.

RexxSchneider

For primes that are 1 mod 8, square roots can be found by the Tonelli-Shanks algorithm or Cipolla's algorithm (or possibly by finding generator and solving the discrete log problem, but this is using a harder problem to solve an easier one). I was taught Shanks, but I later found Cipolla and think it's easier to understand. Interestingly, Shanks is usually better but Cipolla is sometimes better.

hacatu

*Six exercises to supplement the warm-ups:*
Ex1: Solution of x^2 ≡ 4 (mod 7). Ex2: Solution of x^2 ≡ 3 (mod 7).
Ex3: Solution of x^2 ≡ 2 (mod 7). Ex4: Solution of x^2 ≡ 2 (mod 13).
Ex5: Solution of x^2 ≡ 3 (mod 13). Ex6: Solution of x^2 ≡ 10 (mod 13).

*Summary of techniques we have so far for solving x^2 ≡ a (mod p).*
If p divides a, (a/p) = 0 by definition. Otherwise, we have:
(n^2/p) = 1 because x^2 ≡ n^2 (mod p) always has solutions x ≡ ± n (mod p).
(a/2) = 1 because x^2 ≡ a (mod 2) always has solutions x ≡ ± 1(mod 2).
(-1/p) = { +1 if p ≡ 1 (mod 4) || -1 if p ≡ 3 (mod 4) }.
(2/p) = { +1 if p ≡ ± 1 (mod 8) || -1 if p ≡ ± 3 (mod 8) }.
(3/p) = { +1 if p ≡ ± 1 (mod 12) || -1 if p ≡ ± 5 (mod 12) }. ** Maybe this one isn't "on the list". **
(p/q).(q/p) = { +1 if p or q ≡ 1 (mod 4) || -1 if p and q ≡ 3 (mod 4) }.
If p ≡ 3 or 7 (mod 8) (same as saying p ≡ 3 (mod 4)), then x^2 ≡ a (mod p) has solutions x ≡ ± a^((p+1)/4) (mod p) if a solution exists.
If p ≡ 5 (mod 8), then x^2 ≡ a (mod p) has solutions either x ≡ ± a^((p+3)/8) (mod p) or x ≡ ± a^((p+3)/8).2^((p-1)/4) (mod p) if a solution exists.
If p ≡ 1 (mod 8), then we have no "easy" solutions.

*Ex1: Solution of x^2 ≡ 4 (mod 7)*
=> (4/7) = 1 because (n^2/p) = 1 and x ≡ ± √(n^2) ≡ ± √a (mod p) will always be a solution.
=> x = ± 2 (mod 7) ≡ 2, 5 (mod 7).

*Ex2: Solution of x^2 ≡ 3 (mod 7)*
=> (3/7) = -1 because 7 ≡ ± 5 (mod 12). Optionally (3/7) = (-1).(7/3) = (-1).(1/3) = (-1).(1) = -1.
=> No solutions exist.

*Ex3: Solution of x^2 ≡ 2 (mod 7)*
=> (2/7) = 1 because 7 ≡ -1 (mod 8), so a solution exists.
Note 7 ≡ 7 (mod 8) (or 7 ≡ 3 (mod 4).
=> x ≡ ± a^((p+1)/4) (mod p) ≡ ± 2^(8/4) (mod 7) ≡ ± 4 (mod 7) ≡ 3, 4 (mod 7).

*Ex4: Solution of x^2 ≡ 2 (mod 13)*
=> (2/13) = -1 because 13 ≡ -3 (mod 8).
=> No solutions exist.

*Ex5: Solution of x^2 ≡ 3 (mod 13)*
=> (3/13) = 1 because 13 ≡ 1 (mod 12). Optionally (3/13) = (1).(13/3) = (1/3) = 1, so a solution exists.
Note 13 ≡ 5 mod 8.
=> x might be ≡ ± a^((p+3)/8) (mod p) ≡ ± 3^(16/8) (mod 13) ≡ ± 9 (mod 13).
Test: (±9)^2 = 81 ≡ 3 (mod 13). So solutions are 4, 9 (mod 13).

*Ex6: Solution of x^2 ≡ 10 (mod 13)*
=> (10/13) = (2/13).(5/13)
(2/13) = -1 because 13 ≡ -3 (mod 8).
(5/13) = (1)(13/5) = (3/5) = (1)(5/3) = (2/3) = (-1) because 3 ≡ 3 (mod 8).
(2/13).(5/13) = (-1).(-1) = 1 so a solution exists.
Note 13 ≡ 5 mod 8.
=> x might be ≡ ± a^((p+3)/8) (mod p) ≡ ± 10^(16/8) (mod 13) ≡ ± 100 ≡ ± 9 (mod 13).
Test: (±9)^2 = 81 ≡ 3 (mod 13). Not a solution.
=> x ≡ ± a^((p+3)/8).2^((p-1)/4) (mod p) ≡ ± 10^(16/8).2^3 (mod 13) ≡ ± 800 ≡ ± 7 (mod 13).
Check: (±7)^2 = 49 ≡ 10 (mod 13). The solutions are x = 6, 7 (mod 13).

RexxSchneider

In order to see that 2 is a perfect square mod 23, we can also note that 2 = 25 (mod 23) = 5².

boristerbeek

Honestly, I feel a little bit stupid after the watching the video. I think I have to watch it again as I did not understand anything.... But thank you also for this one, Prof. Penn.

hassanalihusseini

19:37 Homework
20:12 Good Place To Stop

goodplacetostop

I haven't seen it yet but how come you videos, and a few others, have shrunken screens compared to other Youtubers?
It's like half the width instead of 2/3s and closer to 1/3 the height versus half.

pauljackson

19:05 this makes me think there may be a continuation of this trend (that p = 1 mod 2^n divides into two cases) into mod 16. is there any guarantee we can get if (p = 9 mod 16)?
x^2 = a mod p; p = 9 mod 16
a^((p-1)/2) = 1 mod p
p = 16k + 9
(p-1)/2 = 8k + 4
a^(8k+4) = (a^(2k+1))^4 = 1 mod p
a^(2k+1) comes from the set {1, -1, i, -i}, where i satisfies i^2 = -1 mod p.
if a^(2k+1) is in the set {1, -1} mod p, then this is similar to the case where p = 5 mod 8
a^(2k+2) is in the set {a, -a} mod p. I will define s in just a moment, but: a^(2k+1) being in the set {1, -1} -> x is in the set {a^(k+1), s a^(k+1)}
so the trouble here comes from when a^(4k+2) = -1 = p-1 mod p.
assuming we know i such that i^2 = -1 mod p, then we have a^(2k+1) is in the set {i, -i} mod p
since every prime has a multiplicative inverse for every nonzero element, we know it = 1 mod p has a unique solution.
... else i a^(2k+1) is in the set {1, -1} mod p
let v : v^2 = i mod p
for the case where i a^(2k+1) = -1 mod p, we get that a^(k+1) *iv = x
for the case where i a^(2k+1) = 1 mod p, we get that a^(k+1) *v = x
for each p = 9 mod 16, we need these values:
i : i^2 = -1 mod p
t : it = 1 mod p
notice: (it)i = i = -t mod p; t = -i mod p; t = p-i.
u : u^2 = -i mod p
v : v^2 = i mod p
(iv)^2 = v^2 i^2 = -i mod p; iv is in the set {u, -u} mod p
(iu)^2 = u^2 i^2 = i mod p; iu is in the set {v, -v} mod p
u and -u are interchangeable, as are v and -v. therefore we set iv = u.
finally, for each p = 9 mod 16, we must FIND only these values:
i : i^2 = -1 mod p
v : v^2 = i mod p
from this, we get:
iv = u mod p;
a^(2k+1) is in the set {1, -1, i, -i} mod p; x is in the set {a^(k+1), a^(k+1) * i, a^(k+1) * iv, a^(k+1) * v} mod p.
expressed through "distribute multiplication onto each element of a set" notation:
sqrt(x) is in the set a^(k+1) * {1, i, v, iv} mod p
sqrt(set of possible x)^2 = a^(2k+2) * {1, -1, i, -i} = a * ... mod p
... == a^(2k+1) * {1, -1, i, -1}
...^4 = a^(8k+4) * {1} = a^((p-1)/2) * {1} mod p
so it is sufficient to find any value "v" such that v^2 = i; i^2 = -1 mod p in order to find all four possible square roots of any value, given by the values of a^(k+1) * {1, v, v^2, v^3}

MrRyanroberson