Question

Evaluate the Legendre Symbol. (19/67)

Answer 1

I could use Euler's Criterion here, but a lot of the previous problems have been relatively easy applications of theorems or were easier to evaluate.

This seems pretty unclean to solve. Is there a combination of two theorems I'm just not seeing?

Answer 2

studied quadratic reciprocity law yet ?

Answer 3

Next question had something on it, I hadn't really looked at it yet. It had some terms I wasn't familiar with

Answer 4

quadratic reciprocity law takes time to understand, it took me 2-3 weeks to properly understand how it works and everything

Answer 5

i said that so you won't approach it thinking it is just another theorem like euler's criterion

Answer 6

Alright then. I'm guessing there's no way to easily break down the problem without it then?

I see this lemma involving sums in the book, is this what we should use?

Answer 7

Where p =67 and a = 19

Answer 8

that looks like a step in the proof of quadratic reciprocity law

Answer 9

You can evaluate ANY legendre symbol in one line with easy arithmetic using quadratic reciprocity law

Answer 10

i don't want this to be your introduction to quadratic reciprocity law if you haven't studied it yet..

Answer 11

Oh wow okay. Would it be worth attempting to learn it now for this assignment or should I wait until I have more time to focus on it?

Answer 12

wait until your professor teaches you officially

Answer 13

Alright, so should I just go through with Euler's Criterion then? Even if it is a bit of a pain?

Answer 14

Or do you see any alternative theorems that could be applied?

Answer 15

With euler's citerion, you need to evaluate\[(19/67)=19^{(67-1)/2}\pmod{67}\]

Answer 16

Right, and those are some pretty big numbers but I can go through it like any other mod problem

Answer 17

yeah i see its not reducing nicely

Answer 18

Is the law of quadratic reciprocity something that can be easily applied if not understood?

Answer 19

notice that both 19 and 67 are of form 4k+3, so\[(19/67)=-(67/19)\]

Answer 20

pretend we can do that,
can you evaluate that legendre symbol ?

Answer 21

-(67/19) should be relatively easy because the modulus is just 19 now

Answer 22

That looks a lot more manageable 1 moment

Answer 23

first reduce 67 in mod 19

Answer 24

Neither of which is too terrible

Answer 25

careful, don't forget the negative..

Answer 26

Right that goes to 10, which could either evailuate at

10^9 mod 19

or

(2/19) (5/19) mod 19

Answer 27

Right

Answer 28

The negative applies to legendre value right? Not what's inside?

Answer 29

So we'll apply that at the end

Answer 30

\[(19/67)=-(67/19)=-(10/19)=-(2/19)(5/19)\]

Answer 31

okay looks good!

Answer 32

with quadratic reciprocity law, you don't really need to work 2^9 and 5^9

Answer 33

apply quadratic reciprocity law for (5/19) again

Answer 34

since 5 is of form 4k+1 :
\[(5/19) = (19/5)\]

Answer 35

Oh okay then, neat. This is pretty useful, thank you.

Answer 36

\[(19/67)=-(67/19)=-(10/19)=-(2/19)(5/19)\\=-(2/19)(19/5)=-(2/19)(-1/5)\\=-(-1)(1)\\=1\]

Answer 37

basically any legendre symbol can be reduced to finding the quadratic residue of one of the integers less than or equal to 3

Answer 38

Yeah, still working through the arithmetic, but I can definitely see how this can help reduce large numbers

Answer 39

Thank you so much for all the help you've been tonight (and previous nights as well haha)

Answer 40

np