Use Euclid's algorithm to find integer solutions of the given equation, and hence find the solutions of the congruence equations that are also given

(a) 127a + 583b = 1, 127x $\displaystyle \equiv$ mod 583

I seem to need a lot of working to solve these and was just wondering if I was performing everything correctly/efficiently (reasonably).

My working:

I drew out the GCD working so I could work backwards:

583 = 4x127 + 75

127 = 75 + 52

75 = 52 + 23

23 = 3x6 + 5

6 = 5 + 1

5 = 5x1 + 0

$\displaystyle \therefore$ GCD = 1

Then I worked backwards to find integer values for x and y:

1 = 6 - 5

= 6 - (23 - 3x6)

= 4x6 - 23

= 4(52 - 2x23) - (75 - 52)

= 5x52 - 8x23 - 75

= 5(127 - 75) - 8(75 -52) - 75

= 5x127 - 14x75 + 8x52

= 5x127 -14(583 - 4x127) + 8(127 - 75)

= 69x127 - 14x583 - 8(583 - 4x127)

= 101x127 - 22x583

$\displaystyle \therefore$ a = 101 and b = -22

Is that normal to have to do that much for everyone one of these? I'm not complaining, just wondering if I'm missing something

For the second part, I'm not quite sure what I need to do...