Baltic Way 1994 · Problem 6

Solution:

Since the number of congruence classes modulo $q$ is finite, there exist two non-negative integers $i$ and $j$ with $i>j$ which satisfy $2^{i} \equiv 2^{j} \pmod{q}$. Hence, $q$ divides the number $2^{i}-2^{j}=2^{j}\left(2^{i-j}-1\right)$. Since $q$ is odd, $q$ has to divide $2^{i-j}-1$. Now it suffices to multiply the numerator and denominator of the fraction $\frac{p}{q}$ by $\frac{2^{i-j}-1}{q}$.