linear congruence by euclidean algorithm

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 :)

Re: linear congruence by euclidean algorithm

Re: linear congruence by euclidean algorithm

Thank you, but I need to solve it by euclidean algorithm. Can you also solve by this way please?