Is finding b such that (a * b) % n really that much work?
It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
That only has a solution if a is relatively prime to n, and generally the best way to find that solution is to use the extended Euclidean algorithm [1].
Briefly because a and n are relatively prime, there exists integers x and y such that ax + ny = 1 [2]. The extended Euclidean algorithm finds x and y. But ax + ny mod n is just ax mod n, and so we have ax = 1 mod n. The b we seek is x.
[1] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
Of course, assume a and n are relatively prime.
Then this is equivalent to finding a b such that (a % n + b % n) % n == 1.
We already know that 0 < a % n < n so simply picking b = n + 1 - a % n works. In fact, b = zn + 1 - a % n for any positive integer z works.
Your solution makes sense to me too but I wonder if I'm missing something obvious above?