2
$\begingroup$

Given a positive integer $m$, a prime $p$ and an integer $a$, I would like to prove that $$ x \equiv ay \pmod{p^{2m}} \qquad \lvert x \rvert,\lvert y \rvert \leq p^m $$ always has at least one solution $(x,y)\in\mathbb{Z^2}$ with $x,y$ not both $0$.


I have no problem if $p\mid a$. Indeed: if $\lvert a \rvert \leq p^m$ then $(a,1)$ is a solution, otherwise $p^m\mid a$ and $(0,p^m)$ will do.

If $p\nmid a$ then $a$ is invertible modulo $p^{2m}$, hence $x \equiv ay \pmod{p^{2m}}$ has many non-trivial solution. However, I don't know how to find one with $\lvert x \rvert,\lvert y \rvert \leq p^m$.

$\endgroup$
3
  • $\begingroup$ Hmm. It just occurred to me that there may be a problem in your reasoning when $p\mid a$ and $|a|>p^m$. It does not follow that $p^m\mid a$. For example we might have $a=p^m+p$. $\endgroup$ Sep 5, 2014 at 13:23
  • $\begingroup$ That's right; silly me... $\endgroup$
    – A.P.
    Sep 5, 2014 at 13:28
  • 1
    $\begingroup$ Don't worry about that too much. The way to avoid mistakes is to do all of them (at least) once, and learn from them :-) $\endgroup$ Sep 5, 2014 at 13:30

2 Answers 2

2
$\begingroup$

I think this follows from something resembling the pigeon hole principle as follows.

Fix $a$. We can assume that $p^m\nmid a$ as the case $p^m\mid a$ is easy. Consider the set of smallest non-negative remainders modulo $p^{2m}$ $$ S_a=\{ay\bmod p^{2m}\mid 1\le y\le p^m\}. $$ Observe that there are no repetitions, so $|S_a|=p^m$.

Let us place these $p^m$ pigeons into $p^m$ holes with hole #$j$ consisting of the interval $I_j:=[jp^m, (j+1)p^m-1]$, $0\le j<p^m$. There are two possibilities. Either two or more pigeons try to enter the same hole, or all the holes are occupied by a single pigeon.

If there is no double occupancy, then one of the pigeons flew into the interval $I_0$. If this pigeon carried the coordinate tag $y_0$, this means that the remainder of $ay_0$ is in the range $I_0$, and we have found our solution: the matching $x_0$ is the remainder of $ay_0$ modulo $p^{2m}$.

The other case is that two pigeons, $ay_1$ and $ay_2$, are in the same hole. Without loss of generality we can assume that the remainder of $ay_1$ is smaller than that of $ay_2$. Thus the remainder $r$ of $a(y_2-y_1)$ mod $p^{2m}$ is in the range $0<r<p^m$, and as $0<|y_2-y_1|<p^m$ we have, again, found a solution.

$\endgroup$
6
  • $\begingroup$ Sorry about fumbling with the indices and absolute values for a while. $\endgroup$ Sep 5, 2014 at 13:10
  • $\begingroup$ Sounds nice, thanks. I hope you don't mind if I wait a bit more before accepting the answer. $\endgroup$
    – A.P.
    Sep 5, 2014 at 13:19
  • $\begingroup$ Of course you should wait! There may be something simpler out there. $\endgroup$ Sep 5, 2014 at 13:20
  • $\begingroup$ Absolutely, @Thomas. Thanks for spotting the mistake! $\endgroup$ Sep 5, 2014 at 15:45
  • 1
    $\begingroup$ The proof works more generally for $x=ay\pmod{n^2}$ with $|x|,|y|\leq n$. Probably easier to read without all those exponents, too. $\endgroup$ Sep 5, 2014 at 16:01
-1
$\begingroup$

Put $R=\Bbb Z_{p^m}$ then in $R[x,y]$ the polynomial $x-ay$ has non trivial solutions iff $a \not \equiv 0 \pmod {p^m}$. Suppose $a \equiv 0 \pmod {p^n}$ with $n<m$ then take for $y$ a unit in $R$. It is impossible that $ay=0$ because that would imply that $y \equiv 0 \pmod {p^{m-n}}$ and so $y \equiv 0 \pmod {p}$, and this is a property that units just don't have. If $a \equiv 0 \pmod {p^m}$ then clearly $a=ay=0$.

$\endgroup$
2
  • 2
    $\begingroup$ That doesn't seem to say anything about the solution being in that range, or that the solution lifts to $\mathbb Z_{p^{2m}}$ in some way... $\endgroup$ Sep 5, 2014 at 15:44
  • $\begingroup$ Maybe there is a way to correct my answer and to first replace $m$ by $2m$. Then the problem seems to be to show that there is a unit $<p^m$. $\endgroup$ Sep 5, 2014 at 19:10

You must log in to answer this question.

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