Repairing a scratched QR code means finding two polynomials, an error locator and an error evaluator, that satisfy a congruence modulo x^2t. Run extended Euclid on x^2t and the syndrome polynomial and stop halfway, as soon as the remainder drops below degree t, and it hands you both: the remainder is the evaluator and the accumulated coefficient is the locator. ZXing, the open source barcode library, decodes this way in its runEuclideanAlgorithm routine. Polynomials support division with remainder just as integers do, so the algorithm needs no change at all.