2
$\begingroup$

I want to show that if $N$ is a square free odd integer then there is some number coprime to $N$ such that the Jacobi Symbol $(\frac{a}{N}) = -1 $

Honestly I don't even know how to start showing this.

I know that for every odd prime $p$ there are $\frac{p-1}{2}$ quadratic residues$\pmod p$.

Taking the factorisation $N = p_1\dots p_k$ of distinct primes then, maybe I could argue that there's something that isn't a quadratic residue to an odd number of the prime factors. However, I can't quite see how I might manage something like that.

$\endgroup$
1
$\begingroup$

Hint: choose $a$ so that $$ \begin{align*} a&\equiv1\pmod{p_1}\\ a&\equiv1\pmod{p_2}\\ &\cdots\\ a&\equiv1\pmod{p_{k-1}}\\ a&\equiv b\pmod{p_k} \end{align*} $$ where $b$ is not a square modulo $p_k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.