Here is a textbook question that I don't know how to do:
n is an euler pseudoprime to the base b if gcd(b,n)=1 and if n satisfies
$b^{(n-1)/2} = (b/n)$ mod n (legendre symbol)
Questions: Show that $2047 = 2^{11} − 1$ is not an Euler pseudoprime to the base 3 and conclude from this that 2047 is a composite number
This is my problem; I must evaluate the quantity (b/n), however the legendre symbol is only defined for primes (am I right?) therefore, since 2047 is not a prime, how can I solve the question?
Since gcd$(3,2047)=1$ and by definition we have to show that $$3^{(2047-1)/2} \equiv \bigg(\frac{3}{2047}\bigg)\pmod{2047} $$ And $$2047 = 23\cdot89$$ Then $$\bigg(\frac{3}{23}\bigg)\cdot\bigg(\frac{3}{89}\bigg) = -\bigg(\frac{23}{3}\bigg)\cdot\bigg(\frac{89}{3}\bigg)\qquad \text{by law of Quadratic Reciprocity} \\ = -\bigg(\frac{2}{3}\bigg)\cdot\bigg(\frac{2}{3}\bigg) \qquad \qquad \qquad \qquad \qquad \\ $$ By Legendre symbol we have $$\bigg(\frac{2}{3}\bigg)=-1$$ Hence $$\bigg(\frac{3}{23}\bigg)\cdot\bigg(\frac{3}{89}\bigg) = -1$$ Now we have to check whether $$3^{1023} \equiv -1 \pmod{2047} $$ OR $$3^{1024} \equiv -3 \pmod{2047} $$ But $$3^{1024} \not\equiv -3 \pmod{2047} $$ Thus, 2047 is not an Euler pseudoprime to base 3.