Math 2200-2 Exam 2

Math 2200-2
Exam 2
Instructions: NO CALCULATORS, NO TEXTBOOKS. Solve the following exercises. To get full credit for one exercise it is not enough to give the correct answer,
but you have to show how you got it. Strive to be tidy and, when possible, make
sure to circle your answer. Please, do not use a red-ink pen. 3 minutes rule: You
have 3 minutes to turn in the quiz from the moment I tell you to give them back,
afterward I will start taking away points for any minute you further delay.
First and Last Name:
UnID:
5
1. Is the set of all bit strings (strings of zeroes and ones) not containing the bit 0 countable
or uncountable? If it is countable write a one to one correspondence between this set
and the set Z+ .
Solution: This set is countable. Infact let us call it B and consider the function
f : B → Z+ that to each string b ∈ B assigns its number of digit plus one, that
is f (b) = “number of digits in b+1”. This is certainly a function, because given
a string there is jut one output value possible. Now observe that B is the set of
strings that are either empty or consist just of ones. Two such strings have the
same number of digits if and only if they are the same string. Thus f is 1-1. It is
also surjective. Infact the preimage of 1 is the empty string λ given any n > 1, it
is the image of the string
n−1 times
z }| {
1...1 .
1
2
2. Extracredit!!! Give an example of two uncountable sets A and B such that A ∩ B
is finite
Solution: Take, for example, A = [0, 1), B = (−1, 0]. We learned in class that
these are uncountable, but A ∩ B = {0} is certainly finite.
10
3. Show that if two sets A and B have the same cardinality, then |A| ≤ |B| and |B| ≤ |A|.
Hint: Use the definition of having the same cardinality and having less or equal
cardinality.
Solution: Since A and B have the same cardinality we have a bijective function
(1-1 correspondence) f : A → B. In particular f is a 1-1 function and therefore,
by definition |A| ≤ |B|. Since f is bijective, it admits and inverse function f −1 :
B → A. Also f −1 is bijective and, in particular is an injunction. We have, by
definition, that |B| ≤ |A|.
4. Suppose that a is a integer a ≡ 4(mod7) and b is an integer b ≡ 3(mod7). Find an
integer c, 0 ≤ c ≤ 6, such that
5
(a) c ≡ 3a(mod7)
5
(b) c ≡ a2 − b(mod7)
Solution: (a) c ≡ 3a(mod7) ≡ 12(mod7). Therfore c = 12 mod 7 = 5
(b) c ≡ a2 − b(mod7) ≡ 13(mod7). Therfore c = 13 mod 7 = 6
10
5. Prove or disprove: if p and q are prime, both greater than 2, then p + q is composite.
Solution: The statement is true!
Proof. Observe that if p and q are primes greater than 2, then they are both odd
(an even number greater than 2 is composite because it is divisible by 2). Thus
p + q is an even integer. Furthermore, since both p and q are greater than q, then
p + q is greater than 2. We conclude that p + q is an even number greater than 2:
it is composite.
Page 2 of 7
6. Use the Euclidean algorithm to find
5
(a) gcd(44, 52)
5
(b) gcd(31, 57)
Solution: (a)
52 = 44 + 8
44 = 5 · 8 + 4
8=2·4+0
The greatest common divisor is 4
(b)
57 = 31 + 26
31 = 26 + 5
26 = 5 · 5 + 1
5=1·5+0
The greatest common divisor is 1
Page 3 of 7
7. Using the above exercise, find, if possible
5
(a) the multiplicative inverse of 44 in Z52 ;
5
(b) the multiplicative inverse of 31 in Z57 . Give a solution of 31x ≡ 2(mod57).
If it is not possible explain why.
Solution: (a) It is not possible to find the multiplicative inverse of 44 in Z52
since, by the above exercise 44 and 52 are not relatively prime.
(b) We use the extended Euclidean algorithm and the computation in the above
exercise.
1 = 26 − 5 · 5 = 26 − 5(31 − 26) = 6 · 26 − 5 · 31 = 6(57 − 31) − 5 · 31 =
= (−11) · 31 + 6 · 57.
The multiplicative inverse of 31 in Z57 is −11 mod 57 = 46. The only solution
of the aforementioned congruence in Z57 is −22 mod 57 = 35. Other acceptable
solution are −22, 92 etc.
10
8. Use Fermat’s little theorem to find 845 mod3.
Solution: Observe that 45 is congruent to 1 modulus 2. Using Fermat’s Little
Theorem we have that 845 mod3 = 8mod3 = 2.
9. Prove using Induction that for every positive integer n, the following property:
P (n) = “1 + 3 + 5 + · · · + 2n − 1 = n2 ”.
Use the following steps as guideline.
2
(a) Write P (1). Is it true?
2
(b) Write P (k).
2
(c) Write P (k + 1).
4
(d) Perform the Inductive Step.
Solution: (a) P (1) reads “1 = 12 ”, that is obviously true.
P
(b) P (k) is ki=1 2i − 1 = k 2 .
Page 4 of 7
(c) P (k + 1) is
(d)
k+1
X
i=1
Pk+1
i=1
2i − 1 = (k + 1)2 .
2i − 1 =
k
X
IH
2i − 1 + 2k + 1 = k 2 + 2k + 1 = (k + 1)2 .
i=1
10 10. Use Mathematical Induction to prove that 2|(n2 + 3n) for every integer n ≥ 1. Can
you give also a different proof (for 3 points extracredit)?
Solution: The BASIC STEP is 2|12 + 3 that is 2|4 and it is trivilly true.
Let us prove the INDUCTIVE STEP: suppose that 2|k 2 + 3k and let us prove that
2|(k + 1)2 + 3(k + 1). First of all we rewrite (k + 1)2 + 3(k + 1) in the following
manner:
(k + 1)2 + 3(k + 1) = k 2 + 2k + 1 + 3k + 3 + k 2 + k + 2k + 4 = k 2 + 3k + 2(k + 2)
Since 2 obviously divides 2(k + 2) and the INDUCTIVE HYPOTHESIS tells us
that 2 divides k 2 + 3k we have that 2 divides the rightmost hand side above, and
thus it divides (k + 1)2 + 3(k + 1).
Without induction: Observe that if n is odd, then both 3n and n2 are odd
(this comes from the fact that if 2 (a prime) divides 3n since 2 and 3 are relatively
primes, it must divide n). Thus their sum is even.
On the other side if n is even both n2 and 3n are even and their sum is even too.
10 11. Suppose that there exist only $3 and $10 bills. Show using strong induction that you
can still pay any amount greater or equal $18. (You can also use regular induction for
9 points)
Solution: We want to show that andy n ≥ 18 can be written as n = 3s + 10t with
s and t non-negative integers. The BASIC STEP of this strong induction consists
in proving the theorem for n = 18, 19, 20. Now 18 is 6 · 3, thus P (18) is true. In
the same way 19 = 3 · 3 + 10 and 20 = 2 · 10. This ends the basic step. For what
it concerns the INDUCTIVE STEP, suppose that k + 1 > 20 and that for every
18 ≤ j ≤ k the statement is true. In particular it is true for k + 1 − 3, since this
latter number is certainly smaller than k + 1 and bigger or equal 18 (remember:
Page 5 of 7
we can assume that k + 1 > 20, since we proved the statement for values smaller
or equal 20 in the basic step). Therefore we can write
k + 1 − 3 = 3s0 + 10t
with s0 and t non-negative integers. By adding 3 to both sides we get
k + 1 = 3(s0 + 1) + 10t
with s0 + 1 and t non-negative integers.
5 12. Find the error in the following proof of this “theorem”:
“Theorem: Every positive integer equals the next largest positive integer.”
“Proof : Let P (n) be the proposition “n = n + 1”. To show that P (k) → P (k + 1),
assume that P (k) is true for some k, so that k = k + 1. Add 1 to both sides of this
equation to obtain k + 1 = k + 2, which is P (k + 1). Therefore P (k) → P (k + 1) is
true. Hence P (n) is true for all positive integers n.”
Solution: The Basic Step was not performed!!!
Page 6 of 7
Question
Points
1
5
2
2
3
10
4
10
5
10
6
10
7
10
8
10
9
10
10
10
11
10
12
5
Total:
102
Page 7 of 7
Score

Download Report