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)
Then to decode 111x73+A=0 (mod 676)
and you can see A=9 works fine.
A "practical" method. Is it OK for you?
By the way, this is the first number theory I've done in ......8 years. Hope it's OK.