Hey!

I have a question about solutions of linear congruences with Euclidean algorithm. I'd be very happy if you can help.

9x=1 (mod 16)

What I know is gcd of 9 and 16 is equal to 1 and it divides 1. Thus exists a unique solution.

But I cannot figure out how to find x=9 by Euclidean way.

If someone helps or just tries, thanks in advance