#1: a) Let a, b, c be integers and x is congruent to y (mod m). Prove that ax^2+bx+c is congruent to ay^2+by+c (mod m).
b) Show that the result in part a may be false if a, b, c are not all integers, even if ax^2+bx+c and ay^2+by+c are both integers.
#2: Let p: X --> Y and q: Y -->Z be functions such that (q(p)): X-->Z is onto. Prove that q is onto and give an example to show that p need not be onto.
#3: Give an algebraic proof to show that nCr = (n-1) C (r-1) + (n-1)C r.
These are a little bit confusing. I am stuck on these problems.
I can help you with these problems. Let's go through each one step by step and explain how to approach them.
#1:
a) To prove that ax^2 + bx + c is congruent to ay^2 + by + c (mod m), we need to show that their difference is divisible by m. We can start by subtracting the two expressions:
(ax^2 + bx + c) - (ay^2 + by + c) = ax^2 - ay^2 + bx - by = a(x^2 - y^2) + b(x - y).
Now, factor out (x - y) from this expression:
a(x - y)(x + y) + b(x - y).
Since x is congruent to y (mod m), we have x - y is divisible by m. Therefore, a(x - y)(x + y) and b(x - y) are both divisible by m. Hence, ax^2 + bx + c is congruent to ay^2 + by + c (mod m).
b) In this part, we have to find an example where ax^2 + bx + c is congruent to ay^2 + by + c (mod m), but ax^2 + bx + c and ay^2 + by + c are not both integers. One such example is when m = 2, a = 1/2, b = 1/2, c = 1, x = 0, and y = 1. In this case, ax^2 + bx + c = 1/2(0)^2 + 1/2(0) + 1 = 1, and ay^2 + by + c = 1/2(1)^2 + 1/2(1) + 1 = 2. Both expressions are congruent to each other modulo 2, but they are not both integers.
#2:
To prove that q is onto, we need to show that for every z in Z, there exists an x in X such that q(p(x)) = z. Since (q(p)): X --> Z is onto, there exists y in Y such that q(p(x)) = y. Now, for this y, we can use the onto property of p: X --> Y to find an x in X such that p(x) = y. Therefore, we have q(p(x)) = q(y) = z, which shows that q is onto.
For an example where p need not be onto, consider the following functions:
p: X --> Y, where p(x) = x^2
q: Y --> Z, where q(y) = y.
In this case, (q(p)): X --> Z, which means q(p(x)) = x^2 for every x in X, is onto. However, p: X --> Y is not onto since there are elements in Y (negative numbers) that do not have any preimages in X.
#3:
To prove nCr = (n-1) C (r-1) + (n-1)C r algebraically, we can start with the formula for choosing r items from n items:
nCr = n! / (r!(n-r)!).
Now, let's simplify the right side of the equation:
(n-1) C (r-1) + (n-1)C r = (n-1)! / ((r-1)!(n-r)!) + (n-1)! / (r!(n-r-1)!).
To combine the two fractions, we need a common denominator, which is r!(n-r)!(n-r-1)!. Multiplying the first fraction by (n-r) / (n-r) and the second fraction by r / r, we can obtain:
[(n-1)!(n-r) + (n-1)!r] / (r!(n-r)!(n-r-1)!).
Now, let's simplify the numerator:
[(n-1)!(n-r) + (n-1)!r] = (n-1)!(n-r + r) = (n-1)!n.
Substituting this back into the expression:
(n-1)!n / (r!(n-r)!(n-r-1)!) = n! / (r!(n-r)!).
This is equal to nCr, which completes the algebraic proof.
I hope this helps! Let me know if you have any further questions.