Skip to main content
MathOverflow

Return to Question

added 6 characters in body
Source Link
Mak Nazečić-Andrlon
Mak Nazečić-Andrlon
  • 131
  • 4

Characterizing $x y \equiv r \pmod{a^n}$ when $x, y \geq a^$a^{n-1}$ \leq x, y < a^n$

Let $x, y \in \mathbb{Z}$ such that $x, y \geq a^{n-1}$$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.

Characterizing $x y \equiv r \pmod{a^n}$ when $x, y \geq a^{n-1}$

Let $x, y \in \mathbb{Z}$ such that $x, y \geq a^{n-1}$ 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.

Characterizing $x y \equiv r \pmod{a^n}$ when $a^{n-1} \leq x, y < a^n$

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.

Source Link
Mak Nazečić-Andrlon
Mak Nazečić-Andrlon
  • 131
  • 4

Characterizing $x y \equiv r \pmod{a^n}$ when $x, y \geq a^{n-1}$

Let $x, y \in \mathbb{Z}$ such that $x, y \geq a^{n-1}$ 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.