M328K Final Exam, May 10, 2003

1. ``Bibonacci'' numbers. The Bibonacci numbers tex2html_wrap_inline34 are defined by tex2html_wrap_inline36 , tex2html_wrap_inline38 , and, for n>2, tex2html_wrap_inline42 .

a) Prove that, for all positive integers n, tex2html_wrap_inline46 .

b) Prove that, for all positive integers n, tex2html_wrap_inline50 .

2. The following theorem-proof combination is erroneous. Find the errors (there are at least two). Then, rewrite the proof (and, if necessary, the statement of the theorem) so that it really does prove the theorem.

``Theorem'' Every positive integer is divisible by a prime.

``Proof'' Let n be a positive integer. If n is prime, then n is divisible by the prime n, and we are done. If n is composite, then n = ab, where a and b are integers less than n. If a is prime, then a|n, and we are done. If a is composite, write a as a product of two smaller integers, and examine the first of these. Repeat this process, dividing composite factors into products of still smaller factors, and examining the first sub-factor, until you get a factor that cannot be divided further, and is therefore prime.

3. Matrix products. It is a known fact that, if A and B are matrices such that the product AB makes sense, then tex2html_wrap_inline84 . (That is, the transpose of the product is the product of the transposes, in the opposite order). Taking this fact as given, prove the following statement:

Claim: Let n > 1 and let tex2html_wrap_inline88 be an ordered n-tuple of matrices such that the product tex2html_wrap_inline92 is defined. Then tex2html_wrap_inline94 , i.e., the transpose of the product is the product of the transposes with the order reversed.

4. a) Find the greatest common factor of 50 and 76.

b) Write this number as a linear combination of 50 and 76.

c) Find all solutions, mod 76, of the equation tex2html_wrap_inline96 .

5. a) Find all solutions, in the range tex2html_wrap_inline98 , to the following system of congruences.

eqnarray16

b) Find all solutions, in the range tex2html_wrap_inline100 , to the system of congruences

eqnarray20

6. a) Compute tex2html_wrap_inline102 (mod 101). (Note that 101 is prime)

b) You are told that tex2html_wrap_inline104 (mod 101) and that tex2html_wrap_inline106 . Find a positive integer d such that tex2html_wrap_inline110 .

c) If y=24, what is x?

7. Let n=8999271. a) What is the prime factorization of n? (Hint: n is the product of more than two primes) You may use your calculators, but you may NOT use a ``factor'' key or function, and you MUST show how you did the factorization in order to receive credit.

b) Compute tex2html_wrap_inline122 .

c) Somebody suggests coding numbers by tex2html_wrap_inline124 , where x is relatively prime to n. Find a key that decodes this (i.e., a number k such that tex2html_wrap_inline132 .


Lorenzo Sadun
Sat May 10 20:34:35 CDT 2003