Assignments.
 Due Sep. 30:
 Make truth tables for each of the following propositional forms:
 P∧ ∼P
 P∧(Q∨R)
 (P∧Q)∨(P∧R)
 ∼(P∧Q)
 ∼P∨∼Q
 (P⇒Q)∧(Q⇒R)
 P⇒R
 ∼P∨R
 Exercise 2.1: (ii), (iii), (iv), (v), (ix).
 Use the first problem to conclude that P⇒Q and ∼P∨Q are equivalent. Then conclude that P⇒Q and ∼Q→∼P are equivalent.
 As we discussed in class, in English, or is used as the exclusive or: meaning "one or the other but not both". The exclusive or is denoted by ⊻. Make the truth table of P⊻Q. Find a propositional form using only P, Q, ∧, ∨ and ∼ which is equivalent to P⊻ Q.
 Aliens have a strange "logical connective" between three statements. Its truth table is as follows
P  Q  R  f(P,Q,R) 
T  T  T  T 
T  T  F  F 
T  F  T  F 
T  F  F  T 
F  T  T  F 
F  T  F  T 
F  F  T  T 
F  F  F  F 
Is there a propositional form expressed only in terms of P, Q, R, ∧, ∨ and ∼ which is equivalent to f(P,Q,R)? If yes, find it and say why they are equivalent. If not, say why.
 Due Oct. 10:
 For any proposition P, let χ(P)=1 if P is true and χ(P)=0 if P is false. Prove that for any two propositions P and Q we have
 χ(∼P)=1χ(P).
 χ(P ∧ Q)=χ(P) χ(Q).
 χ(P ∨ Q)=χ(P)+χ(Q)χ(P)χ(Q).
 P ⇒Q if and only if χ(P)≤ χ(Q).
 P is equivalent to Q if and only if χ(P)=χ(Q).
 χ(P⇒Q)=χ(χ(P)≤ χ(Q)).
 χ(P⇔Q)=χ(χ(P)=χ(Q)).

 Prove that n^{2} is even if and only if n is even.
 Prove that √ 2 is irrational.
 Let a ∈ Z and b ∈ N. Show that there is a unique pair (q,r) of integers such that
 Exercises 3.1, 5.4, 5.6.
 Problems I: 10, 17, 18, 19.
 Due Oct. 14:
 Let f_{0}=0, f_{1}=1 and f_{n+1}=f_{n}+f_{n1} for any integer n.
 Prove that for any nonnegative integers n and m, we have f_{n+m}=f_{n}f_{m+1}+f_{n1}f_{m}.
 Prove that f_{n} divides f_{nk} for any natural numbers n and k.
 Let f_{n} be as in the previous problem. Show that any natural number can be written as a sum of distinct f_{n}'s. (Hint: use the strong induction.)
 By induction on n, prove that an npolygon has exactly n(n3)/2 diagonals.
 Prove that 1+(1/√ 2 )+…+(1/√ n ) ≤ 2√ n , for any natural number n.
 Let A and B be two subsets of X. The symmetric difference of A and B is the set of elements which are either in A or in B but not in both of them and it is denoted by A Δ B. For instance {1,2} Δ {1,3}={2,3}. Prove that
 A Δ B=(A∖B)∪(B∖A).
 A Δ B=(A∪B)∖(A∩B).
 A Δ B=B Δ A.
 A Δ A=∅
 A Δ ∅=A
 A Δ (B Δ C)=(A Δ B) Δ C.
 If A Δ B=A Δ C, then B=C.
 Prove that for any ε>0 there is δ>0 such that, if x5<δ, then x^{2}25<ε.
 Due Oct. 21 :
 Exercises 7.4, 7.8, 8.3.
 Problems II: 14, 15.
 Write in mathematical language what it means to say that there is a unique a in A such that P(a).

 Write in mathematical language what it means to say:
 lim_{x→ a}f(x) does not exist.
 any real number can be approximated by rational numbers.
 any real number can be approximated by irrational numbers.
 Let f(x)=1 if x ∈ Q and f(x)=0 if x ∈ R ∖ Q. Prove that for any real number a, lim _{x → a}f(x) does not exist.
 Define what it means to say that lim_{x→+∞} f(x)=L.
 Let A be a finite set and f and g be two functions from A to itself. Prove that the composite of f and g is bijective if and only if f and g are bijective.
 Due Oct. 28:
 Exercises: 9.1, 9.2, 9.3, 9.4, 9.6
 Let f:R→ R, f(x)=√ x^{2}+1 . A (sloppy) student wrote f as the composite function of functions g_{1}, g_{2} and g_{3}. He defined g_{i}'s this way:
 g_{1}(x)=x^{2}.
 g_{2}(x)=x+1.
 g_{3}(x)=√ x .
His answer is not complete. Why? Complete his answer.
 Let S_{n} be the set of all the invertible functions from A={1,...,n} to itself.
 Find the order of S_{3} and S_{4}.
 Let f and g be two functions from {1,...,n} to itself. Prove that the compsite of f and g is in S_{n} if and only if f and g are in S_{n}. (You are allowed to use problems from previous homework.)
 If f is in S_{n}, then f^{(1)} is also in S_{n}.
 Let f^{(1)}=f and recursively let f^{(m)} be the composite of f^{(m1)} and f. Prove that there is a natural number m such that, for any f in S_{n}, f^{(m)}=I_{A}.
 Let f:A→B and g:B→A. Determine whether the following statements are true or false. If a statement is ture, then prove it. If it is not true, then provide a counterexample.
 If the composite of f and g is the identity function of A, then the composite of g and f is invertible.
 If the composite of f and g is the identity function of A and the composite of g and f is invertible, then g is the inverse (function) of f.
 Prove that there is a bijection between the power set of {1,...,n} and {0,1}^{n}={(e_{1},...,e_{n}) for any i, e_{i}=0 or 1}. (Hint: use one of the previous week's problems!)
 Due Nov. 4:
 Write down the details of the proof of the Unique Factorization, which was presented in the class.
 For any nonzero integer n and prime p, let v_{p}(n)=d if p^{d} divides n and p^{d+1} does not
divide n. For instance, v_{2}(4)=2, v_{3}(6)=1 and v_{5}(6)=0. Notice that we have
n=∏_{p} p^{vp(n)},
where p is running through primes. Let m and n be two nonzero integers.
 Prove that v_{p}(mn) = v_{p}(m)+v_{p}(n).
 Prove that v_{p}(m+n) ≥ min{v_{p}(m),v_{p}(n)}.
 Prove that mn if and only if for any prime p we have v_{p}(m) ≤ v_{p}(n).
 Prove that v_{p}(gcd(n,m)) = min{v_{p}(n),v_{p}(m)}.
 Let lcm(m,n) be the least common multiple of m and n. Prove that
v_{p}(lcm(m,n)) = max{v_{p}(m),v_{p}(n)}.
 Prove that mn=lcm(m,n).gcd(m,n).
 Prove that the number d(n) of the positive divisors of n is equal to ∏_{p}(v_{p}(n)+1).
 Prove that d(n) is odd if and only if n is a perfect square.
 Prove that d(mn)=d(m)d(n) if gcd(m,n)=1.
 Let f_{n} be the Fibonacci sequence. Prove that gcd(f_{m},f_{n})=f_{gcd(m,n)} for any positive integers m and n.
 Due Nov. 14:
 In the following questions, if the answer is yes, find all the possible solutions, and if the answer is no, prove your claim.
 Is there x such that 14x≡1(mod 29)?
 Is there x such that 7x≡4 (mod 18)?
 Is there x such that 14x≡8(mod 36)?
 Is there x such that 14x≡1(mod 36)?
 Find the min value of x+y such that x and y are integers and 53x+29y=3. Prove your claim.
 Prove that gcd(2^{2n}+1,2^{2m}+1)=1 if m and n are distinct positive integers.

 Prove that if p is prime and x^{2}1≡0 (mod p), then x is congruent to either 1 or 1 mod p. Is it true mod m where m is not prime?
 Prove that if p is prime and a is not congrunet to zero mod p, then there is a' such that a'a≡1 (mod p).
 (Wilson's theorem) Prove that (p1)!≡1(mod p) if p is prime. Hint: Group any number a in {1,..., p1} with a' in {1,...,p1} such that a'a≡1 (mod p). (n!=1.2.3. ... .n.)
 Prove that there is no positive integer n for which 2^{n} + 1 is divisible by 7.
 Prove that gcd(2^{n}1,2^{m}1)=2^{gcd(m,n)}1.
 Due Nov. 21:

Let m and n be two integers. Assume that gcd(m,n)=1. Let f:Z/(mn)Z → Z/mZ × Z/nZ
f(x+(mn)Z)=(x+mZ,x+nZ).
 Prove that f is a bijection. (Hint: it is enough to show that it is an injection.)
 (Chinese Remainder Theorem) Prove that for any integers a and b there is a unique x modulo mn such that x≡ a (mod m) and x≡ b (mod n).
 Prove that for any x and y in Z/(mn)Z we have f(xy)=f(x)f(y).
 Prove that f(U(Z/(mn)Z))=U(Z/mZ)× U(Z/nZ), where as we defined in the class U(R) is the set of invertible elements in R.
 Prove that φ(mn)=φ(m)φ(n), where φ is the Euler's phi function.
 Prove that φ(p^{k})=p^{k1}(p1) for any prime p and positive integer k.
 Prove that φ(n)=∏_{pn}p^{(vp(n)1)}(p1), where p runs through all the prime divisors of n and v_{p}(n) is defined as in the previous week's problem set.
 Prove that, if p and q are distinct prime numbers, then p^{q1}+q^{p1}≡ 1 (mod pq).
 Page 296, Problems VI, problems 12, 13, 14, 16.
 Due Nov. 28
