Thanks! Reading my comment again it's clear I had a brain fart during writing the comment but I was indeed trying to solve: find b such that (a + b) % n == 1.

Thanks! Reading my comment again it's clear I had a brain fart during writing the comment but I was indeed trying to solve: find b such that (a + b) % n == 1. 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?