Question

Determine if 83 divides 2^41 +1 using quadratic results of quadratic residues

Answer 1

I can pretty easily go through and set up a congruent like x = 2^41+1 mod 83 and reduce that to x = 0 to show that there's no remainder

But with quadratic residues I'm not sure what residues to point out.

If I set up x-1 = 2^41 mod 83 I find that this mirrors the euler's criterion ie

(2/41) = 2^41 mod 83

But I'm not sure of the relevance.

Answer 2

Little fermat gives us
\[2^{82}\equiv1 \pmod{83}\]
or
\[2^{82}-1\equiv 0 \pmod{83}\]
factor and get
\[(2^{41}-1)(2^{41}+1)\equiv 0\pmod{83}\]

Answer 3

Because \(83\) is a prime, it follows that
\(2^{41}-1\equiv 0\pmod{83}\) or \(2^{41}+1\equiv 0\pmod{83}\)

Answer 4

Notice that first congruence is same as the euler's criterion
if the first congruence held, then \(2\) is a quadratic residue of \(83\)

Answer 5

if we could show that \(2\) is "not" a quadratic residue of \(83\), then thats same as proving that the first congruence does not hold.

that lets us to conclude that the second congruence holds.

Answer 6

Oohhh okay

Answer 7

That makes a lot of sense

Answer 8

so try and show that "2" is not a quadratic residue of 83

Answer 9

Right

Answer 10

I'm gunna go through and do that since I get it from there. I've got 1 last problem I was stuck on after this. I know I've bothered you a whole bunch today, but would you mind looking at it?

Answer 11

sure, but wiat
do u know how to test whether "2" is a quadratic residue or not ?

Answer 12

You may use below to evaluate the legendre symbol (2/p) :\[(2/p) = (-1)^{(p^2-1)/8}\]

Answer 13

There was a book problem asking a similar problem, I was just going to take a look at that

Answer 14

Right that looks familiar.

Answer 15

Okay

Answer 16

@ganeshie8 Sorry, lost connection to openstudy :c

Answer 17

The question is:

Let p>= 5 havequadratic residues a1 a2.... a(p-1)/2 prove that p divides the sum from i = 1 to (p-1)/2 of ai

Answer 18

^There's a terrible drawing if my written way of putting it wasn't clear

Answer 19

Notice that the quadratic residues of \(p\) are precicely the integers from set:\[\{1^2, 2^2, ...,((p-1)/2)^2\}\]

Therefore the sum
\[\sum\limits_{i=1}^{(p-1)/2}a_i \]
is same as
\[\sum\limits_{i=1}^{(p-1)/2}i^2 \]

Answer 20

whats the sum of squares of first (p-1)/2 integers ?

Answer 21

I'm sorry, I'm just not seeing it

Answer 22

Oh wait. There's this sum thing. One moment

Answer 23

Yeah, the sum from 1 to n of i^2 is n(n+1)(2n+1)/6

Answer 24

Is that what you're hinting at? Cause I imagine that simplifies out nicely.

Answer 25

yes, plugin n=(p-1)/2

Answer 26

Alright then, that's pretty clever. Thank you.

Answer 27

You're always super helpful, I really do appreciate it.

Answer 28

np:)