# Isomorphism between quotient rings

Given a positive integer $n$ and some $a \in \mathbb{Z}/n\mathbb{Z}$, I want to know if there always exists a ring isomorphism $\phi$ between the two rings: $$\frac{\frac{\mathbb{Z}}{n\mathbb{Z}}[X]}{\langle X^2-1\rangle} \text{and} \frac{\frac{\mathbb{Z}}{n\mathbb{Z}}[X]}{\langle X^2-a\rangle}.$$

I haven't been able to find a counter-example, but I haven't been able to prove this either. Any clue anyone?

Side note - My interest in this problem stems from integer factorization algorithms. If the above isomorphism exists and can be computed efficiently, then we can get a randomized polynomial time algorithm for factorising $n$.

## 2 Answers

$n = 3$, $a = 0$ is a counter-example.

You can check manually that the quotient by $x^2-1$ has no elements $\alpha$ such that $\alpha^2 =0$.

But the quotient by $x^2$ does, namely the image of $x$ under the quotient.

For a general class of counterexample: Choose $n$ and $a$ so that $x^2 -a$ has no roots in $\mathbb{Z}_n$ and $n$ is prime. Then the quotient by $x^2-a$ is a field while the quotient by $x^2-1$ has zero divisors.

Let's consider the case $n=p$, an odd prime. In this case I'll write $\Bbb F_p$ for $\Bbb Z/n\Bbb Z$. Then $\Bbb F_p[X]/(X^2-1)$ is always isomorphic to $\Bbb F_p\times\Bbb F_p$. If $a=b^2$ is a quadratic residue modulo $p$, then so is $\Bbb F_p[X]/(X^2-b^2)$. On the other hand, if $a$ is a quadratic non-residue then $\Bbb F_p[X]/(X^2-a)$ is isomorphic to the finite field of order $p^2$ and so not to $\Bbb F_p[X]/(X^2-1)$. Finally, $\Bbb F_p[X]/(x^2-0)$ has nontrivial nilpotents so isn't isomorphic to anything we've yet seen.

When $n$ isn't a prime, then things get more complicated. I won't give the full story but just a few cases. This reduces by Chinese remaindering to when $n$ is a prime power. So let $n=p^r$ where $p$ is an odd prime, and I'll take $p\nmid a$ for simplicity. In the case where $a$ is a quadratic residue mod $p$ we have $(\Bbb Z/n\Bbb Z)[X]/(x^2-a)\cong\Bbb (Z/n\Bbb Z)^2$. When $a$ is a quadratic non-residue $R=(\Bbb Z/n\Bbb Z)[X]/(x^2-a)$ has an interesting structure: it is a Galois algebra. It is a local ring containing $\Bbb Z/n\Bbb Z$ as its prime subring, but $R$ factored out by $pR$, which is its maximal ideal, is the finite field of order $p^2$.