# Solving a modular equation programmatically

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.

• Why not simply use symbolic computation? – dkaeae Jun 7 '19 at 8:54
• @dkaeae How does that help? And would it be efficient? – Mooncrater Jun 7 '19 at 9:03
• That's what the big math toolboxes do. – dkaeae Jun 7 '19 at 9:11
• 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. – Mooncrater Jun 7 '19 at 9:13
• This is essentially an exercise in modular arithmetic. – Yuval Filmus Jun 7 '19 at 9:29