# Infinite graph with Legendre symbol .

Consider a (kind of) infinite oriented graph as follows :

1.The vertexes represent the prime numbers $p>2$ .

2.We draw an oriented edge from $p$ to $q$ if $\left(\frac{p}{q} \right )=1$ (this is the Legendre symbol ) . Note that we are allowed to have both orientations between two primes .

Prove that this graph is connected in the sense that if $p$ and $q$ are two primes then there are (at least) two oriented paths between them : one from $p$ to $q$ and one from $q$ to $p$ .

If you want a challenge : Find other interesting properties of this graph . Or maybe prove that the corresponding graph with the Jacobi symbol (this time between all numbers $>1$ ) is connected .

I have no idea how to prove this so I ask here for help .

Thanks to anyone who tries to solve these awesome problems .

Fix $p$ and $q$, distinct odd primes. Let's break it down to a couple of cases:

Case 1: $p$ and $q$ are both $3 \pmod{4}$.

Then $\left(\frac{p}{q} \right) = - \left(\frac{q}{p} \right)$ by quadratic reciprocity. Thus, we may assume without loss of generality that $\left(\frac{p}{q} \right) = -1$. Since Dirichlet's Theorem tells us that there is a prime $r$ satisfying $r \equiv 1 \pmod{4pq}$ (in fact it tells us that there are infinitely of them. Chinese remainder theorem tells us that $r \equiv 1 \pmod{4}$, $r \equiv 1 \pmod{p}$, and $r \equiv 1 \pmod{q}$, since $p,q$, and $r$ are coprime. We thus have that $$\left(\frac{p}{r} \right) = \left(\frac{r}{p} \right) = \left(\frac{1}{p} \right) = 1.$$ where the first is by Quadratic Reciprocity (recall $r \equiv 1\pmod{4}$), and the second is due to the fact that $r \equiv 1 \pmod{p}$. Thus there is an oriented edge from $p$ to $r$. Similarly, we have $$\left(\frac{r}{q} \right) = \left(\frac{1}{q} \right) = 1.$$ Thus there is an edge from $r$ to $q$. There is thus a path from $p$ to $r$ to $q$. Recall that $\left(\frac{q}{p} \right) = 1$ by Quadratic reciprocity so this completes the first case.

Case 2: Either $p$ or $q$ is $1 \pmod{4}$.

Then $\left(\frac{p}{q} \right) = \left(\frac{q}{p} \right)$. If both Legendre symbols are $1$, then we are done. Thus, we may assume that both are $-1$. Similarly, find a prime $r \equiv 1 \pmod{4pq}$. Then by the above logic, we have $$\left(\frac{p}{r} \right) = \left(\frac{r}{p} \right) = \left(\frac{1}{p} \right) = 1.$$ Similarly, $$\left(\frac{r}{q} \right) = \left(\frac{1}{q} \right) = 1.$$

Thus, we have a path from $p$ to $r$ to $q$. Since $r \equiv 1\pmod{4}$, these edges can be reversed by Quadratic Reciprocity, competing the proof.

• Thanks for the proof , it's very helpful . It seems that the same method works also for Jacobi symbols . Thanks again .
– user252450
Nov 2, 2015 at 17:23