How to solve for y in formula (y*known_number)%145 = 81 without a loop

Is it possible to solve for y in this equation without a loop?

known_number = 7
(y * known_number) % 145 == 81

I'm using a loop, but i'm thinking since it's simple multiplication, there may be a formula that can be used to solve it without a loop, or is there?

Here is my code i use to solve for it:

known_number = 7
for y in range(145):
   if (y * known_number) % 145 == 81:
       print(y)  # -> 53

1 answer

  • answered 2019-11-14 03:18 harold

    There is an other way, though it has a different kind of loop if you look closely.. anyway, it can be solved like this:

    y*known_number ≡ 81 (mod 145)
    y ≡ 81 * known_number ^ -1 (mod 145)
    

    Which works iff known_number indeed has a modular multiplicative inverse modulo 145, which happens when the GCD between the known number and the modulus is 1 (gcd(7, 145) = 1 so in this case it would work). Here the inverse is 83, so we compute y = 81 * 83 % 145 = 53.

    In general you may find that inverse by using the Extended Euclidean Algorithm, but also through various other methods, for example pow(known_number, 111, 145), where 111 is totient(145) - 1. Computing a totient is not easy unless you have the prime-factorization of the number. The pow function hides a loop, but a much shorter loop than brute-forcing the equation.