Prove that there are infinitely many prime numbers $p$ such that $left(frac{a}{p}right)=1$ for fixed $a$....
This question already has an answer here:
Infinitely many primes for quadratic residues
1 answer
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.
number-theory legendre-symbol
asked Dec 10 '18 at 13:24
mjoseph
859
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.
add a comment |
This question already has an answer here:
Infinitely many primes for quadratic residues
1 answer
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.
number-theory legendre-symbol
asked Dec 10 '18 at 13:24
mjoseph
859
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.
I didn't think so but why not?
– mjoseph
Dec 10 '18 at 13:30
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
– mjoseph
Dec 10 '18 at 13:40
1
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$.
– Mark Bennet
Dec 10 '18 at 13:43
@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_1cdots p_n)$ is divisible by $f(0)p_1cdots p_n$. say that $g(kf(0)p_1cdots p_n)=mtimes f(0)p_1cdots p_n$. Dividing by $f(0)$ we get that $frac {f(kf(0)p_1cdots p_n)}{f(0)}=mtimes p_1cdots 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.
– lulu
Dec 10 '18 at 13:50
add a comment |
This question already has an answer here:
Infinitely many primes for quadratic residues
1 answer
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.
number-theory legendre-symbol
asked Dec 10 '18 at 13:24
mjoseph
859
This question already has an answer here:
Infinitely many primes for quadratic residues
1 answer
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.
This question already has an answer here:
Infinitely many primes for quadratic residues
1 answer
number-theory legendre-symbol
number-theory legendre-symbol
asked Dec 10 '18 at 13:24
mjoseph
859
asked Dec 10 '18 at 13:24
mjoseph
859
asked Dec 10 '18 at 13:24
mjoseph
859
asked Dec 10 '18 at 13:24
mjoseph
859
asked Dec 10 '18 at 13:24
mjoseph
859
859
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.
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.
I didn't think so but why not?
– mjoseph
Dec 10 '18 at 13:30
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
– mjoseph
Dec 10 '18 at 13:40
1
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$.
– Mark Bennet
Dec 10 '18 at 13:43
@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_1cdots p_n)$ is divisible by $f(0)p_1cdots p_n$. say that $g(kf(0)p_1cdots p_n)=mtimes f(0)p_1cdots p_n$. Dividing by $f(0)$ we get that $frac {f(kf(0)p_1cdots p_n)}{f(0)}=mtimes p_1cdots 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.
– lulu
Dec 10 '18 at 13:50
add a comment |
I didn't think so but why not?
– mjoseph
Dec 10 '18 at 13:30
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
– mjoseph
Dec 10 '18 at 13:40
1
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$.
– Mark Bennet
Dec 10 '18 at 13:43
@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_1cdots p_n)$ is divisible by $f(0)p_1cdots p_n$. say that $g(kf(0)p_1cdots p_n)=mtimes f(0)p_1cdots p_n$. Dividing by $f(0)$ we get that $frac {f(kf(0)p_1cdots p_n)}{f(0)}=mtimes p_1cdots 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.
– lulu
Dec 10 '18 at 13:50
I didn't think so but why not?
– mjoseph
Dec 10 '18 at 13:30
I didn't think so but why not?
– mjoseph
Dec 10 '18 at 13:30
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
– mjoseph
Dec 10 '18 at 13:40
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
– mjoseph
Dec 10 '18 at 13:40
1
1
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$.
– Mark Bennet
Dec 10 '18 at 13:43
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$.
– Mark Bennet
Dec 10 '18 at 13:43
@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_1cdots p_n)$ is divisible by $f(0)p_1cdots p_n$. say that $g(kf(0)p_1cdots p_n)=mtimes f(0)p_1cdots p_n$. Dividing by $f(0)$ we get that $frac {f(kf(0)p_1cdots p_n)}{f(0)}=mtimes p_1cdots 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.
– lulu
Dec 10 '18 at 13:50
@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_1cdots p_n)$ is divisible by $f(0)p_1cdots p_n$. say that $g(kf(0)p_1cdots p_n)=mtimes f(0)p_1cdots p_n$. Dividing by $f(0)$ we get that $frac {f(kf(0)p_1cdots p_n)}{f(0)}=mtimes p_1cdots 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.
– lulu
Dec 10 '18 at 13:50
add a comment |
1 Answer
1
active
oldest
votes
Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $ainmathbb{N}^+$ there is some prime $p$ such that $pequiv{1}pmod{4}$ and $pequiv 1pmod{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 $ainmathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $ainmathbb{N}^+$ there is some prime $p$ such that $pequiv{1}pmod{4}$ and $pequiv 1pmod{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 $ainmathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
add a comment |
Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $ainmathbb{N}^+$ there is some prime $p$ such that $pequiv{1}pmod{4}$ and $pequiv 1pmod{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 $ainmathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
add a comment |
Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $ainmathbb{N}^+$ there is some prime $p$ such that $pequiv{1}pmod{4}$ and $pequiv 1pmod{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 $ainmathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $ainmathbb{N}^+$ there is some prime $p$ such that $pequiv{1}pmod{4}$ and $pequiv 1pmod{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 $ainmathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
answered Dec 10 '18 at 16:35
Jack D'Aurizio
287k33279656
287k33279656
add a comment |
add a comment |
I didn't think so but why not?
– mjoseph
Dec 10 '18 at 13:30
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
– mjoseph
Dec 10 '18 at 13:40
1
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$.
– Mark Bennet
Dec 10 '18 at 13:43
@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_1cdots p_n)$ is divisible by $f(0)p_1cdots p_n$. say that $g(kf(0)p_1cdots p_n)=mtimes f(0)p_1cdots p_n$. Dividing by $f(0)$ we get that $frac {f(kf(0)p_1cdots p_n)}{f(0)}=mtimes p_1cdots 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.
– lulu
Dec 10 '18 at 13:50