6.042/18.062J Mathematics for Computer Science February 18,2005
Srini Devadas and Eric Lehman
Notes for Recitation 6
1 The Pulverizer
We saw in lecture that the greatest common divisor (GCD) of two numbers can be written
as a linear combination of them.
1
That is,no matter which pair of integers a and b we are
given,there is always a pair of integer coef?cients s and t such that
gcd(a,b) = sa + tb,
However,the proof was nonconstructive,it didn’t suggest a way for?nding such s and t,
That job is tackled by a mathematical tool that dates to sixth-century India,where it was
called kuttak,which means,The Pulverizer”,Today,the Pulverizer is more commonly
known as,the extended Euclidean GCD algorithm”,but that’s lame,We’re sticking with
“Pulverizer”,
Euclid’s algorithm for?nding the GCD of two numbers relies on repeated application of
the equation,
gcd(a,b) = gcd(b,a rem b)
which was proved in lecture (see the notes,Number Theory I”),For example,we can
compute the GCD of 259 and 70 as follows,
gcd(259,70) = gcd(70,49) since 259 rem 70 = 49
= gcd(49,21) since 70 rem 49 = 21
= gcd(21,7) since 49 rem 21 = 7
= gcd(7,0) since 21 rem 7 = 0
= 7,
The Pulverizer goes through the same steps,but requires some extra bookkeeping along
the way,as we compute gcd(a,b),we keep track of how to write each of the remainders
(49,21,and 7,in the example) as a linear combination of a and b (this is worthwhile,
because our objective is to write the last nonzero remainder,which is the GCD,as such a
1
In fact,we proved that among all positive linear combinations of the numbers their GCD is the smallest,
2 Recitation 6
linear combination),For our example,here is this extra bookkeeping,
x y (x rem y) = x? q · y
259 70 49 = 259? 3 · 70
70 49 21 = 70? 1 · 49
= 70? 1 · (259? 3 · 70)
=?1 · 259 + 4 · 70
49 21 7 = 49? 2 · 21
= (259? 3 · 70)? 2 · (?1 · 259 + 4 · 70)
= 259? 11 · 703 ·
21 7 0
We began by initializing two variables,x = a and y = b,In the?rst two columns above,
we carried out Euclid’s algorithm,At each step,we computed x rem y,which can be
written in the form x? q · y,(Remember that the Division Algorithm says x = q · y + r,
where r is the remainder,We get r = x? q · y by rearranging terms.) Then we replaced x
and y in this equation with equivalent linear combinations of a and b,which we already
had computed,After simplifying,we were left with a linear combination of a and b that
was equal to the remainder as desired,The?nal solution is boxed,
Recitation 6 3
2 Problem,The Pulverizer!
There is a pond,Inside the pond there are n pebbles,arranged in a cycle,A frog is
sitting on one of the pebbles,Whenever he jumps,he lands exactly k pebbles away in
the clockwise direction,where 0 < k < n,The frog’s meal,a delicious worm,lies on the
pebble right next to his,in the clockwise direction,
(a) Describe a situation where the frog can’t reach the worm,
Solution,If k | n (say k = 3 and n = 6),then no number of jumps will lead the frog to
the worm,as the frog will be returning to his original pebble ad in?nitum,
(b) In a situation where the frog can actually reach the worm,explain how to use the
Pulverizer to?nd how many jumps the frog will need,
Solution,Suppose the frog can reach the worm,When he actually reaches it,he has
jumped a number of times,say j,and he has travelled around the cycle a number of times,
call it c,Then,the distance that the frog has covered is both j · k and c · n + 1,so that
jk = cn + 1,
But this means that 1 can be written as a linear combination of n and k,
(?c)n + jk = 1,
Since 1 is positive,we conclude that it is a positive linear combination of n and k,And
since it is the smallest positive integer,we also conclude that it is the smallest positive linear
combination of n and k,But we have proved in lecture that the smallest positive linear
combination of two integers is their GCD,So,the GCD of n and k is 1,
gcd(n,k) = 1
and we can use the Pulverizer to?nd?c and j,
(c) Compute the number of jumps if n = 50 and k = 21,Anything strange?
Solution,We go through the steps as described in Section 1 (see the table below) to get
that 1 = 8 · 50? 19 · 21,or 1 =?(?8) · 50 + (?19) · 21,Hence,c =?8 and j =?19,which
makes little sense,What does it mean for the frog to make?19 jumps?
The point is that the Pulverizer is guaranteed to give us the integers coef?cients of a
linear combination that equals the GCD,but it promises nothing about the signs of those
coef?cients —which,in this case we wanted them to be? and +,To get coef?cients of the
desired sign,we have to think more (and much less after the next lecture),
So,we know 1 = 8 · 50? 19 · 21,Or,to obtain meaningful signs for the numbers,
19 · 21 = 8 · 50? 1,That is,after 19 jumps the frog will have covered 8 full cycles but
1 pebble,So,he will be right next to his original pebble,but in the counter-clockwise
direction,Given this,how can he reach the pebble he is after?
4 Recitation 6
Well,if he makes 19 more jumps,he will land 2 pebbles away from his original position
in the counter-clockwise direction,Another 19 jumps will lead him 3 pebbles away,and
so on,After a total of 49 sets of 19 jumps,he will be 49 pebbles away from its original
position in the counter-clockwise direction,which is of course the worm’s pebble,Then,
the frog will have made 49? 19 = 931 jumps,
Here is the table produced by the Pulverizer,
x y (x rem y) = x? q · y
50 21 8 = 50? 2 · 21
21 8 5 = 21? 2 · 8
= 21? 2 · (50? 2 · 21)
=?2 · 50 + 5 · 21
8 5 3 = 8? 1 · 5
= (50? 2 · 21)? 1 · (?2 · 50 + 5 · 21)
= 3 · 50? 7 · 21
5 3 2 = 5? 1 · 3
= (?2 · 50 + 5 · 21)? 1 · (3 · 50? 7 · 21)
=?5 · 50 + 12 · 21
3 2 1 = 3? 1 · 2
= (3 · 50? 7 · 21)? 1 · (?5 · 50 + 12 · 21)
= 50? 19 · 218 ·
2 1 0
Recitation 6 5
3 Problem,The Fibonacci numbers,Again,
Give an inductive proof that the Fibonacci numbers F
n
and F
n+1
are relatively prime for
all n ≥ 0,Recall that the Fibonacci numbers are de?ned as follows,
F
0
= 0 F
1
= 1 F
n
= F
n?1
+ F
n?2
(for n ≥ 2),
Solution,We use induction on n,Let P(n) be the proposition that F
n
and F
n+1
are
relatively prime,
Base case,P(0) is true because F
0
= 0 and F
1
= 1 are relatively prime,
Inductive step,We show that,for all n ≥ 0,P(n) implies P(n + 1),So,?x some n ≥ 0 and
assume that P(n) is true,that is,F
n
and F
n+1
are relatively prime,We will show that F
n+1
and F
n+2
are relatively prime as well,We will do this by contradiction,
Suppose F
n+1
and F
n+2
are not relatively prime,Then they have a common divisor
d > 1,But then d also divides the linear combination F
n+2
F
n+1
,which actually equals
F
n
,Hence,d > 1 divides both F
n
and F
n+1
,Which implies F
n
,F
n+1
are not relatively
prime,a contradiction to the inductive hypothesis,
Therefore,F
n+1
and F
n+2
are relatively prime,That is,P(n + 1) is true,
The theorem follows by induction,
Recitation 6 6
4 Problem,The power of 3,
Let N be a number whose decimal expansion consists of 3
n
identical digits,Show by
induction that 3
n
| N, For example,
3
2
777777777
|
3
2
= 9 digits
Recall that 3 divides a number iff it divides the sum of its digits,
Solution,We proceed by induction on n,Let P (n) be the proposition that 3
n
| N,
where the decimal expansion of N consists of 3
n
identical digits,
Base case,P (0) is true because 3
0
= 1 divides every number,
Inductive step,Now we show that,for all n ≥ 0,P (n) implies P (n + 1),Fix any n ≥ 0 and
assume P (n) is true,Consider a number whose decimal expansion consists of 3
n+1
copies
of the digit a,
aaaaaa,,, aaaaaa = aaa,,, aaaaaa,,, aaaaaa,,, aaa
3
n+1
digits 3
n
digits 3
n
digits 3
n
digits
= aaa,,, aaa 1 000,,, 001000,,, 001
·
3
n
digits 3
n
digits 3
n
digits
Now 3
n
divides the?rst term by the assumption P (n),and 3 divides the second term
since the digits sum to 3,Therefore,the whole expression is divisible by 3
n+1
,This proves
P (n + 1),
By the principle of induction P (n) is true for all n ≥ 0,
Srini Devadas and Eric Lehman
Notes for Recitation 6
1 The Pulverizer
We saw in lecture that the greatest common divisor (GCD) of two numbers can be written
as a linear combination of them.
1
That is,no matter which pair of integers a and b we are
given,there is always a pair of integer coef?cients s and t such that
gcd(a,b) = sa + tb,
However,the proof was nonconstructive,it didn’t suggest a way for?nding such s and t,
That job is tackled by a mathematical tool that dates to sixth-century India,where it was
called kuttak,which means,The Pulverizer”,Today,the Pulverizer is more commonly
known as,the extended Euclidean GCD algorithm”,but that’s lame,We’re sticking with
“Pulverizer”,
Euclid’s algorithm for?nding the GCD of two numbers relies on repeated application of
the equation,
gcd(a,b) = gcd(b,a rem b)
which was proved in lecture (see the notes,Number Theory I”),For example,we can
compute the GCD of 259 and 70 as follows,
gcd(259,70) = gcd(70,49) since 259 rem 70 = 49
= gcd(49,21) since 70 rem 49 = 21
= gcd(21,7) since 49 rem 21 = 7
= gcd(7,0) since 21 rem 7 = 0
= 7,
The Pulverizer goes through the same steps,but requires some extra bookkeeping along
the way,as we compute gcd(a,b),we keep track of how to write each of the remainders
(49,21,and 7,in the example) as a linear combination of a and b (this is worthwhile,
because our objective is to write the last nonzero remainder,which is the GCD,as such a
1
In fact,we proved that among all positive linear combinations of the numbers their GCD is the smallest,
2 Recitation 6
linear combination),For our example,here is this extra bookkeeping,
x y (x rem y) = x? q · y
259 70 49 = 259? 3 · 70
70 49 21 = 70? 1 · 49
= 70? 1 · (259? 3 · 70)
=?1 · 259 + 4 · 70
49 21 7 = 49? 2 · 21
= (259? 3 · 70)? 2 · (?1 · 259 + 4 · 70)
= 259? 11 · 703 ·
21 7 0
We began by initializing two variables,x = a and y = b,In the?rst two columns above,
we carried out Euclid’s algorithm,At each step,we computed x rem y,which can be
written in the form x? q · y,(Remember that the Division Algorithm says x = q · y + r,
where r is the remainder,We get r = x? q · y by rearranging terms.) Then we replaced x
and y in this equation with equivalent linear combinations of a and b,which we already
had computed,After simplifying,we were left with a linear combination of a and b that
was equal to the remainder as desired,The?nal solution is boxed,
Recitation 6 3
2 Problem,The Pulverizer!
There is a pond,Inside the pond there are n pebbles,arranged in a cycle,A frog is
sitting on one of the pebbles,Whenever he jumps,he lands exactly k pebbles away in
the clockwise direction,where 0 < k < n,The frog’s meal,a delicious worm,lies on the
pebble right next to his,in the clockwise direction,
(a) Describe a situation where the frog can’t reach the worm,
Solution,If k | n (say k = 3 and n = 6),then no number of jumps will lead the frog to
the worm,as the frog will be returning to his original pebble ad in?nitum,
(b) In a situation where the frog can actually reach the worm,explain how to use the
Pulverizer to?nd how many jumps the frog will need,
Solution,Suppose the frog can reach the worm,When he actually reaches it,he has
jumped a number of times,say j,and he has travelled around the cycle a number of times,
call it c,Then,the distance that the frog has covered is both j · k and c · n + 1,so that
jk = cn + 1,
But this means that 1 can be written as a linear combination of n and k,
(?c)n + jk = 1,
Since 1 is positive,we conclude that it is a positive linear combination of n and k,And
since it is the smallest positive integer,we also conclude that it is the smallest positive linear
combination of n and k,But we have proved in lecture that the smallest positive linear
combination of two integers is their GCD,So,the GCD of n and k is 1,
gcd(n,k) = 1
and we can use the Pulverizer to?nd?c and j,
(c) Compute the number of jumps if n = 50 and k = 21,Anything strange?
Solution,We go through the steps as described in Section 1 (see the table below) to get
that 1 = 8 · 50? 19 · 21,or 1 =?(?8) · 50 + (?19) · 21,Hence,c =?8 and j =?19,which
makes little sense,What does it mean for the frog to make?19 jumps?
The point is that the Pulverizer is guaranteed to give us the integers coef?cients of a
linear combination that equals the GCD,but it promises nothing about the signs of those
coef?cients —which,in this case we wanted them to be? and +,To get coef?cients of the
desired sign,we have to think more (and much less after the next lecture),
So,we know 1 = 8 · 50? 19 · 21,Or,to obtain meaningful signs for the numbers,
19 · 21 = 8 · 50? 1,That is,after 19 jumps the frog will have covered 8 full cycles but
1 pebble,So,he will be right next to his original pebble,but in the counter-clockwise
direction,Given this,how can he reach the pebble he is after?
4 Recitation 6
Well,if he makes 19 more jumps,he will land 2 pebbles away from his original position
in the counter-clockwise direction,Another 19 jumps will lead him 3 pebbles away,and
so on,After a total of 49 sets of 19 jumps,he will be 49 pebbles away from its original
position in the counter-clockwise direction,which is of course the worm’s pebble,Then,
the frog will have made 49? 19 = 931 jumps,
Here is the table produced by the Pulverizer,
x y (x rem y) = x? q · y
50 21 8 = 50? 2 · 21
21 8 5 = 21? 2 · 8
= 21? 2 · (50? 2 · 21)
=?2 · 50 + 5 · 21
8 5 3 = 8? 1 · 5
= (50? 2 · 21)? 1 · (?2 · 50 + 5 · 21)
= 3 · 50? 7 · 21
5 3 2 = 5? 1 · 3
= (?2 · 50 + 5 · 21)? 1 · (3 · 50? 7 · 21)
=?5 · 50 + 12 · 21
3 2 1 = 3? 1 · 2
= (3 · 50? 7 · 21)? 1 · (?5 · 50 + 12 · 21)
= 50? 19 · 218 ·
2 1 0
Recitation 6 5
3 Problem,The Fibonacci numbers,Again,
Give an inductive proof that the Fibonacci numbers F
n
and F
n+1
are relatively prime for
all n ≥ 0,Recall that the Fibonacci numbers are de?ned as follows,
F
0
= 0 F
1
= 1 F
n
= F
n?1
+ F
n?2
(for n ≥ 2),
Solution,We use induction on n,Let P(n) be the proposition that F
n
and F
n+1
are
relatively prime,
Base case,P(0) is true because F
0
= 0 and F
1
= 1 are relatively prime,
Inductive step,We show that,for all n ≥ 0,P(n) implies P(n + 1),So,?x some n ≥ 0 and
assume that P(n) is true,that is,F
n
and F
n+1
are relatively prime,We will show that F
n+1
and F
n+2
are relatively prime as well,We will do this by contradiction,
Suppose F
n+1
and F
n+2
are not relatively prime,Then they have a common divisor
d > 1,But then d also divides the linear combination F
n+2
F
n+1
,which actually equals
F
n
,Hence,d > 1 divides both F
n
and F
n+1
,Which implies F
n
,F
n+1
are not relatively
prime,a contradiction to the inductive hypothesis,
Therefore,F
n+1
and F
n+2
are relatively prime,That is,P(n + 1) is true,
The theorem follows by induction,
Recitation 6 6
4 Problem,The power of 3,
Let N be a number whose decimal expansion consists of 3
n
identical digits,Show by
induction that 3
n
| N, For example,
3
2
777777777
|
3
2
= 9 digits
Recall that 3 divides a number iff it divides the sum of its digits,
Solution,We proceed by induction on n,Let P (n) be the proposition that 3
n
| N,
where the decimal expansion of N consists of 3
n
identical digits,
Base case,P (0) is true because 3
0
= 1 divides every number,
Inductive step,Now we show that,for all n ≥ 0,P (n) implies P (n + 1),Fix any n ≥ 0 and
assume P (n) is true,Consider a number whose decimal expansion consists of 3
n+1
copies
of the digit a,
aaaaaa,,, aaaaaa = aaa,,, aaaaaa,,, aaaaaa,,, aaa
3
n+1
digits 3
n
digits 3
n
digits 3
n
digits
= aaa,,, aaa 1 000,,, 001000,,, 001
·
3
n
digits 3
n
digits 3
n
digits
Now 3
n
divides the?rst term by the assumption P (n),and 3 divides the second term
since the digits sum to 3,Therefore,the whole expression is divisible by 3
n+1
,This proves
P (n + 1),
By the principle of induction P (n) is true for all n ≥ 0,
