$f(x)\bmod b$: solve for $ x$

Solution 1:

$\!\bmod \color{#0a0}{a^2}\!: \overbrace{\color{#c00}f(\color{#c00}f(x)) \equiv x}^{\large f(x) \,:=\, ax^2-x+a}\!\!\!,\ $ so $\,\ f(x)\equiv y\iff x\equiv f(y),\,$ by $\,\color{#c00}{f\ \text{self-inverse}}$.

$\!\bmod \color{darkorange}2\!:\ \ a\equiv 1,\,\ x^2\equiv x\,\Rightarrow\, f(x)\equiv 1\,$ so $\,f(x)\equiv y\,$ is solvable $\!\iff\! y$ is odd.

So by $\,\gcd(\color{darkorange}2,\color{#0a0}a^2)\!=\!1,\,$ CRT $\Rightarrow f(x)\equiv y\pmod{\!\color{darkorange}2\color{#0a0}{a^2}}\,$ is solvable $\!\iff\! y\,$ is odd, with solution $\,x\equiv f(y)\pmod{\!a^2}\,$ or, equivalently, $\, x\,\equiv\, f(y),\ f(y)\!+\!a^2\pmod{\!2a^2}$

Remark $ $ Though it is easy to verify by calculation that $\,f\,$ is self-inverse, it can be viewed more generally as the special case $\,g(x)= x^2+1\,$ of the following simple self-inverse criterion, which shows that the self-inverse $\,f(x)\equiv -x\pmod{\!a}\,$ has a lift $\,f(x)\equiv -x+a\:\!g(x)\pmod{a^2}\,$ that persists self-inverse $\!\iff\! g(x)\,$ is even $\!\bmod a,\,$ i.e. $\,g(-x)\equiv g(x)\pmod{\!a}$.

$\begin{align}{\bf Lemma}\quad\ \ \color{0darkorange}{\rm if}\ \ &y\equiv f(x)\ {\overset{\rm\color{darkorange} H}\equiv}\:\! -x+a\:\!g(x)\!\! \pmod{\!a^2},\ \ {\rm for}\ g\in \Bbb Z[x]\\[.2em] {\rm then}\ \ & x\equiv f(y)\!\!\!\pmod{\!a^2}\!\iff\! g(-x)\equiv g(x)\!\!\!\pmod{\!a}\end{align}$

$\begin{align}{\bf Proof}_{\,1}\ &\bmod \color{#c00}a^2\!:\,\ 0 \equiv \color{#c00}a(g(f(x))-g(x))\equiv f(f(x))-x\,\\[-.1em] \overset{{\rm cancel}\ \color{#c00}a}\iff\ \ &\bmod a\!:\,\ \ \ 0 \ \,\equiv\,\ g(\color{#0a0}{f(x)})-g(x) \equiv g(\color{#0a0}{-x})-g(x)\ \ {\rm by}\ \ \color{#0a0}{f(x)\equiv -x} \end{align}$

$\begin{align} {\bf Proof}_{\,2}\quad\ \color{0darkorange}{\rm if}\ \ \ &0\equiv f(x)-y\:\!\ \smash[t]{{\overset{\rm\color{darkorange} H}\equiv}} -x-y+a\:\!g(x)\pmod{a^2}\\[.2em] {\rm then}\ \ \ &0 \equiv f(y)-x = -y-x+a\:\!g(y),\,\ \ \rm so\ subtracting\\[.2em] \iff\ &0\equiv a(g(x)-g(y)),\, {\rm but} \ a(\color{#0a0}{x+y})\ \smash[t]{{\overset{\rm\color{darkorange} H}\equiv}}\:\!\ a^2g(x)\equiv 0,\ \rm so \\[.2em] \smash[t]{\overset{\rm\color{#0af} R}\iff}\ \ &0\equiv a(g(x)-g(\color{#c00}y)\ \ \,\bmod\ \ \color{#0a0}{x+y})\\[.2em] \iff\ &0\equiv a(g(x)-g(\color{#c00}{-x}))\ \ {\rm by}\ \ \color{#c00}{y\equiv -x}\!\!\!\pmod{\!\color{#0a0}{x+y}}\\[.2em] \iff\ &0\equiv\ \ \ g(x)-g(-x)\!\!\pmod{\!a},\ \ {\rm by\ cancelling}\,\ a \end{align}$

by $\,\rm\color{#0af} R\!:\:$ if $\,a\color{#0a0}e\equiv 0\,$ and $\,n\equiv \bar n\pmod{\!\color{#0a0}e}\,$ then $\,an\equiv 0\!\iff\! a\bar n\equiv 0\,$ [order Reduction], where above we have $\,\color{#0a0}{e=x+y},\,$ $\,n = g(x)-g(y),\,$ $\,\bar n := n\bmod e$.

Solution 2:

Let's first consider the slightly different congruence $y\equiv ax^2+a-x\pmod{a^2}$ rather than $\pmod{2a^2}$.

Every $x\pmod{a^2}$ can be uniquely written as $x=av-w$ where $0\le v\le a-1$ and $0\le w\le a-1$. (The strange choice of $av-w$ rather than $av+w$ makes a later formula come out more nicely in hindsight.) Using this substitution gives \begin{align*} ax^2+a-x &= a(av-w)^2+a-(av-w) \\ &= a^3 v^2- a^2(2 v w)+a (w^2+1-v)+w \\ &\equiv a (w^2+1-v)+w \pmod{a^2}. \end{align*} So if we want to see what value of $x$ yields a particular value of $y\pmod{a^2}$, we can write $y=as+t$ for some $0\le s\le a-1$ and $0\le t\le a-1$. Then we should set $w=t$ and (after a tiny bit of algebra) $v \equiv t^2+1-s\pmod{a^2}$.

If we want to reach a particular odd value of $y\pmod{2a^2}$, we should use the above recipe if $1\le y\le a^2$, or the above recipe applied to $y'=y-a^2$.