If a∣m and (a+1)∣m, prove a(a+1)|m.

Using the Euclid-Wallis algorithm (described below)

10100012341−482−29713−131↑7−231000⋆

lookng below the horizotal line, the top row times 100 plus the middle row times 23 equals the bottom row. Therefore, the arrow column says that

3⋅100−13⋅23=1

Furthermore, the top and middle numbers in each column are relatively prime. Therefore, the star column gives the smallest combination of 100 and 23 that equals 0. Add arbitrary multiples of the star column to a particular multiple of the arrow column to get all solutions for a particular problem. Since we want a result of −19, add arbitrary multiples of the star column to −19 times the arrow column:

−19=(−19⋅3−23k)100+(−19⋅−13+100k)23=(−57−23k)100+(247+100k)23

This gives all the integer solutions. Thus, x=−57−23k=12−23(k+3)=12+23n where n=−k−3.

---

Euclid-Wallis Algorithm This algorithm computes gcd(m,n), solves the Diophantine equation mx+ny=gcd(m,n), and yields the continued fraction for m/n.
Start with the two columns

10m01n(1)

Above each successive column write down the floor of the quotient of the base of the previous column divided into the base of the column before that, then compute the next column by subtracting that number times the previous column from the column before that. Let us work an example; m=17,n=23:

Above each successive columnwrite down the floor of thequotient of the base of theprevious column divided into thebase of the column before that101701230←⌊17/23⌋10170123010171←⌊23/17⌋10170123010171−1162←⌊17/6⌋→↙→↙→Compute the next column bysubtracting that number timesthe previous column from thecolumn before that1017012301017←1−0⋅0←0−0⋅1←17−0⋅2310170123010171−116←0−1⋅1←1−1⋅0←23−1⋅1710170123010171−11623−25←1−2⋅−1←0−2⋅1←17−2⋅6⋮

10170123010171−11623−251−431523−170(2)

The red column (preceding the blue one with 0 at its base) has gcd(m,n) at its base. Also, m times the top row plus n times the middle row equals the bottom row. Thus, the red column (with gcd(m,n) at its base) has the coefficients for mx+ny=gcd(m,n) in the top two rows. Also, the blue column (with 0 at its base) has the smallest non-zero solution to mx+ny=0. Multiples of this solution can be added to a particular solution of mx+ny=k to get all solutions.
The orange quotients above the columns yield the continued fraction for m/n.
Thus,

gcd(17,23)=1(−4+23k)17+(3−17k)23=1

and the continued fraction for 17/23 is [0,1,2,1,5].

---

Euclidean Algorithm (plus bookkeeping)
The algorithm above is simply the Euclidean algorithm in the top and bottom rows, with some bookkeeping in the two middle rows. The quotients are in the top row and the remainders (which, as dictated by the Euclidean Algorithm, later become divisors and then dividends) are in the bottom row.
In (2), the first dividend is 17 and the first divisor is 23. The first quotient is 0 and the remainder is 17. In the next pass, the dividend is 23 (which was the previous divisor) and the divisor is 17 (which was the previous remainder). The second quotient is 1 and the remainder is 6. In the third pass the dividend is 17 and the divisor is 6, which yields a quotient of 2 and a remainder of 5. This proceeds until a remainder of 0 appears. The algorithm has to stop here since the next divisor would be 0.
The bookkeeping in the middle two rows mimics the computation performed in the bottom row. That is, below the line, the third column is first column minus 0 times the second column. The fourth column is the second column minus 1 times the third column. The fifth column is the third column minus two times the fourth column. This bookkeeping assures that the first row below the line times 17 plus the second row times 23 equals the bottom row. This allows us to back out the Euclidean algorithm at the same time we are performing it.