Thread: Legendre symbols

hi, can somebody please help me with the following proof:

Let r be an odd prime. Show that there is an integer a such that



and




I know i need to consider the smallest positive quadratic nonresidue
mod r.

The first condition by itself is easy - try a=1.

[Something seems wrong if both conditions must hold at the same time - try r=7. The numbers mod 7 are 1,2,3,4,5,6 whose quadratic residues are:
1,4,2,2,4,1 and it doesn't look like any of them satisfy your 2 conditions.]

Ignore the above - misinterpreted the Legendre symbol.

Originally Posted by qmech

the first condition by itself is easy - try a=1.

Something seems wrong if both conditions must hold at the same time - try r=7. The numbers mod 7 are 1,2,3,4,5,6 whose quadratic residues are:
1,4,2,2,4,1 and it doesn't look like any of them satisfy your 2 conditions.

both of the condtions have to hold at the same time, since the definition states that:

Originally Posted by qmech

The first condition by itself is easy - try a=1.

Something seems wrong if both conditions must hold at the same time - try r=7. The numbers mod 7 are 1,2,3,4,5,6 whose quadratic residues are:
1,4,2,2,4,1 and it doesn't look like any of them satisfy your 2 conditions.

so our hypothesis is satisfied in this case.

If our hypothesis was false, then that would mean .

We know , so that would mean an so on.

So we've just shown that every number is a square modulo which is a contradiction.