# 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.

• You can use these \mod, \gcd Feb 7, 2021 at 8:59
• @Mathlover \pmod works better I think. Feb 7, 2021 at 9:00
• @Mathlover $\pmod p$ - Here I used 'pmod p' only inside the dollar signs without any brackets. Feb 7, 2021 at 9:01

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. 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 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$$.

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.

• Well, the statement is that if its possible that $a^2 x \equiv a \mod p$ then you could find that $z \in \mathbb Z$. If the hypothesis isn't true, you cannot continue so is not a counterexample. Feb 7, 2021 at 12:04
• @JavierHerrero Oh, I dind't understand the statement correctly. So, for (b): if $a=p^s$ with $s<r$ then $\langle p^s\rangle$ contains only the multiples of $p^s$ less than $p^r$ since it divides $p^r.$ Similarly, if $2s<r$ then $\langle p^{2s}\rangle$ contains only the multiples of $p^{2s}$ less than $p^r.$ so $p^s\notin\langle p^{2s}\rangle;$ and if $2s\ge r$ then $\langle p^{2s}\rangle$ is just $\{0\},$ and $p^s\notin\{0\}.$ So, if it is verified the hypothesis, either $a$ is a unit or $a$ is $0.$ In that case, you have already solved it. Feb 7, 2021 at 12:16
• Now for (c) we can use (b)! Let $m=p_1^{e_1}p_2^{e_2}...p_n^{e_n}$ where $p_1,p_2,...,p_n$ are different prime numbers. As $a^2x\equiv a \mod m$ for some $x\in\mathbb{Z}$ then the equation $$a^2x\equiv a \mod p_i ^{e_i},$$ with i=1,2,..,n is hold for the same $x,$ so there is for each $p_i, i=1,2,...,n$ there is $z\in\mathbb{Z}$ such that $az^2\equiv a \mod p_i,$ and by the chinese remainder theorem, there is $z\in \mathbb{Z}$ such that $a^2z\equiv a \mod m.$ Feb 7, 2021 at 12:40
• 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.

• if you prove ${p^r}$ then you have proved for any m, as ${p^r}$ is composite for r>1
– SSA
Feb 7, 2021 at 12:04