1
$\begingroup$

This question already has an answer here:

I already proved this is true for all prime numbers and clearly see how this is true for all perfect squares, I'm just having trouble expanding it to any prime factorization. If we let $a$ have prime factorization $a=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$, then since the Legendre Symbol is multiplicative, we know that: $$ \left(\frac{a}{p}\right)=\left(\frac{p_1}{p}\right)^{a_1}\left(\frac{p_2}{p}\right)^{a_2}...\left(\frac{p_n}{p}\right)^{a_n} $$ I don't, however, understand where to go from here.

$\endgroup$

marked as duplicate by lulu, Watson, JavaMan, Lord Shark the Unknown, user10354138 Dec 12 '18 at 6:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I didn't think so but why not? $\endgroup$ – joseph Dec 10 '18 at 13:30
  • $\begingroup$ Thanks for sharing that link @lulu. Can someone explain the first idea a little more? I got lost with how the author came up with $\frac{f(k f(0) p_1 ... p_n))}{f(0)}$ and how it proves the proposition $\endgroup$ – joseph Dec 10 '18 at 13:40
  • 1
    $\begingroup$ Actually, provided $a$ is not a multiple of $p$ you can extract any square factors of $a$ before you start so that you can assume that $a_i=1$. $\endgroup$ – Mark Bennet Dec 10 '18 at 13:43
  • $\begingroup$ @mjoseph If $f(0)=0$ then the claim is trivial so suppose $f(0)\neq 0$. Write $f(x)=g(x)+f(0)$, note that $x\,|\,g(x)$. Thus $g(kf(0)p_1\cdots p_n)$ is divisible by $f(0)p_1\cdots p_n$. say that $g(kf(0)p_1\cdots p_n)=m\times f(0)p_1\cdots p_n$. Dividing by $f(0)$ we get that $\frac {f(kf(0)p_1\cdots p_n)}{f(0)}=m\times p_1\cdots p_n+1$ which is obviously prime to each of the $p_i$. Thus any prime which divides it has to be a new prime to add to the list. $\endgroup$ – lulu Dec 10 '18 at 13:50
1
$\begingroup$

Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $a\in\mathbb{N}^+$ there is some prime $p$ such that $p\equiv{1}\pmod{4}$ and $p\equiv 1\pmod{a}$. For such a prime $$ \left(\frac{a}{p}\right)=\left(\frac{p}{a}\right)=\left(\frac{1}{a}\right)=1.$$

Yet another overkill: by Chebotarev's density theorem the polynomial $x^2-a$ has a root in $\mathbb{F}_p$ for approximately half the primes $p$. In particular an $a\in\mathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.

$\endgroup$

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