#Help with Euclid’s Algorithm
sturdy mirageBOT
fierce condor
What would you like help with exactly? Do you have an idea of how you would start off?
fierce condor
So, like start off with 135 and try to Euclidean divide that by 59
Where does that lead you to?
fierce condor
So like you mean 135 = 2(59) + 17, yea?
fierce condor
So like you mean 135 = 2(59) + 17, yea?
Cool, then similarly divide 59 by 17 and write it like this is the idea
Yep, then divide 17 by 8
Cool, and therefore, you know the gcd of 135 and 59 is 1, right?
Then the idea is that you work backwards from that - and now you know that d = 1
So then backwards from 1 = 17 - 2(8)
Basically write each of them backwards
So you know that 8 = 59 - 3(17), put that into 1 = 17 - 2(8)
Yep, you keep going until you have 1 = 135s + 59t
Yep, then expand that and collect it in terms of 17 and 59
I meant that you expand the 2(59 - 3(17)) but keep the 17 as is
Keep the 59 as 59 as well btw
And also it should be +6(17)
But otherwise yea and then collect like terms
More that you have 1 = 7(17) - 2(59)
Check that you see why!
Remember here I had that I said:
Keep the 59 as 59 as well btw
And also it should be +6(17)
So what you should get is that 1 = 17 - 2(59) + 6(17)
You agree with me there?
Then do 17 + 6(17) = 7(17)
Yep yep 
fierce condor
So like you mean 135 = 2(59) + 17, yea?
Replace the 17 in 1 = -2(59) + 7(17), using the above
Not yet, there's some simplification to do!
Not quite, be careful!
The 7(135) is fine!
But remember that on expansion it should be 7*-2
Let's check 
,w 7(135) - 16(59)
burnt sorrelBOT
fierce condor
Hmmm, the way I did it was slightly different - I had started on "pebble 0" and then aimed to get to "pebble 1" from jumps, and the problem is equivalent to finding the smallest $j$ such that $21j = 1 \mod(50)$
burnt sorrelBOT
chartbit
fierce condor
It would be quite a lot of jumps you would need, is what I would say
Basically, tl;dr you want to find integers $j,k$ such that $21j +50k = 1$
burnt sorrelBOT
chartbit
fierce condor
Then from there, you want j such that it's positive and less than 50
To do that, you can use the extended Euclidean method as per the last question we did
Also 6 + 21 should be 27 there!
[you're still before the point you cycle back - but note that regardless you will have a very long time going if you were to do it that way!]
yep it's 31 
No worries, it's a pleasure 
happy with all of that then?
Perfect, I might head off to sleep soon then
If you're done with all that, type .solved to mark this as solved!
sturdy mirageBOT
Solved