Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

So I'm a programmer and have reduced solving some problem to finding values x and y such that $x+y*A \equiv B \pmod{2^{32}}$ with the requirement that $x<2^{16}$, $y<2^{16}$, and $\gcd(A,2^{32}) = 1$.

Intuitively, it seems like there should only be one pair $(x,y)$ which satisfies this equation. This looks like a linear algebra problem of writing $B$ in terms of the basis vectors $1$ and $A$ multiplying by coefficients $x$ and $y$. In practice, it also turns out that just by brute forcing over all $2*2^{16}$ values I do get only one solution.

This is perfectly fine as a solution, but it's bothering me that I can't figure out why there is only one $(x,y)$ pair.

Also, is there some closed-form solution to find $x$ and $y$ faster than brute force?

share|improve this question
    
Obviously if $A=1$ and $B$ is, e.g., $2^{16}-1$ then there are $2^16$ solutions. On the other hand for $A=1$, $B=2^18$ there are no solutions. If $A$ is $2^{16}$ times an odd number plus a very small number, then this should be true for most values of $B$. –  Will Sawin Oct 5 '12 at 21:33
2  
try math.stackexchange.com/questions –  Will Jagy Oct 5 '12 at 22:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.