Please solve problem #4 (the last one)

\#1 Congruence Magic. Do the following problems by hand, using congruences. If approached the right way, the calculations should take only a line or two, and can be done easily by hand. (You are welcome to check your result using a calculator, or WolframAlpha, but you must come up with a rigorous solution based on congruences.) (a) Find the last decimal digit of 347101. (b) Find the remainder of 347101 when divided by 101. (Hint: Use Fermat's Little Theorem, but be careful: The exponent, 101, is not quite the same as in the theorem ...) (c) Find the remainder of 10011001 upon division by 9 . (d) Show that 7 divides 43n+1+23n+1+1 for all nN. \#2 Proof practice: Properties of congruences. For each of the following statements either give a proof or a counterexample. If the statement is false, a counterexample is sufficient. For true statements, give a careful step-by-step proof using only the official definitions of congruences (i.e., " ab mod m " means "there exists kZ such that a=b+km "). Your proofs should not use any properties or theorems about congruences and divisibility. In all statements, a,b,c,d are assumed to be integers, and m is a natural number. (a) If ab0modm, then a0modm or b0modm. (b) If abmodm and cdmodm, then acbdmodm. (c) If abmodm then kakbmodm for any kN. \#3 Proof practice: Properties of Relations: In each of the following problems, a set S and a relation on S, denoted by , are defined. Determine whether the given relation is (R) reflexive, (S) symmetric, (T) transitive. For each of the properties (R), (S), (T), either give a proof, or a specific counter-example. The proofs required are short-a line or two is usually enough for symmetric and reflexive properties; a bit more is needed for the reflexive property-but they must be properly written up, in correct logical order, with all quantifiers included. (a) S=N.xyxy. (b) S=R.xyxy1. (c) S=R.xyxyZ. (d) S=R.xy "There exists nZ such that x=2ny. " \#4 Equivalence classes. For those relations in the previous problem that are equivalence relations, determine explicitly the equivalence class of the element 1. Explain briefly! (The point of this exercise is to determine these sets explicitly, i.e., not by using general notations such as {xN:x1}. For example, for the congruence relation modulo 2 on the set S=Z, the equivalence class [1] is the set of odd integers