000RM.dvi

206 Greatest common divisor

Exercise

1.Find the gcd of the following pairs of numbers by completing the

second column of each table.

Express the gcd as an integer combination of the given numbers by

completing the last two columns.

rk qk xk yk

54321 ∗∗∗ 1 0

12345 0 1

rk qk xk yk

267914296 ∗∗∗ 1 0

196418 0 1

2.Find the immediate neighbors of^1331 inF 31.

3.Find the immediate neighbors of the fraction^12 in the Farey se-

quenceFn.

4.Somebody received a check, calling for a certain amount of money

in dollars and cents. When he went to cash the check, the teller

made a mistake and paid him the amount which was written as

cents, in dollars, and vice versa. Later, after spending $ 3.50, he

suddenly realized that he had twice the amount of the money the

check called for. What was the amount on the check?