1. ## Legendre symbols

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

$\displaystyle (\frac{a}{r})=+1$

and

$\displaystyle [(\frac{a+1}{r})=-1$

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

2. 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.

3. 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:

4. 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.
$\displaystyle \left(\frac{2}{7}\right)=1$

$\displaystyle \left(\frac{2+1}{7}\right)=\left(\frac{3}{7}\right )=-1$

so our hypothesis is satisfied in this case.

5. If our hypothesis was false, then that would mean $\displaystyle \left(\frac{a}{r}\right)=1 \implies \left(\frac{a+1}{r}\right)=1$.

We know $\displaystyle \left(\frac{1}{r}\right)=1$, so that would mean $\displaystyle \left(\frac{2}{r}\right)=1 \implies \left(\frac{3}{r}\right)=1 ...$ an so on.

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