2
$\begingroup$

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.

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

3 Answers 3

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 7, 2021 at 12:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Nico2701
    Feb 7, 2021 at 12:16
  • $\begingroup$ 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.$ $\endgroup$
    – Nico2701
    Feb 7, 2021 at 12:40
0
$\begingroup$
  • 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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .