Modular solution to $ax - by \equiv 0\ (\mathrm{mod}\ p)$?

by Russ   Last Updated August 15, 2018 14:20 PM

Given prime $p$, integers x and y where both $x, y < p$ and $x \neq y$, is there an efficient way to find nontrivial coefficients $a, b$ where $a, b < \sqrt p$ such that

$$ax - by \equiv 0\bmod p$$

If there is no efficient (non-brute force) method, then assume we have many such pairs $a_ix - a_jy \equiv 0\bmod p$; is there an efficient way to find at least one satisfying pair $a_i, a_j$?



Related Questions



How to solve a quadratic modular equation?

Updated April 28, 2017 15:20 PM