Consider that I've a mathematical equation of the form: $$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$ How can I solve this modular equation by using a program, efficiently? By trial and error, one can infer that the answer is $x=4,15,26,...$. But how can I solve this programmatically?

I can not use a binary search here, as there is no pattern followed by numbers greater than the answer, and vice versa.( Plus, there are infinite solutions).

I can obviously check all values from $0,1,2,...,21$, but that wouldn't be efficient in my use case.

So, for a given equation of the form $$(a+b\times x)mod\text{ }m=0$$, is there any constant or logarithmic algorithm in $m$, that can be used to solve this equation?

P.S: I can't directly solve for $$a+bx=m$$. For example take $$(6+10\times x)mod\text{ }22=0$$ Here, $x=6$, is the correct answer which can't be inferred using the equation mentioned above.

  • $\begingroup$ Why not simply use symbolic computation? $\endgroup$ – dkaeae Jun 7 '19 at 8:54
  • $\begingroup$ @dkaeae How does that help? And would it be efficient? $\endgroup$ – Mooncrater Jun 7 '19 at 9:03
  • 1
    $\begingroup$ That's what the big math toolboxes do. $\endgroup$ – dkaeae Jun 7 '19 at 9:11
  • $\begingroup$ I can't use foreign math toolboxes, sorry if my question didn't clarify that. This is a subproblem of a competitive programming question, so all code must be, written by me, short and obviously, efficient. $\endgroup$ – Mooncrater Jun 7 '19 at 9:13
  • 1
    $\begingroup$ This is essentially an exercise in modular arithmetic. $\endgroup$ – Yuval Filmus Jun 7 '19 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.