I am not sure what Euclid's algorithm in the title of the question is referring to, but as Marc van Leeuwen says, polynomial long division is the way to go. Since doing it by hand is asked about, I will suggest the following based on long experience of doing such divisions by hand and making many mistakes along the way by not being careful.
Use ruled paper for your work, turning it through a right angle so that the lines are vertical rather than horizontal. Then, write one symbol per column to keep things aligned properly. The calculation is exactly as shown in ego's answer but has vertical ruled lines between the bits so that you can keep things properly aligned. Yes, the problem can be solved easily without this artifice in this instance, but the simple trick is very helpful when dealing with polynomials of larger degree.