Square roots mod p -- Number Theory 25

[@RexxSchneider]

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]

@@petersievert6830 Thank you for spotting that. Yes, the prime bases should be 7 and 11, as you worked out. If you don't mind, I'll replace: "... we can deduce that x^2 ≡ 55 (mod 5) and x^2 ≡ 55 (mod 7)." etc. with "... we can deduce that x^2 ≡ 55 (mod 11) and x^2 ≡ 55 (mod 7)." etc. so that I don't confuse other viewers.

[@petersievert6830]

@@RexxSchneider Sure. Btw many thanks for the solution :-)

[@conanedojawa4538]

Did professor penn forget to made congruences mod primes ?

[@Tehom1]

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

[@RexxSchneider]

*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).

[@hacatu]

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.

[@boristerbeek319]

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

[@rosiefay7283]

Yes, solving an equation is easy if you already know an answer.

[@boristerbeek319]

@@rosiefay7283 my alternative is far from contrived, seeing 2 and 23 together would quickly evoke the thought of 25 for many others. But then again, it's only an alternative and yes, you can solve this congruence from the ground up like Michael did. Just saves a bit of time by thinking about it briefly

[@goodplacetostop2973]

19:37 Homework 20:12 Good Place To Stop

[@nikoivan2580]

Stop time traveling, this video was uploaded 9 minutes ago

[@megauser8512]

@@nikoivan2580 lol

[@goodplacetostop2973]

@@nikoivan2580 No 😎

[@pauljackson3491]

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

[@MrRyanroberson1]

i'm pretty sure he uses a wide aspect ratio. youtube sets a different player size for each aspect ratio (width/height) of a video. if you ever see a black border, then it's because the video was edited into the aspect ratio that you see the player take, but when there is no border: that's the real way the video was saved.

[@hassanalihusseini1717]

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.

[@MrRyanroberson1]

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}

[@pratapmondal145]

2:37 Shouldn't we have to show that the solution exists first,when p=4k+3?

[@JosBergervoet]

Faster and more straightforward would be: 18^6=(-5)^6=25^3=2^3=8 (mod 23)

[@hhhh2855]

Michael, can you please make a lecture about cryptography?

[@nikoivan2580]

Is this university math level or just "simple" highschool stuff?

[@learnitbyyourself]

Highschool olympiad math

[@nikoivan2580]

@@learnitbyyourself thanks for the answer. But now I'm wondering why I'm not learning this stuff right now in my highschool in Germany?

[@deadfish3789]

These are for a number theory course he teaches at university. You would not get taught this at school. It might come up in olympiads, admittedly, but competitors would need to learn it in their spare time.

[@nikoivan2580]

@@deadfish3789 thank you for your helpful answer

[@mrpenguin815]

This sort of thing was taught in my first year on an undergraduate maths course.

[@da33smith37]

Noticing the Green New Deal T-shirt. In the words of Jordan Peterson, "Intelligence has absolutely zero correlation with wisdom."

[@sonifer7692]

Well that certainly applies to Peterson, but like all of his other bad advice, it doesn't generalise well.

[@da33smith37]

@@sonifer7692 So in your sophistry you are admitting Peterson is intelligent.

[@sonifer7692]

@@da33smith37 I have no doubt that he is intelligent, but that hasn't stopped him from being a dodgy half-arsed guru to the toxic alt-right. Linus Pauling was one of the greatest physicists, but he ended up spouting a lot of bullshit about vitamin C. The difference with Peterson is that he's full of shit in his actual main career.

[@da33smith37]

@@sonifer7692 And yet he thinks about what he says, talks about matters of substance, and doesn't need to use ad hominem insults. You could try that yourself.

[@sonifer7692]

@@da33smith37 well then I apologise for implying that only unwise people could support a Green New Deal in the middle of a mass extinction event.

[@particleonazock2246]

f-f-first?