0

If given $n \in \mathbb{Z}^{+}$, $0 < a < p^n$ and $b \in \mathbb{Z}^{+}$ can I find $x$ such that

$$a\equiv xb\pmod {p^{n}}$$

If anyone has tips for where to further research the background material necessary to tackle this problem that would be sufficient.

trisct
  • 4,896
  • 11
  • 32
Algebra is Awesome
  • 594
  • 2
  • 11
  • 3
    It depends on $b$ and $a.$ If $b$ is relatively prime to $p^n$ then you can always solve it. If $p$ is a divisor of $b$ then $p$ must be a divisor of $a,$ or there is no solution. – Thomas Andrews Sep 04 '19 at 05:49
  • See [here](https://math.stackexchange.com/a/2053174/242) for the general case using modular *fractions*. – Bill Dubuque Sep 04 '19 at 14:03

1 Answers1

0

Answer: if $a$ is a multiple of ${\rm gcd}(b,p^n)$, then yes; otherwise, no. Below, ${\rm gcd}$ means the greatest common divisor.

The tool you are missing is Bezout's identity:

For two nonzero integers $a,b$, there exists integers $x,y$ such that $$ax+by={\rm gcd}(a,b)$$

and its corollary

As $x,y$ both run through every integer, $ax+by$ runs through precisely the multiples of ${\rm gcd}(a,b)$. In other words, each $ax+by$ is a multiple of ${\rm gcd}(a,b)$; conversely, each multiple of ${\rm gcd}(a,b)$ has the form $ax+by$.

Let's return to your original question. Use the corollary you get $$a\equiv bx\pmod{p^n}\text{ has a solution}\\ \iff a-bx=p^ny\text{ for some integers }x,y\\ \iff a\text{ has the form }bx+p^ny\\ \iff a\text{ is a multiple of }{\rm gcd}(b,p^n)$$

trisct
  • 4,896
  • 11
  • 32