Denumerable and Induction

1. Show that if A and > are denumerable disjoint sets then A u > is denumerable 2. Show that every set of cardinalty c contains a denumerable subset 3. Show by induction that 6 divides n^3 - n for all n in N

Sets

In each part of this problem, display an example of a set M with the specific property or properties. a) M does not equal R (R is the set of all real numbers), but M is bounded neither above nor below. b) M is bounded above but fails to contain its least upper bound. c) M is the set of integers that contains neither a smallest element nor a largest element. d) M is not a set of integers but nevertheless contains both a smallest and a largest element.

Big O notation

i) Show that x^3 is O(x^4) but x^4 is not O(x^3) ii)Show that xlnx is O(x^2) but x^2 is not O(xlnx) iii)Show that a^x O(b^x) but b^x is not O(a^x) if 0 < a < b (0 = zero) iv)Show that 1^k + 2^k+...+n^k is O(n^(k+1)) for every positive integer k

Recursive algorithms

Write a recursice algorithm to find x^n mod m whenever n,x and m are positive integers based on the fact that : x^n mod m = (x^(x-1) mod m * x mod m)mod m

Congruences

Find all common solutions to the congruences (in the folowin notations the = is meant to be a congruence symbol) x=2(mod 3), x=1(mod 4), x=3(mod 5), x=4(mod 7)