is a perfect square. On the other hand, it is also known (see [@mordell], [@schinzel]) that a primitive congruence class $n = r \mod q$ which is a perfect square, cannot be solved by polynomials (this also follows from Proposition \[odd\]). The next proposition classifies all solvable primitive congruences.

\[res-class\] Let $q \mod r$ be a primitive residue class. If this class is Type I solvable by polynomials, then all sufficiently large primes in this class belong to one of the following sets:

-   $\{ n = -f \mod 4ad\}$, where $a,d,f \in {\mathbb{N}}$ are such that $f|4a^2 d+1$. [@nakayama]

-   $\{ n = -f \mod 4ac \} \cap \{n = -c/a \mod f \}$, where $a,c,f \in {\mathbb{N}}$ are such that $(4ac,f)=1$.

-   $\{ n = -f \mod 4cd \} \cap \{n^2 = -4c^2d \mod f \}$, where $c,d,f \in {\mathbb{N}}$ are such that $(4cd,f)=1$.

-   $\{ n = -1/e \mod 4ab \}$, where $a,b,e \in {\mathbb{N}}$ are such that $e \mid a+b$ and $(e,4ab)=1$. [@aigner], [@rosati]

Conversely, any residue class in one of the above four sets is solvable by polynomials.

Similarly, $q \mod r$ is Type II solvable by polynomials if and only if it is a 