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

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 computey = 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 istotient(145)  1
. Computing a totient is not easy unless you have the primefactorization of the number. Thepow
function hides a loop, but a much shorter loop than bruteforcing the equation.