The notation "MN" refers to the Matoušek--Nešetříl text (second edition). The first edition is also entirely adequate for this class. Note that a new Chapter 2 has been inserted in the second edition so for $i\ge 3$ if you can find something in Chapter $i$ in the second edition, it will appear in Chapter $i-1$ in the first edition.
The notation "LIN" refers to the instructor's Linear Algebra notes, currently in progress.
The notation "PZ" refers to the puzzle problem set from the instructor's 2011 REU course.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the instructor's attention) and no deadline (except they expire when discussed in class). Make sure you hand them in on a separate sheet, state your name, the fact that this is a challenge problem solution, and indicate the problem being solved. One further request: if you hand in a solution to a challenge problem, send email to the instructor giving the problem number and a brief indication of the problem (copied from the problem announcement: like "n+1 numbers" or "another limit related to the def of "e"" -- no detailed description needed, this suffices to remind me which problem it was). Such email will create an easy record and help avoid mistakes in bookkeeping.
REWARD PROBLEMS are challenge problems that you should NOT hand in. The solution is its own reward. No deadline. Of course you are welcome to discuss your thoughts with the TA, the instructor, and your peers.
If you hand in material before its due date, make sure you put it on a separate sheet since solutions are graded in batches by their due dates.
14.1 DO: Prove: there exists a reducible Markov Chain (transition digraph not strongly connected) which has a unique stationary distribution.
14.2 HW: Let $T$ be a stochastic matrix and suppose the limit $L = \lim_{k\to\infty} T^k$ exists. Prove: each row of $L$ is a stationary distribution. (6 points)
14.3 HW: Suppose $\pi=(\pi_1,\dots,\pi_n)$ is a stationary distribution for an irreducible Markov Chain. Prove: $(\forall i)(\pi_i > 0)$. (8 points)
14.4 HW: Let $T$ be a stochastic matrix. Prove: $T$ is irreducible if and only if for all sufficiently large $k$ the matrix $(T+I)^k$ is positive (i.e., all of its entries are positive). ($I$ denotes the identity matrix.) (10 points)
14.5 DO: Let $a_1,\dots,a_m$ be nonnegative integers. Prove: if $\gcd(a_1,\dots,a_m)=1$ then all sufficiently large integers can be written in the form $a_1x_1+\dots+a_mx_m$ where all the $x_i$ are nonnegative integers.
14.6 DO: Let $T$ be a stochastic matrix. Prove: $T$ is ergodic (irreducible and aperiodic) if and only if for all sufficiently large $k$ the matrix $T^k$ is positive.
14.7 DO (convergence of a finite Markov Chain): LN 8.1.8. (Prove the convergence of the powers of a certain 2 × 2 stochastic matrix.) State the limit matrix. -- Your proof should be short. Elegance counts.
14.8 DO: LN 8.1.17. (Prove that the powers of a certain 2 × 2 stochastic matrix do not converge; find a stationary distribution.)
14.9 HW (due Tuesday, November 29): Let $A$ be an $n \times n$ complex matrix and let $G = ([n], E)$ be the associated digraph ($ i\to j$ exactly if $a_{ij}\neq 0$). Suppose $G$ is strongly connected and has period $d$. Prove: if $\lambda$ is an eigenvalue of $A$ and $\omega$ is a complex $d$-th root of unity (i.e., $\omega^d = 1$) then $\lambda\omega$ is also an eigenvalue. (10 points)
13.1 DO: Prove: a digraph is strongly connected if and only if it does not have a directed cut, i.e., a partition $V = A \dot\cup B$ such that $A, B$ are not empty and there is no edge from $B$ to $A$.
13.2 HW: We say that a digraph is Eulerian if every vertex has the same indegree as its outdegree. Prove: if an Eulerian digraph is weakly connected then it is strongly connected. (8 points)
13.3 HW: Prove: if a digraph is strongly connected then its period is equal to the gcd of the lengths of its cycles. (10 points)
13.4 HW: Find a finite Markov Chain with more than one stationary distribution. Your example should have as few states as possible. (6 points)
12.1 HW (strong concentration of degrees) : Let $C_n$ be a sequence of real numbers that approaches infinity (arbitrarily slowly) as $n\to\infty$. (Think, for instance, that $C_n = \ln \ln \ln n$.) Let $a_n =\sqrt{(n/2)(C_n +\ln n)}$. Prove: for almost all graphs on $n$ vertices, the degree of every vertex is within the interval $[(n-1)/2-a_n,(n-1)/2+a_n]$. (Note: the statement in class was weaker; solve this version instead.) (10 points)
12.2 HW ("typical is less than expected" revisited): Let us roll a standard die $n$ times; let $X_n$ denote the product of the $n$ numbers shown. Prove that $P(X_n\ge E(X_n))$ is exponentially small, i.e., there is a constant $C>1$ such that for all sufficiently large $n$ we have $P(X_n\ge E(X_n)) \le C^{-n}$. Hint: Let $Y_n = \ln X_n$. Note that $Y_n$ is the sum of independent random variables. Shift (to get zero expected value), normalize (to get the bound 1), and apply Chernoff's bound. This exercise requires no numerical calculation. (18 points)
12.3 HW (dual graphs): Find a planar multigraph with two non-isomorphic duals (i.e., your graph should have two very different plane drawings). Use few edges. (8 points)
12.4 DO: Prove Euler's formula for connected plane multigraphs.
12.5 HW (6CT): (a) Prove: every planar graph has a vertex of degree $\le 5$. (Use a result proved in class.) (b) Prove: every planar graph is 6-colorable. (Use part (a); your proof should be very short.) (4+8 points)
12.6 DO (simple generating functions): Find closed-form expressions for the generating functions of the following sequences: (a) $a_n = 1/n!$ (b) $b_n = n$ (c) $c_n = n^2$ (d) $d_n = 1/n$.
12.7 HW (linear recurrence): Consider the sequence $a_n$ defined by the recurrence $a_n = a_{n-1} + 6a_{n-2}$ (for $n\ge 2$), with initial values $a_0=3$ and $a_1=-7$. (a) Find a closed-form expression for the generating function of this sequence. (b) Write this closed-form expression as the sum of partial fractions. (c) Use (b) to find a simple explicit formula for $a_n$. Show all your work. (6+6+4 points)
12.8 HW: Newton's binomial coefficient $\binom{z}{k}$ is defined for any complex number $z$ and any nonnegative integer $k$ as follows: $\binom{z}{k} = z(z-1)\dots(z-k+1)/k!$. Solve LN 5.1.3 (a) and (b). (4+8 points)
12.9 DO: LN 5.2.5 (generating function of $na_n$).
12.10 DO: LN 5.2.6 (non-homogeneous Fibonacci recurrence)
12.11 DO: (a) State and prove the Multinomial Theorem: the expansion of the expression $(x_1+\dots + x_k)^n$. (b) What is the number of terms in this expansion?
12.12 DO: LN 6.1.18 (number of spanning trees of $K_n$ with prescribed degrees) (Hint: show that under the given conditions, one of the $d_i$ must be 1. Now proceed by induction on $n$.)
12.13 HW (Cayley's formula): Use the preceding exercise to prove Cayley's formula that the number of spanning trees of $K_n$ is $n^{n-2}$. (8 points)
12.14 CHALLENGE PROBLEM: LN 6.1.22 (max number of edges of a graph without 4-cycles)
12.15 DO (Grötzsch's graph: 4-chromatic graph without triangles): LN 6.1.17.
12.16 DO: Construct a graph that is bipartite, not planar, and does not contain a topological $K_{3,3}$.
12.17 DO: Prove that the probability $p_n$ that a random graph on $n$ vertices is planar is very small: for all sufficiently large $n$ we have $p_n < 2^{-0.49 n^2}$.
11.1 HW (Ramsey's Theorem, another baby case) : (a) Define the Erdos - Rado arrow symbol $n\to (k,\ell,m)$. (b) Prove: $17 \to (3,3,3)$. (2+7 points)
11.2 HW: Prove: $(\forall k)(k^2 \not\to (k+1,k+1))$. (8 points)
11.3 HW: Prove: almost all graphs are not planar. (Define what this statement means.) (10 points)
10.1 HW (variance of the number of triangles): Let $G$ be a random graph on a given set of $n$ vertices. (Adjacency is decided by flipping a fair coin for each pair of vertices.) Let $X_n$ denote the number of triangles in $G$. (a) Compute $\var(X_n)$. (Give a closed-form expression.) (b) Asymptotically evaluate your answer (give a simple expression which is asymptotically equal to $\var(X_n)$). The result should be of the form $an^b$; determine the constants $a$ and $b$. (c) Asymptotically compare your answer to the variance of $H_n$, the number of heads in $\binom{n}{3}$ coin flips. [Note: the word "asymptotically" was added on 11/8 at 12:55am. If you missed it, it is ok, but this clarification can make your job easier.] (d) Does the "weak law of large numbers" hold for $X_n$? Briefly argue your answer. (e) For large $n$, which random variable is more concentrated (has smaller variance): $X_n$ or $H_n$? [Note: the words "for large $n$" were added on 11/8 at 12:55am. If you missed this, it is ok, but this clarification can make your job easier.] (10+3+2+2+2 points)
10.2 HW ("typical is less than expected"): Let us roll a standard die $n$ times; let $X_n$ denote the product of the $n$ numbers shown. (a) Determine $E(X_n)$. (b) Prove that for all sufficiently large $n$, $P(X_n\ge E(X_n)) < 0.01$. Hint: Let $Y_n = \ln X_n$. Determine $E(Y_n)$ and $\var(Y_n)$. Apply Chebyshev's inequality to $Y_n$. (2+15 points)
10.3 HW: Prove that almost all graphs have diameter 2. In other words, let $p_n$ denote the probability that a random graph on a given set of $n$ vertices has diameter 2. You need to show that $\lim_{n\to\infty} p_n = 1$. Hint: show that it is exponentially unlikely that a pair of vertices does not have a common neighbor. (12 points)
10.4 DO: Prove: every connected graph has a spanning tree.
10.5 DO: Verify Cayley's $n^{n-2}$ formula (for the number of spanning trees of the complete graph $K_n$) for $n=6$. Hint: For $n=6$, list all non-isomorphic trees on $n$ vertices: $T_1,\dots,T_k$. Let $a_i$ be the number of automorphisms of $T_i$. Determine each $a_i$. Verify that $n! \sum_i 1/a_i = n^{n-2}$.
10.6 DO (exponential beats polynomial growth): Prove: $(\forall k)(\forall c>0)(n^k = o(\exp(n^c)))$. (We used the notation $\exp x = \eee^x$.) Use the fact from calculus that $\ln x = o(x)$. Do not use calculus beyond this fact (and basic properties of limits). Use substitution of variables and basic algebra.
9.1 HW: Prove: if a graph with $n$ vertices is self-complementary (isomorphic to its complement) then $n \equiv 0$ or $1 \pmod 4$. (6 points)
9.2 HW: Let $z_n$ denote the number of independent sets in the path $P_n$ of length $n-1$. Determine $z_n$. Prove your answer. (8 points)
9.3 HW: Let $\alpha(G)$ denote the size of the largest independent set in the graph $G$ and let $\chi(G)$ denote the chromatic number of $G$. Prove: $\alpha(G)\chi(G) \ge n$. (8 points)
9.4 CHALLENGE PROBLEM (chromatic polynomial). Let $G$ be a graph on $n$ vertices and $x$ a positive integer. Let $f_G(x)$ denote the number of legal colorings $f\,:\,V(G)\to [x]$. Show that $f_G$ is a polynomial of $x$ of degree $n$.
Click here for the "DO" exercises (kindly posted by Anna Olson).
8.1 HW: (a) Prove: pairwise independence of three events does not imply (full) independence. Make your sample space as small as possible. (b) Prove that your sample space is smallest possible, in no more than four sparsely written lines, with reference to a "DO" exercise also assigned in class on Tuesday, Oct 25. You need to state that exercise in full within your four lines. (8 + 3 points)
8.2 HW: Count and draw all trees on seven vertices up to isomorphism. (11 points) Lose 2 points per error. Error: (a) you miss an isomorphism class; (b) you draw a redundant graph (that is isomorphic to a graph previously listed). (The deductions stop at zero, so you get zero points if you make 6 or more errors.)
8.3 HW: Determine the expected number of triangles in a random graph on a given set of n vertices. (Random: edge probability = 1/2 independently for each pair of vertices.)
Click here for the "DO" exercises (kindly posted by Anna Olson).
7.1 DO (inverting the PNT): Let $p_n$ denote the $n$-th prime number. Prove: $p_n\sim n\ln n$. Use the
Prime Number Theorem: Let $\pi(x)$ denote the number of primes $\le x$. Then $\pi(x) \sim x/\ln x$. (Hint: notice that $\pi(p_n) = n$.)
7.2 HW (inverting an asymptotic equality): Let $\{a_n\}$ be a sequence of positive real numbers. Prove that the following two statements are equivalent: (a) $a_n^2 \ln a_n \sim n$ (b) $a_n \sim \sqrt{2n/\ln n}$. (10 points)
7.3 HW (asymptotics of logarithm): Let $a_n$ and $b_n$ be sequences of positive reals. Consider the following statement. "If $a_n = \Theta(b_n)$ then $\ln a_n \sim \ln b_n$."
(a) Prove that the statement is false even under the additional assumption that $a_n \ge 2$ and $b_n \ge 2$.
(b) Prove that the statement is true under the additional assumption that $a_n \to\infty$. (4+8 points)
7.4 DO (log grows slowly): Prove: $\ln n = o(n^{0.001})$. (We used the little-oh notation here.)
7.5 DO (polynomial growth): Recall that a sequence $\{a_n\}$ is polynomially bounded if there exists $k$ such that $a_n = O(n^k)$.
Let $a_n \ge 1$. Prove: $\{a_n\}$ is polynomially bounded if and only if $\ln a_n = O(\ln n)$.
ADDITIONAL "DO" EXERCISES were stated in class.
6.1 HW (counting monotone functions): Let $[n]$ denote the set $\{1,2,\dots,n\}$. Count the monotone functions $f : [n] \to [k]$ where $n,k$ are positive integers. Your answer should be a simple closed-form expression (no summation or product symbols, no dot-dot-dots; you may use binomial coefficients, factorials). A function $f : [n]\to [k]$ is monotone if $(\forall x,y\in [n])(x\ge y \Rightarrow f(x)\ge f(y))$. Your solution should be very simple, by reduction to a result proved in class. State the result you require. Do not repeat the proof of that result. (8 points)
6.2 DO: Count the solutions to the equation $x_1+\dots+x_n = k$ where the $x_i$ are integers and $(\forall i)(x_i \ge 2)$. ($n$ and $k$ are given positive integers.)
6.3 HW (truncated Inclusion-Exclusion): Let $A_1,\dots,A_m$ be subsets of the universe $\Omega$ (a finite set). Let $B = \Omega\setminus \bigcup_{i=1}^m A_i$. Recall that the Inclusion-Exclusion Formula says that $|B| = S_0 - S_1 + S_2 - + \dots$ where $S_j$ is the sum of the sizes of the $j$-wise intersections of the $A_i$. (Review this from the text and/or web sources.) Prove: $|B| \le S_0 - S_1 + S_2.$ (8 points) (Note: typo in definition of $B$ corrected 10-15 7:50pm.)
6.4. CHALLENGE PROBLEM (Bonferroni's inequalities): With the notation of the preceding exercise, prove that $|B| \le S_0 - S_1 + S_2 + - \dots + S_{2k}$ and $|B| \ge S_0 - S_1 + S_2 + - \dots - S_{2k+1}$ for all $k$.
6.5: Review LN Chap. 7.1 (Finite Probability Spaces and Events) from 7.1.1 to 7.1.15, including the concept of conditional probability. Review LN Chap 7.2 (Random Variables and Expected Value) except Ex. 7.2.14 and Ex. 7.2.17.
6.5 HW (correlation of divisibility): Let $n$ be a positive integer. Pick a number $x\in [n]$ at random. Let $A(n)$ denote the event that $2\mid x$ and $B(n)$ the event that $3\mid x$. (a) Determine (a1) $P(A(n))$ (a2) $P(B(n))$ (a3) $P(A(n)\cap B(n))$ (b) Depending on the residue class of $n$ modulo 6, determine whether $A(n)$ and $B(n)$ are independent, positively correlated, or negatively correlated. (Your answer should be a list of 6 statements of the form: "if $n\equiv i\pmod 6$ then $A(n)$ and $B(n)$ are ..." ($i=0,1,\dots,5$). (2+2+2+10 points)
6.6 DO: Consider the uniform probability space over the sample space $\Omega$. Prove: if $|\Omega|$ is a prime number then no two nontrivial events are independent. (The trivial events are $\Omega$ and $\emptyset$.)
6.7 DO: LN 7.1.2 (questions about bridge cards)
6.8 DO: LN 7.1.3 ("modular equation")
6.9 DO: LN 7.1.5 (union bound)
6.10 DO: LN 7.1.7 (conditional probabilities multiply)
6.11 DO: LN 7.1.11 (independence via conditional probabilities)
6.12 DO: LN 7.1.12 (independence of complement)
6.13 DO: LN 7.1.13 (independence of die events)
6.14 DO: LN 7.1.8 (sum of three dice)
6.15 DO: LN 7.1.14 (independence/correlation of "sum of dice" events)
6.16 DO: LN 7.1.9 (Theorem of Complete Probability)
6.17 HW (Probability of causes) Diseases $A$ and $B$ have similar symptoms. Let $W$ be the population of all patients showing these symptoms. The two diseases can only be differentiated by costly tests. We know (from sampling the population and performing these costly tests) that $70\%$ of $W$ have disease $A$, $25\%$ have disease $B$, and $5\%$ have some other disease. We consider the effectiveness of treatment $T$. We know that $60\%$ of the patients with disease $A$ respond to $T$, while only $12\%$ of the patients with disease $B$ respond to treatment $T$. From the rest of the population $W$, $40\%$ respond to treatment $T$.
(a) A new patient arrives at the doctor's office. The doctor determines that the patient belongs to $W$. What is the probability that the patient will respond to treatment $T$?
(b) The patient's insurance will not pay for the expensive tests to differentiate between the possible causes of the symptoms. The doctor bets on treatment $T$. A week later it is found that the patient did respond to the treatment. What is the probability that the patient had disease $A$? Show all the intermediate results you need to compute. (8+8 points)
6.18 DO: LN 7.2.3 (computing expected value as sum over range)
6.19 DO: LN 7.2.4 (expected value is between min and max)
6.20 DO: LN 7.2.5, 7.2.6 (additivity, linearity of expected value)
6.21 HW (expected value of indicator variable): LN 7.2.8. (4 points)
6.22 DO: LN 7.2.9 (a) CHALLENGE: LN 7.2.9 (b) (random variables vs. indicator variables)
6.23 DO: Study LN 7.2.10 (Markov's Inequality)
6.24 DO: LN 7.2.11 (expected number of runs of $k$ heads)
6.25 DO: LN 7.2.12 (lottery)
6.26 HW (Bernoulli trials, due Thursday, October 20): Let $0 < p < 1$ be the probability that a biased coin lands on heads. Let $b(n,k)$ denote the probability that out of $n$ flips of our biased coin, exactly $k$ land on heads. Recall that $b(n,k) = \binom{n}{k}p^k(1-p)^{n-k}$. Prove that the sequence $b(n,0), b(n,1),\dots, b(n,n)$ is unimodal, meaning that it increases to its maximum and then it decreases. The increase and decrease are strict except that the two largest (consecutive) terms may be equal. For what value of $k$ is $b(n,k)$ maximal among all $b(n,j)$ $(0\le j\le n)$? (14 points)
5.1 DO: (a) Assume $a\neq 0$. Prove: $ax \equiv ay \pmod{am}$ if and only if $x \equiv y \pmod m$. (Note: the assumption $a\neq 0$ was added 10/12 5:45pm.)
(b) Prove: The congruence $ax\equiv b \pmod m$ is solvable if and only if $\gcd(a,m) \mid b$.
(c) Decide the solvability, and if solvable, find all solutions of each of the following congruences:
(c1) $84x \equiv 70 \pmod{126}$
(c2) $70y \equiv 84 \pmod{126}$
5.2 DO: Let $p$ be a prime $p$ and assume $1\le k\le p-1$. Prove: $p\mid \binom{p}{k}$.
5.3 HW: Use 5.2 to prove Fermat's little Theorem. (Hint: first prove that FlT is equivalent to the statement that $(\forall a)(a^p \equiv a \pmod{p})$. Then prove this statement for $a \ge 0$ by induction on $a$.) (10 points)
5.4 CHALLENGE. Prove that for every $N\ge 5$, the gcd of all numbers of the form $p^2-1$ where $p$ is a prime greater than $N$, is 24. (You may use a big theorem: Dirichlet's Theorem about primes in arithmetic progressions (look it up), but best is if you avoid using big guns and prove the result from first principles.)
4.1 HW (Fermat's little Theorem) Compute $10^{10^{10^{10}}} \bmod {17}$. Show all your work. (6 points) (Clarification added 10/9 at 8:15pm: Your answer should be an explicit integer between $0$ and $16$.)
4.2 DO (composite modulus) Assume $\gcd(m,n)=1$. Prove: $(\forall a,b)(a\equiv b \pmod{mn}) \Leftrightarrow a\equiv b \pmod{m}$ AND $a\equiv b \pmod{n}$)
4.3 HW Prove: $(\forall a)(a^{13}\equiv a\pmod{65})$. You may use Problem 4.2 without proof. (9 points) (Note: the right-hand side was initially erroneously given as `1' instead of `$a$'. Corrected Jan 9, 12:45 PM. The discoverer of the error received bonus points.)
4.4 DO Prove the Euler-Fermat congruence: if $\gcd(a,m)=1$ then $a^{\varphi(m)}\equiv 1 \pmod m$.
4.5 DO (multiplicativity of Euler's $\varphi$ function): (a) Prove: if $a, b \ge 1$ and $\gcd(a,b)=1$ then $\varphi(ab) = \varphi(a)\varphi(b).$ (Hint: Use the Chinese Remainder Theorem (CRT).) (b) Prove: $$\frac{\varphi(n)}{n} = \prod_{p\mid n} \left(1-\frac{1}{p}\right) $$ where $p$ ranges over the prime divisors of $n$.
4.6 CHALLENGE PROBLEM. Prove: $\inf \frac{\varphi(n)}{n} = 0$, where $n$ ranges over the positive integers.
4.7 HW (CRT) Consider the following system of simultaneous
congruences:
$x\equiv 5 \pmod 8$
$x\equiv 2 \pmod {11}$
$3x\equiv 7 \pmod {13}$
Prove that this system has a solution. (Your proof should involve no calculation, only correct references to results learned in class.) (7 points)
4.8 DO: Find all solutions of the system of congruences given in the preceding exercise.
4.9 HW (CRT?)
Decide whether or not the following system of simultaneous
congruences has a solution. Prove your answer.
$x\equiv 11 \pmod{21}$
$x\equiv 5 \pmod{12}$
$x\equiv 1 \pmod{14}$
Your proof should be very short, only a few lines. (7 points)
4.10 DO: Find integers $x,y$ such that $47x+63y =1$. Show your work.
4.11 DO: Prove: If $p$ is a prime number and $x^2\equiv 1 \pmod p$ then $x\equiv \pm 1\pmod p$.
4.12 HW (due Thursday, Oct 13): Suppose $p,q$ are distinct odd primes. Prove: $(\exists x)(x^2\equiv 1\pmod{pq}$ but $x\not\equiv \pm 1 \pmod{pq} )$. (10 points)
3.1 DO (multiplication of congruences): Prove: if $a\equiv x \pmod m$ and $b\equiv y \pmod m$ then $ab\equiv xy \pmod m$. (Hint: first prove that if $r\equiv s \pmod m$ then $rx\equiv sx \pmod m$; then use transitivity of congruence mod $m$.)
3.2 HW (gcd with residue class): Prove: if $a\equiv b \pmod m$ then $\gcd(a,m) = \gcd(b,m)$. (6 points)
3.3 DO (multiplicative inverse): Prove: if $a$ has a multiplicative inverse mod $m$ then $a$ and $m$ are relatively prime (i.e., $\gcd(a,m)=1$). (The converse was proved in class.)
3.4 HW (computing multiplicative inverses): Find the following multiplicative inverses:
(a) $7^{-1} \pmod{23}$.
(b) $(2k+1)^{-1} \pmod{3k+1}$. (Here $k\ge 1$.)
Show your work (show how you got the answer). Each answer should be a positive integer that is less than the modulus. (3+6 points)
3.5 DO: Prove: if $p$ is a prime and $p\ge 5$ then $p\equiv\pm 1\pmod 6$.
3.6 DO: Find a prime $p$ such that $100^2 \equiv -1 \pmod p$. Tell how you found $p$. (You may use computer tools.)
Problems 2.1 and 2.2 are slight variations from the versions stated in class. The posted versions are definitive.
2.1 HW (characterisation of gr.c.d.): Prove: if $d$ is a common divisor of $a$ and $b$ and $d$ can be written as a linear combination of $a$ and $b$ (with integer coefficients) then $d$ is a greatest common divisor of $a$ and $b$. (5 points)
2.2 HW ($p^2-1$ numbers): Determine the gcd of all numbers of the form $p^2-1$ where $p\ge 11$ is prime. Prove your statement. (10 points)
2.3 DO: prove the uniqueness of prime factorization using the theorem that the prime numbers have the prime property (if a prime $p$ divides a product $ab$ then $p\mid a$ or $p\mid b$). (Do not hand in the solution of "DO" exercises.)
2.4 HW (sum and intersection of subgroups): (a) Write the set $24\zzz + 42\zzz$ in the form $d\zzz$ for some $d$. (Determine $d$ and prove that $d\zzz = 24\zzz + 42\zzz$.) (b) Do the same with the set $24\zzz\cap 42\zzz$. (5+5 points)
2.5 HW: Let $\nnn =\{0,1,2,\dots\}$ denote the set of nonnegative integers. Prove that the set-difference $\nnn\setminus (5\nnn + 8\nnn)$ is finite. Find the largest number in this set. (8 points)
2.6. HW: True or false? Give very simple proofs. Remember: to prove the statement, you need to devise a winning strategy for the existential player (tell its moves as a function of the history of the game so far); to disprove it, you need to devise a winning strategy for the universal player. (The domain of the variables is $\zzz)$.
(a) $(\forall x)(\exists y)(\forall z)(z\mid x+y)$.
(b) $(\forall x)(\exists y)(x+y \mid x^2+y^2)$.
(c) $(\exists x,y)(\forall z)(\gcd(x+z,y+z) \mid \gcd(x+z+1,y+z+1))$
(d) $(\forall x,y)(\exists z)(\gcd(x+z,y+z) \mid \gcd(x+z+1,y+z+1))$
(5+5+5+5 points)
2.7 HW: Recall that two integers are relatively prime if their gcd is 1. Find three integers $x,y,z$ such that $\gcd(x,y,z)=1$ but $x,y,z$ are pairwise not relatively prime (i.e., $\gcd(x,y)\neq 1$, $\gcd(y,z)\neq 1$, $\gcd(x,z)\neq 1$). (State your numbers, do not prove.) (4 points)
2.8 HW (due Thu, Oct 6): LN 4.1.15 (c) (10 points) (Upper bound on the number of divisors)
2.9 DO: LN 1.2.5 (d)(f)(h) (logic and numbers)
2.10 DO: LN 4.1.27 (logic and gcd)
2.11 DO: (a) Define the least common multiple in analogy with our definition of the greatest common divisor.
(b) Prove that l.c.m. exists. Hint: do not try to mimic the proof of the existence of a g.c.d.; use instead the fact that g.c.d. exist: represent the l.c.m. as the g.c.d. of a certain set of numbers (which numbers?).
(c) LN 4.2.10: $\gcd(a,b)\lcm(a,b)= |ab|$.
2.12 DO: Find a sequence of real numbers which is bounded but has no limit.
2.13 DO: Determine the limits of the following sequences as $n\to\infty$.
(a) $\frac{7n^2+3n-100}{3n^2+10n+1000}$ ; (b) $\frac{\ln n}{\sqrt{n}}$ ; (c) $\frac{n^{100}}{1.001^n}$.
2.14 DO: Determine the limits of the following functions as $x\to 0$.
(a) $\frac{\ln(1+x)}{x}$ ; (b) $\frac{\sin x}{x}$; (c) $\frac{\sqrt{1+x} -1}{x}$;
2.15 DO: Recall that two sequences $a_n$ and $b_n$ are asymptotically equal if $\lim_{n\to\infty} a_n/b_n = 1.$ Notation: $a_n \sim b_n$. Here, fractions of the form $0/0$ are replaced by 1. Find very simple expressions that are asymptotically equal to each of the following expressions.
(a) $3n^4 +5n -100$ (b) $n + \cos n$ ; (c) $\sqrt{n^2+1}$ ; (d) $\sqrt{n^2+1}-n$ ; (e) $\binom{n}{5}$ ; (f) $\sum_{k=1}^n 1/k$.
2.16 DO: Prove: $\ln(n!) \sim n\ln n.$ Do not use any theorems, just the definition of asymptotic equality and basic properties of limits and logarithms. (Hint: notice that trivially, $\ln(n!) \le n\ln n$. Prove that for every $k$ we have $k^{n-k} < n!$ (assuming $1\le k\le n$). Choose $k=\lfloor n/\ln n \rfloor$ to get a lower bound that is asymptotically equal to $n\ln n$.)
2.17 DO: True or false (prove): If $a_n \sim b_n$ then
(a) $a_n^2 \sim b_n^2$ ; (b) $\sqrt{a_n} \sim \sqrt{b_n}$ ; (c) $2^{a_n} \sim 2^{b_n}$.
2.18 HW: Assume $a_n, b_n > 1$.
Consider the following statement:
"If $a_n\sim b_n$ then $\ln a_n \sim \ln b_n.$"
(a) Prove that the statement is false. (Remember: $a_n, b_n >1$.)
(b) Prove that the statement becomes true if $a_n$ is bounded away from 1, i.e., $(\exists c>0)$ such that $a_n \ge 1+c$ for all sufficiently large $n$. (5+8 points)
If you hand in solutions to CHALLENGE PROBLEMS, please put them on a separate sheet clearly marked "CHALLENGE."
2.19 CHALLENGE PROBLEM: LN 4.3.4. (Determinant of gcd's.)
2.20 CHALLENGE PROBLEM: LN 4.2.13 (Integer-preserving polynomials)
2.21 CHALLENGE PROBLEM: LN 4.2.2, part 2. (Divisor game)
2.22 REWARD PROBLEM: LN 4.2.6: $\gcd(a^m-1, a^n-1)$.
2.23 CHALLENGE PROBLEM: LN 4.2.8 (gcd of Fibonacci numbers)
2.24 CHALLENGE PUZZLE: PZ 14 (unique sums)
2.25 CHALLENGE PUZZLE: PZ 3 (infection)
1.1 HW (sum of three squares): Prove that there are infinitely many positive integers that cannot be written as the sum of three squares. (Hint: experiment with small numbers (say up to 50); notice pattern; formulate conjecture; prove.) (8 points)
1.2 HW (multiplication distributes over gcd): Let $a,b,c$ be integers. Let $A = \gcd(ac,bc)$ and $B = \gcd(a,b)\cdot |c|$. We claim that $A = B$. In class we proved $B\, |\, A$. To complete the proof of the claim, prove that $A\, |\, B$. Use the theorem (stated but not yet proved in class) that the greatest common divisor can be written as a linear combination. Do not use unique prime factorization. (8 points)
1.3 CHALLENGE PROBLEM. Prove that in the divisor game over the positive divisors of the number $n\ge 2$, the first player has a winning strategy.