We will use the following lemma which is an easy corollary of the chinese remainder theorem and Dirichlet's theorem on primes in arithmetic progressions: Lemma: Let $m_1,...,m_r,M$ be pairwise coprime integers, let $\varphi_1,...,\varphi_r \in \{ \pm 1 \}$ and let $a$ be an integer coprime to $M$. Then there exists a prime $p$ such that $\left( \frac{p}{m_i} \right)=\varphi_i$ for all $i$ and auch that $p \equiv a \mod M$. We will now construct two sequences $a_n$ and $b_n$ such that $a_n$ contains every prime $\equiv 1 \mod 4$ exactly once and $b_n$ does the same for the primes $\equiv 1 \mod 8$ in such a way that mapping $a_i$ to $b_i$ induces an isomorphism of the graphs induced by being quadratic residues: Assume we have found $a_1,...,a_n$ and $b_1,...,b_n$ such that mapping $a_i$ to $b_i$ induces an isomorphism of these finite graphs of $n$ vertices. Then continue in the following way: - If $n$ is even, take $a_{n+1}$ to be the smallest prime $\equiv 1 \mod 4$ not in the set $\{a_1,...,a_n\}$. Then the lemma allows us to find a prime $b_{n+1} \equiv 1 \mod 8$ such that $\left( \frac{b_{n+1}}{b_i} \right) = \left( \frac{a_{n+1}}{a_i} \right) $ for all $i$ (note that especially $b_{n+1} \neq b_i$). By construction, the graphs therefore remain isomorphic after adding these new vertices. - If $n$ is odd, do something similar, but this time choose the smallest prime $ b_{n+1} \equiv 1 \mod 8$ not contained in $\{b_1,...,b_n\}$ and then construct $a_{n+1}$ accordingly. Now its easy to see that we finished our task as we can conclude that: a) $a_n$ contains only primes $\equiv 1 \mod 4$ and $b_n$ contains only primes $\equiv 1 \mod 8$ b) each of $a_n$ and $b_n$ contains every prime at most once c) The $n$-th prime $p \equiv 1 \mod 4$ (ordered by size) is contained in $\{a_1,...,a_{2n}\}$ and the $n$-th prime $p \equiv 1 \mod 8$ is contained in $\{b_1,...,b_{2n}\}$ d) For every $n$ the graphs on $\{a_1,...,a_n\}$ and $\{b_1,...,b_n\}$ are isomorphic with the isomorphism given by sending $a_i$ to $b_i$. a) just says we didn't get any 'wrong' primes, b) and c) imply that every prime occurs exactly once, and d) implies that sending $a_i$ to $b_i$ induces an isomorphism between the graphs on $\{a_1,a_2,...\}$ and $\{b_1,b_2,...\}$, solving the problem.