Finding Integer Solutions Worksheet With Answer Key - 7th Grade, Serin Hong Page 4
ADVERTISEMENT
1
2
3
4
5
6Math 7 Spring 2016
Instructor: Serin Hong
Hence we have gcd(F
, F ) = gcd(F , F
), where the latter was seen to be 1 in class.
+2
1
Therefore we conclude that gcd(F
, F ) = 1 for all n
1.
+2
(b) (10 pts) Show that gcd(F
, F ) = gcd(F , 2) for n
1.
+3
Solution. For n = 1, direct computation gives gcd(F
, F ) = gcd(F
, F
) = 1 and gcd(F , 2) =
+3
4
1
gcd(F
, 2) = 1.
1
Now for n
2, the recurrence relation yields
F
= F
+ F
+3
+2
+1
= (F
+ F ) + F = 2F
+ F
+1
+1
= 2(F + F
) + F = 3F + 2F
.
1
1
This implies that gcd(F
, F ) = gcd(F , 2F
). We also obtain gcd(F , 2F
) = gcd(F , 2)
+3
1
1
using the fact gcd(F , F
) = 1 from lecture. Combining these two identities gives the desired
1
identity gcd(F
, F ) = gcd(F , 2).
+3
(c) (5 pts) Use (b) to prove that F
is an even number for m
1.
3
Solution. We prove by induction on m.
For m = 1, we directly find that F
= F
= F
+ F
= 2 is an even number.
3
3
1
2
For the inductive step, we assume that F
is an even number. We want to prove that F
3
3( +1)
is also an even number. Since F
is an even number, we have gcd(F
, 2) = 2. Then (b) yields
3
3
gcd(F
, F
) = gcd(F
, 2) = 2. Hence we see that F
is divisible by 2, completing the
3( +1)
3
3
3( +1)
inductive step.
Extra Credit Problem.
1
a
The Calkin-Wilf tree is a tree obtained by starting with the fraction 1 =
and iteratively adding
1
a + b
a + b
a
and
below each fraction
as “children”.
b
b
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education