How did you get this?

I ended up with 213x73-23x676=1 at the end of Euclid's algorithm so 73 is fine.

Once you've got the inverse for 213 it's quite easy to finish off.

Just try it out with an easy number, say 0.

y=213x0+111 (mod 676)

y=111

Then to decode 111x73+A=0 (mod 676)

and you can see A=9 works fine.

A "practical" method. Is it OK for you?

I can't explain where you went wrong as I'm afraid I don't understand your working. I don't think you posted enough of it.

By the way, this is the first number theory I've done in ......8 years. Hope it's OK.