Answers to the practice midterm

1. Say that p is prime, and p | a. Show that for some integer m,
p² | ma.


Let m=p. Then p | a
=> a = pb for some b
=> ma = mpb = p²b for some b
=> ma is a multiple of p²
=> p² | ma.


2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.


It is impossible to make a function from X to Y, since the elements in X have nowhere to go. So indeed, every function from X to Y is raining frogs1:1.


3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mⁿ.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.


To specify a function from X to S, we need to say where each element of X goes. We already know where the m elements of S go: to themselves. It remains to specify where the other n-m elements of X go, in S. Each has m independent possibilities, giving m^n-m, just as when we counted all functions X->S.


4. Let X be a set. How big can X be, if

every relation is symmetric?

every relation is transitive?

every relation is reflexive?

Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.


Sym: 1. The relation {(a,b)} on {a,b} is not symmetric.
Trans: 1. The relation {(a,b),(b,a)} is not transitive.
Ref: 0. The relation {} on {a} is not reflexive.


5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).


For p o f to not be onto, either everything in X goes to even, or to odd.
If X all goes to odd, then f:X->Y has to take everything to 1. One function so far.
If X all goes to even, then f:X->Y is really a function to {0,2}, and there are 2³ such functions. Eight more.

Forgive me for not drawing these in ASCII.


6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)³ is congruent to a³+b³ mod 3.


(a+b)³ = a³ + 3a²b + 3ab² + b³.
So the difference between that and a³ + b³ is 3(a²b + ab²), a multiple of 3.


7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.

No; let a,b=1. Then (a+b)⁴ is 0 mod 4, but a⁴+b⁴ is 2 mod 4.
(In fact it holds for all prime exponents.)