Given integer Goal and S = { X0, X1, ...., Xn } where Xi is a positive integer > 1, find a, b, in S and positive integer n (not necessarily in S) such that:
a*n mod b = Goal
E.g. Goal = 1, S = {3, 5}, solved by a=3, b=5, n=2:
3*2 mod 5 = 1
I'm trying to write a program to solve* this, but an exhaustive search seems impractical as S can be large (say 10k items) and Xi is a 32-bit integer (I have to account for overflow). I'm looking for an efficient way to solve this.
Note: * I recognize that some sets S will have no solution as the first answer below states. So more completely stated I am trying to build an algorithm that will either solve it, or report there is no solution.
Take $G = 1$, $S = \{2, 4, 6, \ldots\}$. Let $a, b \in S$. If you multiply $a$ by any $n \in \mathbb{N}$ then it is still even and, moreover, $an \pmod{b}$ will be even (with slight abuse of terminology). Therefore you won't be able to solve the congruence equation \begin{equation} an \equiv G \pmod{b}. \end{equation}
You might want to impose some admissibility properties on $S$.
I think you should get a solution whenever $\gcd(a, b)$ divides $G$. I don't know if calculating greatest common divisors is fast enough for you but once you've got those two elements then I'm not sure how to quickly get the value of $n$. It might be fruitful looking at the additive order but I'm not sure. I'll keep thinking.