# Solving Congruence System for Gödel Beta Predicate

I am given the Gödel Predicate form $B(a,b,i,x) \Leftrightarrow x=a \mod (1+b(i+1))$ where I need to encode a numeral string (e.g. 12345) to the parameters a, b of the Gödel Predicate.

My idea was to use Mathematica to solve the resulting equation system:

FindInstance[2==Mod[a, (1+b (0+1))] && 9==Mod[a, (1+b (1+1))], {a,b}]


but it fails with

FindInstance:The methods available to FindInstance are insufficient to find the requested instances

Which method shall I use instead?

FindRoot gives you some solutions with different inputs:

equation = 2 == Mod[a, (1 + b (0 + 1))] && 9 == Mod[a, (1 + b (1 + 1))];

rt1 = FindRoot[equation, {{a, -1}, {b, 1}}]
(*{a -> -6., b -> 7.}*)

equation /. rt1
(*True*)

rt2 = FindRoot[equation, {{a, -100}, {b, -100}}]
(*{a -> 9., b -> 6.}*)

equation /. rt2
(*True*)


You can use brute-force (works very fast in this case):

Flatten[#, 1] & @
Table[If[2 == Mod[a, (1 + b (0 + 1))] && 9 == Mod[a, (1 + b (1 + 1))], {a, b}, Nothing],
{a, 1, 100}, {b, 1, 100}]


{{9, 6}, {20, 5}, {86, 5}, {100, 6}}

This short plot shows that the solutions are placed on lines in equidistances dependent on the line.

The solutions names above or on the left of the void are not on a line. There are only three of them. So there is a chance that they are on a curve as high as cubic order.

The plot shows the solution up to 500 and therefore 7 lines are shown.

Both solutions sets can be found by FindRoot but a proper set of starting points are in need for that operational process. The really high starting values miss a lot of solutions in between and show only the smallest one.

The method with the verification is very much more robust in the numerical meaning and is very much faster. This speed can only be superseded by making use of the knowledge with positions on straight lines in equidistances.

A nice approach to get the lines is making use of Mathematica built-in graphics tools.