0
$\begingroup$

Let $x, y \in \mathbb{Z}$ such that $a^{n-1} \leq x, y < a^n$ for some fixed positive integers $a$ and $n$. Is there a nice characterization of the remainders $r$ satisfying $x y \equiv r \pmod{a^n}$? Further, given $r$, under what conditions does $x y \bmod a^n < r$ hold?

Number theory isn't my specialty, so any pointers would be appreciated. I would ideally be looking for an answer that doesn't rely on factoring, if possible.

Improve this question
$\endgroup$
2
  • $\begingroup$ Since the number of $x,y$ pairs greatly exceeds $a^n$, I would expect most values of $r$ to appear as remainders. Have you tried any experiments? Say, $32\le x,y<64$? $\endgroup$
    – Gerry Myerson
    Commented Apr 11, 2020 at 5:08
  • $\begingroup$ @GerryMyerson Indeed, almost all appear. These are the exceptions I've found, written as $f(a, n)$: $f(2, 2) = \{3\}$, $f(2, 3) = \{5, 7\}$, $f(2, 4) = \{11, 13\}$, $f(2, 5) = \{19, 29\}$. They're primes, which makes sense that some should appear. But for higher $a$ or $n$, it seems to always come up with every possible $r$. $\endgroup$
    – Mak Nazečić-Andrlon
    Commented Apr 11, 2020 at 7:49

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .