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.

Printable View

- Mar 10th 2010, 10:24 AMMathsLegendre 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.

- Mar 10th 2010, 11:07 AMqmech
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. - Mar 10th 2010, 11:42 AMMaths

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

Attachment 15853 - Mar 10th 2010, 12:09 PMchiph588@
- Mar 10th 2010, 12:14 PMchiph588@
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.