Answers to practice problems
1a. Let a,b be natural numbers, a < b. Assume there exist x,y in the naturals such that xa + yb = gcd(a,b). Show y < 10.
A. It depends on whether a=0 or a>0.
If a=0, then the gcd is b. x doesn't matter, and y must be 1. 1 < 10, huzzah.
If a>0, then the largest the gcd can be is a. On the other hand, the smallest positive number that xa+yb can be is a. So both must be a. Hence x=1, y=0. 0 < 10, huzzah redux.
b. Give an example where x > 10.
A. Apparently we're in the a=0 case, since otherwise x would have to be 1.
So y must be 1, and x and b are free to roam. Take x = 57 and b = 1066, for example.
2. What are the last two decimal digits of 112008?
A. 81.
More generally, 11n == 10n + 1 mod 100.
This is easy to prove by induction: multiply both sides by 11, obtaining
11n+1 == 110n + 11 == 10n + 11 == 10(n+1) + 1 mod 100.
3a. Draw an example of finite sets X,Y,Z and functions f:X->Y, g:Y->Z where |X| > |Y|, f is not onto, but the composite g o f is onto.
A. Say X = {a,b,c}, Y = {taupe,vermilion}, Z = {cheese}. Let f(x) = taupe for any x, and g be the only function Y->Z.
b. Prove that |Y| is not equal to |Z| (not just in your example, but in any example).
A. Since g o f is onto, the map image(f) -> Z (made by restricting g) is also onto.
Hence |Z| is less than or equal to |image(f)|. Since image(f) is contained in Y, |image(f)| is less than or equal to |Y|. But f is not onto, so it's strictly contained. Hence |image(f)| < |Y|.
4. In each of the following: can you turn the following two congruences into one, and if so, what?
v1. b congruent to 2 mod 6, b congruent to 7 mod 10.
A. No you can't; the first says b is even, the second says it's odd.
Whereas any single congruence does have solutions.
v2. b congruent to 1 mod 6, b congruent to 7 mod 10.
A. The first can be rewritten as "b congruent to 7 mod 6". Hence 6 and 10 divide b-7, or equivalently, 30 divides b-7. So they can be rewritten as e.g. b-2 congruent to 5 mod 30.
5. Say b == a+7 mod 27, and a2 == b2 mod 27.
Figure out a,b mod 27.
A. a2 - b2 == 0 mod 27.
So (a+b)(a-b) == 0 mod 27.
So (a+b)(-7) == 0 mod 27.
Since gcd(7,27) = 1, we can cancel the 7.
So a+b == 0 mod 27.
So 2a+7 == 0 mod 27.
How to cancel the 2? Subtract 27 from both sides, for example; 2a-20 == 27 == 0 mod 27.
So a-10 == 0 mod 27. Hence a == 10 mod 27, b == 17 == -a mod 27.
A. It depends on whether a=0 or a>0.
If a=0, then the gcd is b. x doesn't matter, and y must be 1. 1 < 10, huzzah.
If a>0, then the largest the gcd can be is a. On the other hand, the smallest positive number that xa+yb can be is a. So both must be a. Hence x=1, y=0. 0 < 10, huzzah redux.
b. Give an example where x > 10.
A. Apparently we're in the a=0 case, since otherwise x would have to be 1.
So y must be 1, and x and b are free to roam. Take x = 57 and b = 1066, for example.
2. What are the last two decimal digits of 112008?
A. 81.
More generally, 11n == 10n + 1 mod 100.
This is easy to prove by induction: multiply both sides by 11, obtaining
11n+1 == 110n + 11 == 10n + 11 == 10(n+1) + 1 mod 100.
3a. Draw an example of finite sets X,Y,Z and functions f:X->Y, g:Y->Z where |X| > |Y|, f is not onto, but the composite g o f is onto.
A. Say X = {a,b,c}, Y = {taupe,vermilion}, Z = {cheese}. Let f(x) = taupe for any x, and g be the only function Y->Z.
b. Prove that |Y| is not equal to |Z| (not just in your example, but in any example).
A. Since g o f is onto, the map image(f) -> Z (made by restricting g) is also onto.
Hence |Z| is less than or equal to |image(f)|. Since image(f) is contained in Y, |image(f)| is less than or equal to |Y|. But f is not onto, so it's strictly contained. Hence |image(f)| < |Y|.
4. In each of the following: can you turn the following two congruences into one, and if so, what?
v1. b congruent to 2 mod 6, b congruent to 7 mod 10.
A. No you can't; the first says b is even, the second says it's odd.
Whereas any single congruence does have solutions.
v2. b congruent to 1 mod 6, b congruent to 7 mod 10.
A. The first can be rewritten as "b congruent to 7 mod 6". Hence 6 and 10 divide b-7, or equivalently, 30 divides b-7. So they can be rewritten as e.g. b-2 congruent to 5 mod 30.
5. Say b == a+7 mod 27, and a2 == b2 mod 27.
Figure out a,b mod 27.
A. a2 - b2 == 0 mod 27.
So (a+b)(a-b) == 0 mod 27.
So (a+b)(-7) == 0 mod 27.
Since gcd(7,27) = 1, we can cancel the 7.
So a+b == 0 mod 27.
So 2a+7 == 0 mod 27.
How to cancel the 2? Subtract 27 from both sides, for example; 2a-20 == 27 == 0 mod 27.
So a-10 == 0 mod 27. Hence a == 10 mod 27, b == 17 == -a mod 27.
posted by Allen Knutson @ 10:32 PM
0 Comments:
Post a Comment
<< Home