General solution

From Euclid's algorithm we have 1 = 61X98 - 43X139

Hence all solutions are of the form 61 + 139 t where t is any integer.

how does this thought come to mind ?
1 = 61X98 - 43X139

Does it come on reading 98x and mod 139 ?[7]

I mentioned Euclid's algorithm in my post right?

In general such congruences are solved by inspection. Here the number is difficult to guess, so we have to turn to Euclid's algo

The congruence ax \equiv b \pmod c has a solution for any b when gcd (a,c) = 1. This is obvious as Euclid tells us that whenever gcd (a,c) = 1 we have ax₀ + cy₀ = 1 for some integers x₀ and y₀.

So abx₀ + cby₀ = b, so setting x = bx₀ we have the solution.