Course home | #1 | #2 | #3 | #4 | #5 | #6 | #7 | #8 | #9 | #10
Recall that HW 9.38, HW 9A.6, HW 9A.11, HW 9A.12 are also due Tuesday, Nov 1.
Please hand in each problem ON ITS DUE DATE, not before.
Do not mix problems with different due dates.
Please hand in all your solutions, except the drawings,
in Latex/PDF.
10A.1 DO (ongoing): Study the relevant problem sets from the instructor's 2014 DM course. By now you need to have completed all exercises in problem sets 1--9. Below I highlight some of the 2014 exercises that have not been specifically stated in this course yet.
10A.2 DO: 2014/9.0 (max no of edges in disconnected graph), 2014/9.1 (graph or complement connected), 2014/9.2 (diameter of graph), 2014/9.4 (diameter vs. cut vertex)
10A.3 CH: 2014/9.8 ($t$-wise independence vs. size of sample space)
10A.4 HW (due Thu, Nov 3): Construct a graph $G$ such that $G$ has no triangles and yet $\chi(G)\ge 4$. Instructions: 11 vertices, 5-fold symmetry (i.e., you can place the vertices in the plane such that the graph will not change if you rotate your picture by 72 degrees). It is sufficient if you provide a neat drawing that displays the 72-degree rotational symmetry; you do not need to prove that your graph has the two required properties. (6 points)
10A.5 DO: Let $G$ be a triangle-free graph. Prove: $\chi(G)=O(\sqrt{n})$.
10A.6 DO (due Thu, Nov 3): Study the Chernoff bound (LN). (There is no specific credit for doing so but some problems will require the Chernoff bound.)
10A.7 HW (due Thu, Nov 3): Consider a random graph $G\sim\ggg_{n,1/2}$. (a) Prove: with high probability, all vertices have degree between $0.49n$ and $0.51n$. The phrase "with high probability" means the following. Let $p_n$ denote the probability in question. Then $p_n\to 1$ as $n\to\infty$. Use Chernoff's bound. (b) Show that this result would not follow from Chebyshev's inequality. (7+3 points)
10A.8 DEF: A DAG (Directed Acyclic Graph) is a directed graph with no directed cycles.
10A.9 DEF: A topological sort of a digraph $G=(V,E)$ is a linear ordering (numbering) of the vertices, say $v_1,\dots,v_n$, such that $(\forall i,j)((i,j)\in E \implies i < j)$.
10A.10 DO: Obviously, if a digraph $G$ admits a topological sort then it is a DAG. Prove that the converse also holds: The digraph $G$ is a DAG if and only if it has a topological sort.
10A.11 DO: Count those tournaments on a given set of $n$ vertices that are DAGs.
10A.12 DO: For a graph $G=(V,E)$ and a positive integer $t$ let $\chi_G(t)$ denote the number of functions $f : V\to [t]$ such that $f$ is a legal coloring. Prove: the function $\chi_G(t)$ is a polynomial of degree $n$. It is called the chromatic polynomial of $G$. Solve this problem without looking it up.
10A.13 HW (due Thu, Nov 3): Let $T$ be a tree with $n$ vertices. Compute the chromatic polynomial $\chi_T$ as a closed-form expression. Prove your answer. (6 points)
10A.14 DEF: Let $e=\{a,b\}$ be an edge of the graph $G$. Let $G-e$ denote the graph $G$ with the edge $e$ deleted (but the vertices $a,b$ are not deleted). Let $G/e$ denote the graph obtained by contraction of $e$. This means that we identify $a$ and $b$ (replace them by a single vertex); this new vertex will be adjacent to all former neighbors of $a$ and $b$ (other than $a$ and $b$). For instance $K_n/e=K_{n-1}$ for any edge $e$ of $K_n$.
10A.15 DO: Prove: $\displaystyle{\chi_G = \chi_{G-e} - \chi_{G/e}}$ where $\chi_G$ denotes the chromatic polynomial of the graph $G$.
10A.16 DO: Compute the chromatic polynomials of $K_n$ and $\overline{K}_n$ as closed-form expressions. You may use binomial coefficients.
10A.17 DO: Compute the chromatic polynomial of $C_n$ as a closed-form expression.
10A.18 CH: Prove: the number acyclic orientations of a graph $G$ is equal to $|\chi_G(-1)|$. (An acyclic orientation is an orientation which has no directed cycles.) Solve this without looking it up.
Recall that HW 8A.11, HW 8A.13, HW 8A.18, HW 8A.20, XC 8A.21, XC 8A.23 are also due Thursday, Oct 27.
9A.1 DEF. We say that two random variables, $X$ and $Y$, are positively correlated if $\cov(X,Y) > 0$, i.e., $E(XY) > E(X)E(Y).$ We say that $X$ and $Y$ are negatively correlated if $\cov(X,Y) < 0$, i.e., $E(XY) < E(X)E(Y).$ We say that $X$ and $Y$ are uncorrelated if $\cov(X,Y) =0$, i.e., $E(XY) = E(X)E(Y).$
9A.2 DO: If the random variables $X,Y$ are independent then they are uncorrelated.
9A.3 HW: Show that the converse of the preceding exercise is false. In other words, construct a probability space and random variables $X,Y$ such that $X$ and $Y$ are uncorrelated but not independent. Make your sample space as small as possible. You do not need to prove minimality of the sample space. (7 points)
9A.4 DO: Prove: The events $A,B$ are positively correlated if and only if their indicator variables $\theta_A$ and $\theta_B$ are positively correlated. Prove the analogous statement for negative correlation.
9A.5 CH (strongly negatively correlated events): Let $A_1,\dots,A_m$ be events. Assume $(\forall i)(P(A_i)=1/2)$ and $(\forall i\neq j)(P(A_i\cap A_j)\le 1/5)$. Prove: $m\le 6$. Make your proof short and elegant.
9A.6 HW (due Tue, Nov 1): LN 7.2.16 ("randomly stuffed envelopes") (4 points)
9A.7 DO: Prove: If the random variables $X_1,\dots,X_k$ are pairwise independent then $\var(\sum X_i) = \sum \var(X_i)$.
9A.8 DO: Compute the variance of the number of sucecsses in a sequence of $n$ pairwise independent Bernoulli trials, each with success probability $p$.
9A.9 DEF: We say that the linear combination $\sum_{i=1}^k c_if_i$ of the functions $f_1,\dots,f_k : \Omega \to \rrr$ is trivial if all coefficients $c_i$ are zero.
9A.10 DEF (linear independence): We say that the functions $f_1,\dots,f_k : \Omega \to \rrr$ are linearly independent if only their trivial linear combination is the identically zero function, i.e., if $(\forall c_1,\dots, c_k\in\rrr)(\sum c_if_i=0 \implies c_1=\dots=c_k=0)$.
9A.11 HW (statistical vs. linear independence) (due Tue, Nov 1):
Prove: If the random variables
$X_1,\dots,X_k$ are pairwise independent and not almost constant
then they are linearly independent. (See exercise 9.27 in the
class notes for the definition of "almost constant.")
(7 points)
The longest decreasing subsequence has length 3; $S$ includes
the decreasing subsequences $11,8,6$ and $11,8,2$.
Find an elegant, immediately convincing ("AHA") argument
that shows that these are indeed longest, i.e., there is no
increasing subsequence of length 5 and no decreasing
subsequence of length 4.
9A.14 CH: Let $X$ denote the length of the longest increasing subsequence in a random permutation of $[n]$. (Here by "permutation" we mean an ordering of $[n]$ in a sequence. We pick one of the $n!$ orderings uniformly at random.) Prove: $E(X) = \Theta(\sqrt{n})$.
8A.1 CH: As before, let $\displaystyle{S(n,k)=\sum_{t=0}^{\infty}\binom{n}{kt}}$. Prove: $|S(n,4)-2^{n-2}| \le 2^{n/2-1}.$
8A.2 XC: Determine the limit $\displaystyle{\lim_{n\to\infty}\frac{(1+1/n)^{n^2}}{\eee^n}}$. (5 points)
8A.3 XC: Prove: the product of any $k$ consecutive integers is divisible by $k!$. Hint. One-line proof. (5 points)
8A.4 HW: Count the paths of length $k-1$ (subgraphs isomorphic to $P_k$) in the complete graph $K_n$. Your answer should be a closed-form expression using binomial coefficients. (5 points)
8A.5 DO: Count the cycles of length $k$ (subgraphs isomorphic to $C_k$) in the complete graph $K_n$. Your answer should be a closed-form expression using binomial coefficients.
8A.6 XC: (a) Let $A\subset \zzz$ be a finite set of integers, $|A|=n$. Let $k\ast A$ denote the set $\displaystyle{\underbrace{A+\dots+A}_{k \text{ times}}}$. Prove: $\displaystyle{|k\ast A|\le\binom{n+k-1}{k}}$. (b) Prove that this bound is tight for every $n$ and $k$. (5+3 points)
8A.7 DO: Prove: In a connected graph, every pair of longest paths shares a vertex.
8A.8 CH: Prove: In a tree, all longest paths share a vertex.
8A.9 DO: Count the independent sets (a) in the path $P_n$ and (b) in the cycle $C_n$. Your answers should be a closed-form expressions in terms of a sequence discussed in class.
8A.10 DEFINITION: A matching in a graph is a set of disjoint edges. The matching number $\nu(G)$ is the size of a maximum matching (largest number of edges in a matching). ($\nu$ is the Greek letter "nu," not the Roman "v.")
8A.11 HW (due Thursday, October 27): (a) Let $M$ be a maximal matching (a matching that cannot be extended by adding an edge). Prove: $\nu(G)\le 2|M|$. (b) Prove that this bound is tight for all even values of $\nu(G)$. In other words, show that $(\forall k)(\exists$ graph $G$ and a maximal matching $M$ in $G$ such that $|M|=k$ and $\nu(G)=2k\,)$. (c) Make your graphs $G$ in part (b) connected. (5+4+2 points)
8A.12 DO (Counting trees with prescribed degrees): Let $d_1,\dots,d_n$ be positive integers such that $\sum_{i=1}^n d_i=2n-2$. Prove that the number of trees with vertex set $V=[n]$ that satisfy $(\forall i)(\deg(i)=d_i)$ is $\displaystyle{\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}}.$ (Note: typo in numerator fixed 10/22/16 at 10:10pm.)
8A.13 HW (due Thursday, October 27): Recall Cayley's formula: the number of spanning trees of $K_n$ is $n^{n-2}$. Use the preceding exercise to prove Cayley's formula. Your proof should be very short. (5 points)
8A.14 DO: Study Prüfer's code for a bijective proof of Cayley's formula.
8A.15 DO: Let $B(n)$ denote the number of partitions of the set $[n]$. Prove: $B(n)\le n^n$.
8A.16 XC: Prove: $(\forall k)(1\le k\le n \implies k^{n-k} \le B(n))$. (4 points)
8A.16 DO: Use the two preceding exercises to solve 6A.19XC: prove that $\ln B(n)\sim n\ln n$. Hint: apply the preceding exercise with $k=n/\ln n$.
8A.17 HW: Let us perform a sequence of $n$ Bernoulli trials; the $i$-th trial has success probability $p_i$. Let $X$ denote the number of successes. Prove: $E(X)=p_1+\dots+p_n$. Hint: Let $Y_i$ denote the indicator of the event that the $i$-th trial is successful. Observe that $X=Y_1+\dots+Y_n$. Use the linearity of expectation. (5 points)
8A.18 HW (due Thursday, Oct 27): (a) LN 7.2.13 (club with 2000 members). Assume the club serves vodka legally to all its members. - Make sure you give a clear definition of the random variables you use. The clarity of the definition accounts for half the credit. - Clarify the role of the vodka. Hint. Review indicator variables (LN 7.2.6, 7.2.7). Represent the number of lucky members as a sum of indicator variables. (b) What is the size of the sample space for this experiment? (8+3 points)
8A.19 DO (random permutations): Recall that a permutation of a set $A$ is a bijection $A\to A$. Associate with a permutation $\pi$ of the set $A$ a directed graph where $A$ is the set of vertices and a directed edge is drawn from $i$ to $\pi(i)$. Let us call such a directed graph (digraph) a "permutation digraph." Prove: every connected component of a permutation digraph is a directed cycle (of length $\ge 1$). Note that fixed points (points $x\in A$ such that $\pi(x)=x$) correspond to "loops" (cycles of length 1). Cycles of length 2 occur when $\pi$ swaps two elements of $A$.
8A.20 HW (due Thursday, Oct 27): For a permutation $\pi$ of the set $A$ and an element $x\in A$ let $c(x,\pi)$ denote the length of the $\pi$-cycle through $x$. Let us pick $\pi$ uniformly at random from among the $n!$ permutations of the set $[n]$. Prove: for all $i$ in the range $1\le i\le n$ we have $P(c(1,\pi)=i)=1/n.$ (8 points)
8A.21 XC (due Thursday, Oct 27): Let $c(\pi)$ denote the number of cycles of the permutation $\pi$. Let us pick $\pi$ uniformly at random from among the $n!$ permutations of $[n]$. Prove: $E(c(\pi))\sim \ln n$. (6 points)
8A.22 CH (expected number of prime divisors): For a positive integer $n$, let $\omega(n)$ denote the number of distinct prime divisors of $n$, and let $\Omega(n)$ denote the total number of prime divisors of $n$. For example, $\omega(80)=2$ and $\Omega(80)=5$. (This is traditional notation in number theory and has nothing to do with our asymptotic notation.) Let us pick a number $x$ uniformly at random from $[n]$. Prove: both $E(\omega(x))-\ln\ln n$ and $E(\Omega(x))-\ln\ln n$ are bounded.
8A.23 XC (due Thursday, Oct 27): Let us pick a number $x$ uniformly at random from $[n]$. Let $A$ denote the event that $2\mid x$ and $B$ the event that $3\mid x$. Determine, for what values of $n$ are the events $A$ and $B$ (a) positively (b) negatively correlated or (c) independent. Give a clear and compact answer; prove. (6 points)
(There is no problem set 7A.)
6A.1 DO: Prove: If the limit $L=\lim_{n\to\infty} a_n/b_n$ exists and $0 < |L| <\infty$ then $a_n = \Theta(b_n)$.
6A.2 HW: Find two sequences of positive reals, $a_n$ and $b_n$, such that $a_n = \Theta(b_n)$ but the limit $\lim_{n\to\infty}a_n/b_n$ does not exist. For your example, do not prove the $a_n=\Theta(b_n)$ relation; but prove that the limit does not exist. (4 points)
6A.3 DO: Prove: (a) $\ln n=o(n)$. (b) $\ln n=o(\sqrt{n})$. (c) $(\forall \epsilon>0)(\ln n=o(n^{\epsilon}))$.
6A.4 DO: True or false? $\log_2 n = \Theta(\ln n)$.
6A.5 XC (due Thursday, October 20): Let $k_n$ be a sequence of nonnegative integers such that $\sqrt{n}= o(k_n)$. Prove: $$\binom{n}{k_n} = o\left(\frac{n^{k_n}}{k_n!}\right) .$$ Compare this with exercise 5A.13 XC. (6 points)
6A.6 DO (Handshake Theorem): Let $G=(V,E)$ be a graph. Prove: $\sum_{v\in V} \deg(v)=2m.$
6A.7 DO: Prove: There is no 3-regular graph with 21 vertices.
6A.8 HW (due Thursday, October 20): A perfect matching in a graph is a 1-regular spanning subgraph, i.e., a set of disjoint edges that cover every vertex. Draw a 3-regular graph that has no perfect matching. Make your graph as small as possible. (You don't need to prove minimality.) Prove that your graph has no perfect matching. (6 points)
6A.9 DO: Find all connected 2-regular graphs.
6A.10 HW (due Thursday, October 20): Let $G(n)$ denote the number of non-isomorphic graphs on $n$ vertices. (More precisely, this means the number of equivalence classes of $n$-vertex graphs under isomorphism.) Let $$ N = 2^{\binom{n}{2}}.$$ (a) Prove: $N/n! \le G(n) \le N$. (b) Prove: $\log_2 G(n) \sim n^2/2.$ (5+6 points)
6A.11 CH: Using the notation of the preceding exercise, prove: $G(n) \sim N/n!$.
6A.12 Definition (Grid graph): The $k\times\ell$ grid graph $\grid(k,\ell)$ has $n=k\ell$ vertices arranged in the plane with integer coordinates $V=\{(x,y)\mid 1\le x\le k,\ 1\le y\le\ell\}$. Two vertices $(x_1,y_1)$ and $(x_2,y_2)$ are adjacent if either $x_1=x_2$ and $|y_1-y_2|=1$ (vertical edges) or $y_1=y_2$ and $|x_1-x_2|=1$ (horizontal edges).
6A.13 DO: Prove that $\grid(k,\ell)$ is bipartite.
6A.14 HW: Note that the distance (length of shortest path) between two opposite corners of the grid graph $\grid(k,\ell)$ is $k+\ell-2$. Count the shortest paths between the bottom left corner and the top right corner of the $k\times \ell$ grid graph. Your answer should be a simple closed-form expression (no summation or product signs) using binomial coefficents. Clearly state and prove your answer. (7 points)
6A.15 Definition. A Hamilton cycle in a graph is a spanning subgraph that is a cycle. A graph is Hamiltonian if it has a Hamilton cycle.
6A.16 DO: Show that the dodecahedron graph is Hamiltonian.
6A.17 HW: For what values of $k,\ell\ge 1$ is the $k\times\ell$ grid graph Hamiltonian? Clearly state your answer. You do not need to prove Hamiltonicity for the pairs $(k,\ell)$ for which you claim the grid is Hamiltonian. However, for the pairs $(k,\ell)$ for which you claim the grid is not Hamiltonian, give an elegant, very short proof. (7 points)
6A.18 DO: Prove: $\ln n! \sim n \ln n$. Do not use Stirling's formula.
6A.19 XC (due Thursday, Oct 20): Let $B(n)$ denote the number of partitions of the set $[n]$. Prove: $\ln B(n)\sim n\ln n$. Your proof should be elegant and elementary; do not use any results not proved in class. (6 points)
5A.1 DO: Prove: If $x$ is odd then $x^2\equiv 1 \pmod 8$. Make your proof simple (one line, no case distinctions).
5A.2 HW: Let $N=35,113=13\times 37\times 73$. Prove: If $\gcd(a,N)=1$ then $a^{72}\equiv 1\pmod N$. (8 points)
5A.3 CH: Let $\displaystyle{P(x)=\prod_{p\le x} p}$ be the product of all primes $\le x$. Prove: $\ln P\sim x$. (Use the Prime number Theorem.) So $P(x)$ is approximately $\eee^x$ in the sense that for all $\epsilon >0$ there is an $x_{\epsilon}$ such that for all $x\ge x_{\epsilon}$ the following holds: $(\eee-\epsilon)^x < P(x) < (\eee+\epsilon)^x$.
5A.4 CH: Let $\displaystyle{Q(n)=\lcm(1,2,\dots,n)}$. Prove: $\ln Q(n)\sim n$. So $Q(n)$ is approximately $\eee^n$.
5A.5 CH: Let $p_1 < p_2 <\dots < p_k$ be an arithmetic progression of prime numbers with increment $d$ (i.e., $d=p_i-p_{i-1}$ for all $i$). Prove: if $k$ is sufficiently large then $d > 2.7^k$.
5A.6 HW: Find two sequences of positive integers, $a_n$ and $b_n$, such that $a_n\sim b_n$ but $2^{a_n}\nsim 2^{b_n}$. (3 points)
5A.7 HW:
(a) Find sequences $a_n,b_n >1$ such that $a_n\sim b_n$
but $\ln a_n \nsim \ln b_n$.
(b) Prove: If $a_n\sim b_n$ and $a_n \ge 1.1$ then
$\ln a_n \sim \ln b_n$.
Terminology: we say that a sequence $a_n > 1$ is bounded away from 1 if $(\exists c>0)$ such that for all sufficiently large $n$ we have $a_n > 1+c$. So problem 5A.5(b) speaks about sequences that are bounded away from 1. (4+6 points)
5A.8 DO: Prove: $\sum_{k=0}^n \binom{n}{k}=2^n.$ Give two proofs: (1) a combinatorial proof, based on the definition of binomial coefficients; and (2) an "algebra proof," based on the Binomial Theorem.
5A.9 DO: Prove: For $n\ge 1$, the number if even subsets of $[n]$ is the same as the number of odd subsets of $[n]$. Give two proofs: (a) a combinatorial proof (find a very simple bijection between the even subsets and the odd subsets); and (b) and algebra proof, using the Binomial Theorem.
5A.10 DO: Prove Pascal's identity: $$ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.$$ Give two proofs: (a) a combinatorial proof (find a very simple bijection between the sets counted on the left-hand side and the sets counted on the right-hand side); (b) and algebra proof, using the Binomial Theorem. Hint for (b): consider the identity $(1+x)^n=(1+x)^{n-1}(1+x)$. Compare the coefficients of $x^k$ on the two sides.
5A.11 DO: Prove the identity $$ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} .$$ Give two proofs: (a) a combinatorial proof: find an interpretation of the left-hand side so it will count the $n$-subsets of a $2n$-set; (b) and algebra proof, using the Binomial Theorem. Hint for (b): consider the identity $(1+x)^n(1+x)^n=(1+x)^{2n}$. Compare the coefficients of $x^n$ on the two sides.
5A.12 XC (due Tuesday, October 18): Prove: If $0 < h < 1$ is real and $k\ge 1$ is an integer then $(1-h)^k \ge 1-kh$. Hint: Induction on $k$. (3 points)
5A.13 XC (due Tuesday, October 18): Let $k_n$ be a sequence of nonnegative integers such that $k_n = o(\sqrt{n})$, i.e., $\lim_{n\to\infty} k_n/\sqrt{n}=0$. Prove: $$\binom{n}{k_n} \sim \frac{n^{k_n}}{k_n!} .$$ (6 points)
5A.14 DO: Prove: $\displaystyle{(\forall n,k)(\binom{n}{k}\le \frac{n^k}{k!})}$.
5A.15 HW (due Tuesday, October 18): Prove: for $1\le k\le n$ we have $\displaystyle{\binom{n}{k}\ge\left(\frac{n}{k}\right)^k}$. (5 points)
5A.16 DO: Prove: $(\forall x\in\rrr)(\eee^x \ge 1+x)$.
5A.17 XC (due Tuesday, October 18): Give a two-line proof of the following statement: $\displaystyle{(\forall n\ge 0)(n! \ge\left(\frac{n}{\eee}\right)^n)}$. Note that Stirling's formula is of no use; it can only prove statements "for sufficiently large $n$." There are effective variants of Stirling's formula; do not use any version of Stirling's formula. (5 points)
5A.18 XC (due Tuesday, October 18): Give a two-line proof of the following statement. For $1\le k\le n$ we have $\displaystyle{\binom{n}{k}\le \left(\frac{\eee n}{k}\right)^k}$. Do not use any version of Stirling's formula. Hint: use the preceding exercise. (5 points)
5A.19 CH: $\displaystyle{\sum_{i=0}^k \binom{n}{i}\le\left(\frac{\eee n}{k}\right)^k}$.
5A.20 DO: Prove: If $p$ is a prime and $1\le k\le p-1$ then $p$ divides $\displaystyle{\binom{p}{k}}$.
5A.21 HW (due Tuesday, October 18): Prove Fermat's little Theorem in the form $(\forall a)(a^p\equiv a\pmod p)$. First observe that it suffices to prove the result for $a\ge 0$. For $a\ge 0$ prove it by induction on $a$. Use the preceding exercise. (8 points)
5A.22 DO: Let $e_p(n)$ denote the exponent of the prime number $p$
in the prime factorization of the positive integer $n$. For instance,
$e_3(63)=2$ and $e_7(63)=1$ and $e_5(63)=0$. Prove:
$e_p(n!)=\sum_{i=1}^{\infty}\lfloor n/p^i\rfloor$. (The
"floor" function $\lfloor x\rfloor$ denotes the greatest
integer $\le x$. For instance, $\lfloor \pi\rfloor =3$
and $\lfloor -\pi\rfloor =-4$ and $\lfloor 5\rfloor =5$.)
5A.23 CH: Prove: If $p^t \mid \binom{n}{k}$ then $p^t\le n$.
5A.24 CH (Chebyshev): Use the preceding exercise to prove that $\pi(x) =\Omega(x/\log x)$, i.e., there exists $c>0$ such that for all sufficiently large $x$ we have $\pi(x) \ge cx/\log x$.
5A.25 CH: Prove, from first principles, that $\prod_{p\le x} p \le 4^x$. Hint. Study the prime factors of the binomial coefficients $\binom{2n}{n}$ and $\binom{2n+1}{n}$.
5A.26 CH (Chebyshev): Prove: $\pi(x)=O(x/\log x)$, i.e., there is a constant $C$ such that $\pi(x) \le C x/\log x$ for all sufficiently large $x$. The two results just proved combine to an entirely elementary proof of
Chebyshev's weak version of the Prime Number Theorem,
namely, $\pi(x)=\Theta(x/\log x)$, i.e., there exist positive constants $c_1$ and $c_2$ such that $c_1 x/\log x \le \pi(x) \le c_2 x/\log x$ for all sufficiently large $x$.
4A.1 DO by Thursday, October 13: Study Home work sets #1, #2, #3, and #4 on the instructor's DM 2014 website. Solve all problems involving concepts discussed in class. This is a large set, start working on it asap.
4A.2 DO: Prove: If $a\equiv b\pmod m$ then $\gcd(a,m)=\gcd(b,m)$.
4A.3 HW: Find the set of solutions of the following system
of simultaneous congruences:
$9x\equiv 6 \pmod{42}$
$x\equiv 31 \pmod {245}$
(a) Decide whether or not this system is solvable. Clearly state
and prove your answer. Do not use CH 4.27; use CRT only.
Hint. First solve the first congruence and replace it
with your solution which will be of the form $x\equiv k \pmod m$
(find $k$ and $m$). Next, split your composite moduli into
prime powers. Next, eliminate any redundant congruences.
(A congruence is redundant if it follows from other
congruences.) Now apply CRT.
(b) If solvable, find the set $S$ of
solutions. Your answer should be of the form $S=b\zzz+c$
(a single residue class); determine the values of $b$ and $c$.
(5+5 points)
4A.4 HW (due Thu, Oct 13): Consider the following system
of simultaneous congruences:
$x\equiv a \pmod{28}$
$x\equiv 11 \pmod {42}$
$x\equiv 7 \pmod {8}$
Determine the set $A$ of those value of $a$ for which this system
is solvable. Your answer should be of the form $A=b\zzz+c$
(a single residue class); determine the values of $b$ and $c$.
Use CH. 4.27 and Theorem 4.22 from the class notes.
(10 points)
Remember that problems 2A.15 and 2A.20 below are also due Thursday, October 6.
3A.1 HW For each pair $(a,m)$ below, decide whether or not
a multiplicative inverse of $a$ modulo $m$ exists (clearly state
EXISTS or DOES NOT EXIST). If it does not exist, state, why.
(Your reason in each case should be no more than half a line.)
If it does exist, find the the smallest positive multiplicative inverse.
Just state this number, do not show how you got it and do not
prove its correctness.
(a) (7, 45); (b) (21, 51)
(c) (-60, 7) (d) (1, 0)
(e) (2, 0) (f) (0, 0) (g) (0, 1)
(1.5 points per question; total will be rounded up to the
next whole number)
3A.2 HW Let $k$ be a positive integer.
For each pair $(a,m)$ below, decide whether or not
a multiplicative inverse of $a$ modulo $m$ exists and find
the smallest positive multiplicative inverse (so this should be
number between $0$ and $|m|-1$). Your answer in each case
should be a simple expression in terms of the positive parameter $k$.
PROVE your answers.
(a) $(2, 2k+1)$ ; (b) $(k, k^2+k+1)$
(4+7 points)
3A.3 HW Find $x,y\in\zzz$ such that $85x+123y=1$. Do not use electronic devices. Show your work! (Every step of it.) Hint. Follow the example in class; you need to find a multiplicative inverse of 123 modulo 85. Clearly state the values of $x$ and $y$; both numbers should be less than 200 in absolute value. (7 points)
3A.4 DO: Prove: $(\forall a,b >0)(\exists x,y)(\gcd(a,b)=ax+by \ \&\ |x|< b \ \&\ |y|< a)$
3A.5 XC (due Tuesday, October 11) Let $k,\ell$ be non-negative integers and let $d=\gcd(k,\ell)$. Prove: $\gcd(2^k-1,2^{\ell}-1)=2^d-1$. (7 points)
3A.6 DEF. Let $F_0=0, F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ denote the Fibonacci numbers. So $F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$, $F_6=8$, $F_7=13$, $F_8=21$, $F_9=34$, $F_{10}=55$, $F_{11}=89$, etc.
3A.7 HW (due Tuesday, October 11) Prove: $(\forall n\ge 0)(\gcd(F_n,F_{n+1})=1)$. Hint. Induction. (6 points)
3A.8 CH Let $k,\ell$ be non-negative integers and let $d=\gcd(k,\ell)$. Prove: $\gcd(F_k, F_{\ell})=F_d$.
3A.9 XC (due Tuesday, October 11) Let us fix $m\ge 2$ and
consider the sequence $(F_k \bmod m)$ $(k=0,1,2,\dots)$.
(Recall that
$(a \bmod m)$ denotes the smallest non-negative integer
$x$ such that $x\equiv a \pmod m$.) So for instance
for $m=3$ we are considering the sequence
$0,1,1,2,0,2,2,1,0,1,1,2,0,\dots$.
Prove that the sequence $(F_k\bmod m)$ is periodic and the period
is $\le m^2-1$. (A sequence $a_0, a_1,a_2,\dots$ is periodic
with period $h > 0$ if $(\forall k)(a_{k+h}=a_k)$.)
(7 points)
3A.10 DO: Prove: If $\gcd(a,c)=1$ then $\gcd(a,bc)=\gcd(a,b)$. Do not use the Fundamental Theorem of Arithmetic, just basic facts we proved about gcd. Hint. Let $d=\gcd(a,bc)$. Clearly $\gcd(a,b) \mid d$ (why?) so what remains to be shown is that $d\mid b$. Take a look at $\gcd(ab,bc)$.
2A.1 DO: Review mathematical induction.
2A.2 Division Theorem.
$(\forall a,b)(b\neq 0 \implies (\exists! q,r)((0\le r\le |b|-1)\ \&\
(a=bq+r))$.
For instance, if $a=87$ and $b=-7$ then $q=-12$ and $r=3$:
$87 = (-7)\cdot(-12)+3$.
2A.3 DO: Prove the Division Theorem. Hint: First assume $a \ge 0$ and prove the statement by induction on $a$. Then extend the result to negative $a$ by reducing it to the case of positive $a$. No induction in this second part of the argument.
2A.4 DEF: We say that a subset $H\subseteq \zzz$ is a subgroup of $\zzz$ if (a) $H$ is not empty and (b) $H-H\subseteq H$. (Here $H-H$ denotes the set $\{a-b\mid a,b\in H\}$.) So what (b) says is that $(\forall a,b)((a,b\in H)\implies (a-b\in H))$. In other words, $H$ is closed under subtraction. Notation: we write $H\le \zzz$ if $H$ is a subgroup of $\zzz$.
2A.5 DO: Prove: For all $a$, the set $a\zzz$ (the set of multiples of $a$) is a subgroup of $\zzz$. We refer to these subgroups as cyclic subgroups: $a$ is called a generator of the cyclic subgroup $a\zzz$.
2A.6 DO: Prove: If $a$ is a generator of a cyclic subgroup $H\le\zzz$ then (1) $-a$ is also a generator of $H$, and (2) no other number is a generator.
2A.7 DO: Which cyclic subgroups of $\zzz$ are finite?
2A.8 HW. Prove: Every subgroup of $\zzz$ is cyclic.
Hint. Let $H\le\zzz$. We need to prove that
$(\exists d)(H=d\zzz)$. Prove the following facts in a sequence.
2A.8.1. $0\in H$. 2A.8.2.
$(a\in H) \implies (-a\in H)$.
2A.8.3. $(a,b\in H) \implies (a+b\in H)$.
2A.8.4. $(a\in H) \implies (a\zzz\subseteq H)$.
2A.8.5. If $H=\{0\}$ then $H$ is cyclic.
2A.8.6. If $H\neq\{0\}$ then $H$ has a positive element.
2A.8.7 Let $d$ be the smallest positive element of $H$.
Prove that $H=d\zzz$. Use the Division Theorem.
(1+1+1+1+1+1+5 points)
2A.9 DO (intersection of subgroups is a subgroup) Prove: If $H,K\le\zzz$ then $H\cap K\le\zzz$.
2A.10 DEF (least common multiple) Recall from the discussion session: We say that the number $c$ is a least common multiple of the numbers $a$ and $b$ if (a) $c$ is a common multiple, i.e., $a\mid c$ and $b\mid c$, and (b) $c$ is a common divisor of all common multiples, i.e., if $a|e$ and $b\mid e$ then $c\mid e$.
2A.11 DO: Prove: If $c$ is a least common multiple of $a$ and $b$ then (1) $-c$ is also a least common multiple of $a$ and $b$, and (2) there is no other least common multiple.
2A.12a CONVENTION: We write $\lcm(a,b)$ to denote the non-negative number among the least common multiples of $a$ and $b$. Example: $\lcm(-8,12)=24$.
2A.12b DO: Prove: $\lcm(a,a)=|a|$.
2A.13 DO:Prove: $c$ is a least common multiple of $a$ and $b$ if and only if $c\zzz = a\zzz\cap b\zzz$.
2A.14 DO: Prove: Every pair $(a,b)$ of integers has a least common multiple. Hint: Use the fact that $a\zzz\cap b\zzz$ is a subgroup.
2A.15 HW (due Thursday, October 6): Find all pairs $(a,b)$ of non-negative integers that satisfy the equation $\lcm(a,b)+a+b=ab.$ Prove your answer. (7 points)
2A.16 HW: Find all integers $x$ such that $6x\equiv 4 \pmod{28}$. Show all your work; the statement of the answer is not sufficient. Prove your answer. You need to prove that all numbers you found actually work and no other number works. (6 points)
2A.17 DO: Prove: If $a\equiv b \pmod m$ then $(\forall k\ge 0)(a^k\equiv b^k \pmod m)$. Hint. Induction on $k$.
2A.18 NOTATION. $(a \bmod m)$ denotes the smallest non-negative integer $r$ such that $a\equiv r\pmod m$. For instance, $(72 \bmod{11})=6$ and $(72 \bmod{-11})=6$ and $(-72 \bmod{11})=5$ and $(72 \bmod{0})=72$. Notice that for $m\neq 0$, the number $(a \bmod m)$ is a number $r$ in the interval $0\le r \le |m|-1$.
2A.19 HW: Compute $(3^{1,000,000} \bmod{11})$. Show all your work. Do not use any electronic devices. To solve this problem, you do not need to do any calculation you could not perform in your head. Your answer should be a number between $0$ and $10$. Clearly state and prove your answer. Your proof should be no more than two lines. Hint: Fermat's little Theorem. (5 points)
2A.20 HW (due Thursday, October 6): Find all integers $x$ that satisfy $x\mid x-12$. Clearly state the number of solutions. Prove your answer. (6 points)
2A.21 XC (Extra credit problem, not mandatory but you can hand it in on the deadline and receive credit for it that adds to your HW score. Highly recommended especially to those who seek to do research in Theory.) Find all pairs $(a,b)$ of positive integers that satisfy $a\mid b+1$ and $b\mid a+1$. Clearly state the number of solutions you found. Prove your answer. Grading has higher standards for XC problems; grading is based on correctness and elegance of your solution. (6 points)
2A.22 DO: Study the 2014 DM problem set #1
2A.23 CH: Find two infinite subsets $A,B$ of the set $\nnn$ of non-negative integers such that $(\forall a\in \nnn)(\exists! x\in A, y\in B)(x+y=a)$.
2A.24 CH: Let $f(x)$ be a polynomial with integer coefficients. Let $p$ be a prime number. Suppose $a$ is an integer such that $f(a)\equiv 0 \pmod p$ and $f'(a)\not\equiv 0 \pmod p$. Prove: $(\forall k\ge 0)(\exists b)(f(b)\equiv 0 \pmod{p^k})$.