Proof the Existence of an Integer given $a^2 x \equiv a \pmod m$ In my final abstract algebra exam, I had the following problem I can't solve completely yet. It states the following:
Given $a \in \mathbb Z$, (a) given p is prime, if there exists $x \in \mathbb Z$ such that $a^2 x \equiv a \pmod  p$ then there exists $z \in \mathbb Z$ such that $a^2 z \equiv a \pmod p$ and $az^2 \equiv z \pmod  p$. (b) Same but substituting $p$ with $p^r$. (c) Same but substituting $p$ with any arbitrary number $m$.
I had (a) correct cause is almost trivial; as we are working in $\mathbb F_p$, then $a$ is either unity or zero. If $a=0$, $z=0$ would do the job. Otherwise, we get that $ax \equiv 1 \pmod p$. From this expression, we can just multiply by $x$ and we get $ax^2 \equiv x \pmod  p$. The first equation($a^2 x \equiv a \pmod p$ is given by hypothesis).
For (b), I followed a similar argument. If $a$ is not a power of $p$, as $p$ is prime then $\gcd(p^r,a)=1$ hence $a$ is unity and we can proceed like in (a). If $a$ is not unity, then $a=p^s$. I'm not sure of the next steps; I see then that $p^{2s} x \equiv p^s \pmod  {p^r}$. As $p$ is prime, $x$ needs to be a power of $p$ hence $p^{2s} x \equiv p^s \pmod  {p^r}$. I deduce that $x=p^{rk - s}$. From here, you get that $p^s * p^{2rk-2s} \equiv p^{2rk-s} \equiv p^{-s} \equiv x$. However, I'm not sure of the argument. Moreover, I don't know how to proceed to an arbitrary integer. I would thank any suggestion or hint.
 A: For (b): If $s=r$ we get that $a\equiv0$ and we can take $z=0$ as you noted for the first part. Now assume that $1<s<r$. Then as $p^{2s}x\equiv p^s\mod p^r$ we get $p^r\mid (p^{2s}x-p^s)=p^s(p^sx-1)$. Since $s<r$ this implies $p\mid p^sx-1$ which is a contradiction as $p\nmid 1$. So if $\gcd(p^r,a)\ne1$ then the only possibility for $a^2x\equiv a$ to be satisfied is if $a\equiv0\mod p^r$.
For (c): Let $m=p_1^{r_1}\dots p_k^{r_k}$ and let $a^2x\equiv a\mod m$. This implies $a^2x\equiv a\mod p_i^{r_i}$ for all $i$. Hence there are $z_i$ that satisfy

*

*$a^2z_i\equiv a\mod p_i^{r_i}$

*$az_i^2\equiv z_i\mod p_i^{r_i}$
By the Chinese remainder theorem there is some integer $z$ such that $z\equiv z_i\mod p_i^{r_i}$. Now the congruences $a^2z\equiv a$ and $az^2\equiv z$ are satisfied modulo the $p_i^{r_i}$. It follows that they are also satisfied mod $m$.
A: *

*for answer (a): when ${ax=1 (mod p)}$,  where ${x \equiv a^{-1} (mod p)}$, now say ${a^{-1}=t}$, now the set ${t+np}$, contains the required set, and ${z}$ can be any element from this set.


*for ex. p=5 and then a=3 , ${a^{-1}=2}$, so now, x= 2+5n contains from a set {2,7,12,17,22,27,32,37,42,47,52,57,62,67,72,77...}  = {(n2,n7)...}  nice pair of 2 and 7!


*now for (b) , ${p^r}$you will still have the subset from above bigger set. for ex.. for ${p^2}$ , the set is {27,52,77..}


*for (c) : As ${p^r}$ is composite for r>1, then, it can be prove for any composite m.
A: Is (b)  (so also (c)) false? Take $a=2, p=2$ and $r=2.$ The equation  $$a^2x\equiv a \mod p^r$$ would be $$4x\equiv 2 \mod 4,$$ but $4x$ is just $0$ so there's no solution... or am I missing something?
Also, I think your solution for (a) is correct.
