# Minimum of $5^a x$ modulo $2^b$ for $1 \leq x < 2^c$

Given positive integers $a$, $b$, and $c$, and the function $f(x) = (5^a x)\ \%\ 2^b$, where $x\ \%\ y = x - y\lfloor \frac{x}{y} \rfloor$, what is the minimum of $f(x)$ the range $1 \leq x < 2^c$, with $x$ also integer?

Alternatively, given the inequality $(5^a x)\ \%\ 2^b < 2^d$, what is the minimum $x$ such that this is true?

This can be 'trivially' computed by trying all possible values for x, but I'm interested in cases where $a$, $b$, and $c$ are all large such that it is not possible to try all possible values of $x$ in reasonable time. I have run a couple of examples with a program I wrote:

$a = 43, b = 97, c = 27: \mathrm{min}\ f(x) = 723839456393370823360$ $a = 44, b = 99, c = 27: \mathrm{min}\ f(x) = 31872086829510029993510$

I have looked for various combinations of product, congruence, and inequality, minimum on Google as well as here. I've tried Wolfram Alpha, which didn't give me anything useful (e.g. link).

At this point I'm not even sure there is a better solution than brute force $O(2^c)$. Even if there's no direct way to compute the result, I'd also accept an algorithm that takes less than linear time (e.g., $O(\sqrt{2^c})$ or $O(log(2^c))$).

 BigInteger pow5 = BigInteger.valueOf(5).pow(28); BigInteger pow2 = BigInteger.ONE.shiftLeft(17); BigInteger max = BigInteger.ONE.shiftLeft(11); BigInteger min3 = BigInteger.ZERO; BigInteger pow5inv = pow5.modInverse(pow2); BigInteger a = pow5.mod(pow2); BigInteger b = pow2.mod(a); outer: while (true) { while (b.compareTo(a) > 0) { b = b.mod(a); } while (a.compareTo(b) > 0) { // Note that this loop implements a = a.mod(b), but does so step by step. a = a.subtract(b); BigInteger orig = a.multiply(p5inv).mod(pow2); if (orig.compareTo(max) > 0) { break outer; } min = a; } }