x
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.
HW 5.1 Asymptotically evaluate the binomial coefficient $\binom{2n}{n}$. Your answer should be a function of the form $a b^n n^c$ where $a,b,c$ are constants. Determine $a,b,c$. Use Stirling's formula. (6 points)
5.2 DO: Examine the Pascal triangle modulo 2. Admire the pattern and make mathematical statements about it. Prove. (See: "Sierpinski gasket")
5.3 DO: In class we proved $\sum_{k=0}^{n} \binom{n}{k}^2=\binom{2n}{n}$. Generalize the result: evaluate $\sum_{k=0}^{r} \binom{n}{k}\binom{m}{r-k}$. Give two proofs: a combinatorial proof (what does this sum count?) and an algebra proof (based on the binomial theorem).
5.4 DO: Prove: For all $n\ge 1$ we have $n! > (n/\eee)^n$. Note that Stirling's formula does not apply; use the power series expansion of $\eee^x$ instead.
5.5 DO: (a) Prove the union bound:
$P(\bigcup_{i=1}^k A_i) \le \sum_{i=1}^k P(A_i)$.
(b) Prove the modular equation:
$P(A\cap B) + P(A\cup B) = P(A) + P(B)$.
4.1 DO: Review Problem 3.13.
4.2 DO: Let $d=\gcd(a,b)$. Prove: $\gcd(a/d,b/d)=1$. The solution should be half a line based on a result we proved in class.
4.3 DO: Prove: if $\gcd(a,c)=1$ then $\gcd(a,bc) =\gcd(a,b)$.
4.4 DO: Prove: $\gcd(a,b)\neq 1$ if and only if there exists a prime number $p$ that divides both $a$ and $b$.
4.5 DO: The Chinese Remainder Theorem makes the assumption that the moduli $m_i$ are pairwise relatively prime and concludes that the given system of congruences has a solution. Prove that this sufficient condition is not necessary: find a system of congruences where the moduli are not pairwise independent and yet the system has a solution. In fact, given any list of moduli $m_1,\dots, m_k$, find values $a_1,\dots,a_k$ such that the system of congruences $x\equiv a_i \pmod {m_i}$ $(i=1,\dots,k)$ has a solution (i.e., there exists an $x$ that satisfies all congruences simultaneously).
4.6 DO: Assume the numbers $m_1,\dots,m_k$ are pairwise relatively prime. Let $S_j$ be the product of all the $m_i$ except $m_j$. Prove: $\gcd(S_1,\dots,S_k)=1$.
4.7 DO (CRT) Consider the following system of simultaneous
congruences:
$x\equiv 5 \pmod{24}$
$x\equiv 2 \pmod {33}$
$3x\equiv 7 \pmod {26}$
Prove that this system has a solution. Your proof should be short and elegant, involve no calculation, only correct references to results learned in class. Do not calculate a solution, only prove it exists.
4.8 DO: Find all solutions of the system of congruences given in the preceding exercise.
4.9 DO (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 line or two.
4.10 DO: Let $p$ be a prime number. Prove that the only solutions of the congruence $x^2 \equiv 1 \pmod p$ are $x\equiv \pm 1 \pmod p$.
4.11 HW: Let $p,q$ be distinct odd primes. Prove that the congruence $x^2\equiv 1 \pmod {pq}$ has four solutions modulo $pq$. (Don't forget to prove that the four solutions you found are indeed pairwise not congruent modulo $pq$.) (8 points)
4.12 DO: Express the following binomial coefficients in terms of ordinary binomial coefficients. (The binomial coefficient $\binom{n}{k}$ is "ordinary" if both $n$ and $k$ are nonnegative integers.) (a) $\binom{-n}{k}$ (b) $\binom{-1/2}{k}$. ($n$ and $k$ are nonnegative integers.)
4.13 DO: Recall the Multinomial Theorem: $$(x_1+\dots+x_t)^n = \sum_{k_i\ge 0, \sum k_i=n} \binom{n}{k_1,\dots,k_t} x_1^{k_1}\cdots x_t^{k_t}.$$ Evaluate the multinomial coefficients: prove that $$\binom{n}{k_1,\dots,k_t}= \frac{n!}{k_1!\cdots k_t!} .$$
4.14 HW (due Tuesday, October 22): Count the terms in the Multinomial Theorem (the sum of how many terms is on the right-hand side?). Your answer should be a single, simple binomial coefficient involving the parameters $n$ and $t$. Prove your answer. (Note: to check the plausibility of your answer, verify that for $t=2$ your answer gives $n+1$, the number of terms in the Binomial Theorem.) (8 points)
4.15 CHALLENGE PROBLEM. Let $S(n,3)$ denote the sum $\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\dots$ (the number of subsets of size divisible by 3). Prove: $|S(n,3) - 2^n/3| < 1$.
3.1 DO (due Thursday, Oct 17) (Euler's $\varphi$ function): Recall that $\varphi(n)$ denotes the number of reduced residue classes modulo $m$, or equivalently the number of those integers among $\{1,2,\dots,n\}$ that are relatively prime to $n$. (i) Prove that the $\varphi$ function is multiplicative, i.e., if $\gcd(a,b)=1$ then $\varphi(ab) = \varphi(a) \varphi(b) $. (ii) Infer that if $p,q$ are distinct primes then $\varphi(pq) = (p-1)(q-1)$. (iii) Infer that if $n=p_1^{k_1}\dots p_r^{k_r}$ where the $p_i$ are distinct primes then $\varphi(n) = n(1-1/p_1)\cdots(1-1/p_r)$.
3.2 CHALLENGE. Prove that $\inf \varphi(n)/n = 0$. Hint. Use the following Lemma. Let $a_1, a_2,\dots$ be a sequence of real numbers such that $0\le a_i <1$. Prove: $\prod_{i=1}^{\infty} (1-a_i) = 0$ if and only if $\sum_{i=1}^{\infty} a_i = \infty$.
3.3 DO: Prove: $\sum_{d\mid n} \varphi(d) = n$. (i) Give a simple direct proof, do not use problem 3.1. (ii) Use the multiplicativity of $\varphi$ to prove that $\sum_{d\mid n} \varphi(d)$ is multiplicative. Verify the result for prime power values of $n$.
3.4 HW (simplifying a congruence)
(a) Prove: if $a\mid bc$ and $\gcd(a,b)=1$ then $a\mid c$.
(b) Prove: if $ax \equiv ay \pmod m$ and $\gcd(a,m)=1$ then
$x\equiv y \pmod m$.
(c) Let $d=\gcd(a,m)$. Assume $d\neq 0$. Prove:
$ax\equiv ay \pmod m$ if and only if
$x\equiv y \pmod{m/d}$.
(3+4+3 points)
3.5 HW (computing multiplicative inverses): Find the following multiplicative inverses:
(a) $6^{-1} \pmod{19}$.
(b) $k^{-1} \pmod{2k+1}$. (Here $k\ge 1$.)
(c) $k^{-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. (2+4+4 points)
3.6 HW Recall that a reduced set of residues modulo $m$ is a set of $\varphi(m)$ integers, one from each reduced residue class modulo $m$. (A residue class is reduced if its elements are relatively prime to $m$.) Let $r_1,\dots, r_{\varphi(m)}$ be a reduced set of residues modulo $m$ and assume $\gcd(a,m)=1$. Prove that $ar_1,\dots,ar_{\varphi(m)}$ is also a reduced set of residues modulo $m$. (6 points)
3.7 DO: Recall that Fermat's little theorem says: if $p$ is a prime and $\gcd(a,p)=1$ then $a^{p-1}\equiv 1\pmod p$. Prove that this statement is equivalent to the following: if $p$ is a prime then $(\forall a)(a^{p}\equiv a\pmod p)$.
3.8 HW: Let $p$ be a prime number and let $k,\ell \ge 1$. Prove: if $k\equiv \ell\pmod {p-1}$ then $(\forall a)(a^k \equiv a^{\ell} \pmod p)$. (5 points)
3.9 HW Compute $10^{10^{10^{10}}} \bmod {17}$. (Your answer should be an explicit integer between $0$ and $16$.) Show all your work. Do not use calculators; this problem requires virtually no calculation. (4 points)
3.10 HW (Euler-Fermat congruence) Let $m\ge 1$. Prove: if $\gcd(a,m)=1$ then $a^{\varphi(m)}\equiv 1 \pmod m$. Hint. Adapt the proof of Fermat's little theorem given in class. (4 points)
3.11 DO (composite modulus) Assume $\gcd(m,n)=1$. Prove: $(\forall a,b)\left((a\equiv b \pmod{mn}) \Leftrightarrow (a\equiv b \pmod{m}\quad\text{ AND}\quad a\equiv b \pmod{n})\right).$
3.12 HW. Prove: $(\forall a)(a^{13}\equiv a\pmod{65})$. Use Problem 3.11 without proof. (7 points)
3.13 DO (stated in class; added here on 10-14, 1:30 am): (a) Prove: the congurence $ax\equiv b \pmod m$ is solvable if and only if $\gcd(a,m) \mid b$. (b) If a solution exists, it is unique modulo what modulus?
3.14 CHALLENGE PROBLEM. Prove: if $p$ is a prime number and $p^t \mid \binom{n}{k}$ then $p^t \le n$.
3.15 CHALLENGE PROBLEM. An integer $n$ is called a Carmichael number if $(\forall a)($ if $\gcd(a,n)=1$ then $a^{n-1}\equiv 1 \pmod n)$. (a) Find a Carmichael number of the form $3pq$ where $3 < p < q$ are primes. (b) Prove: no number of the form $pq$ is a Carmichael number (where $p$ and $q$ are primes).
3.16 CHALLENGE PROBLEM (Erdös). Let $A\subseteq \{1,2,\dots,2n\}$. Assume $|A|=n+1$. Prove: $A$ includes two numbers that are relatively prime. (Paul Erdös (1913-1986), the most prolific mathematician of all time, used to challenge the "epsilons" -- mathematically inclined youngsters -- with this problem.)
2.1 DO: In class we used "Euclid's lemma" to give a second proof of the existence of a greatest common divisor. Use Euclid's lemma to also prove that $\gcd(a,b)$ is a linear combination of $a$ and $b$.
2.2 DO: (a) Let $S\subseteq \zzz$. Define what is a greatest common divisor of $S$. (b) What is the gcd of the empty set? (c) Prove: if $S, T\subseteq \zzz$ then $\gcd(S\cup T) = \gcd(\gcd(S), \gcd(T))$.
2.3 DO: Let $a\ge b\ge 1$. Suppose $a$ has $n$ binary digits. (a) If we compute $\gcd(a,b)$ using Euclid's algorithm, prove that the algorithm terminates in at most $2n$ rounds. (One round is one execution of the division algorithm.) (b) Modify the division algorithm so that Euclid's algorithm becomes even faster, terminates on $\le n$ rounds.
2.4 CHALLENGE. (a) Prove: $\sum 1/p = \infty$ (the summation is over all primes). (b) Prove:$\sum_{p\le x} 1/p \sim \ln\ln x$.
2.5 DO: Let $|A|=n \ge 1$. Prove: the number of odd subsets of $A$ is equal to the number of even subsets of $A$. Give a simple bijective proof.
2.6 HW (due Tuesday, Oct 15). Let $B(n)$ denote the number of partitions of a set of $n$ elements ("Bell numbers"). Prove: (a) $B(n) \le n^n$. (b) $(\forall k)($ if $1\le k\le n$ then $k^{n-k} \le B(n))$. (c) Use these two inequalities to prove that $\ln B(n) \sim n \ln n$. (5+8+8 points)
2.7 HW (due Tuesday, Oct 15). Let $|A|=n$. In class we observed that the number of relations on $A$ is $2^{n^2}$. Count the symmetric relations on $A$. (Your answer should be a very simple formula. Prove your answer.) (8 points)
2.8 DO (Partitions vs. equivalence relations) In class we observed that every partition $\Pi$ of the set $A$ defines an equivalence relation $R_{\Pi}$ on $A$. Prove that every equivalence relation arises this way, i.e., $(\forall$ equivalence relations $R)(\exists$ partition $\Pi) (R=R_{\Pi})$. (The blocks of $\Pi$ are called the equivalence classes for $R$.) (Hint. Notation: for $a\in A$, let $[a]=\{b\in A \mid aRb \}$. Prove the following lemma: $(\forall a,b)($either $[a]=[b]$ or $[a]$ and $[b]$ are disjoint$)$. The sets $[a]$ will be the equivalence classes of $R$.)
2.9 HW. Recall that we say that
"$a$ and $b$ are congruent modulo $m$" if $m\mid a-b$.
In notation: $a\equiv b \pmod m$. For instance,
$5\equiv 33 \pmod 7$ and $-2 \equiv 28 \pmod {-10}$.
Let us fix an integer $m$. (a) Prove that
congruence modulo $m$ is an equivalence relation on $\zzz$.
Specify for each property of the equivalence relation, what
property of divisibility you are using.
(b) Count the equivalence classes.
(6+2 points)
2.10 DO: Assume $a\equiv b\pmod m$ and $x\equiv y \pmod m$. Prove: (a) $a+x \equiv b+y \pmod m$ (b) $a-x \equiv b-y \pmod m$ (c) $ax \equiv by \pmod m$.
2.11 DO: Let $1\le x\le y\le 31$. Observe: Day $x$ and day $y$ of January falls on the same day of the week if and only if $x\equiv y$ modulo what number? (This is why, when doing arithmetic modulo $m$ with 7-th-graders, we refer to the operations as "calendar arithmetic." For grownups, the term is "modular arithmetic.")
2.12 HW. Prove: if $a\equiv b \pmod m$ then $\gcd(a,m) = \gcd(b,m)$. (6 points)
2.13 HW. (a) Find $x,y\in\zzz$ such that $5x+8y=1$. (Just give a solution, you do not need to describe how you found it.) (b) Find $z\in \zzz$ such that $5z\equiv 1 \pmod 8$. Such a $z$ is called a multiplicative inverse of 5 modulo 8. How is this problem related to part (a)? (2+3 points)
1.0 DO (prime property): Recall: an integer $n$ has the prime property if $n\neq \pm 1$ and $(\forall a,b)($ if $n\mid ab$ then $n\mid a$ or $n\mid b)$. Prove: if $n$ has the prime property then either $n=0$ or $|n|$ is a prime number.
1.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)
1.2 HW ($p^2-1$ numbers) (due Thu, Oct 10): Determine the gcd of all numbers of the form $p^2-1$ where $p\ge 11$ is prime. Prove your statement. (10 points)
1.3 DO (Fundamental Theorem of Arithmetic): 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.)
1.4 DO (sum and intersection of modules): (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$.
1.5 HW (due Thu, Oct 10): 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)
1.6. HW (due Thu, Oct 10): 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)
1.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)
1.8 HW: Let $d(n)$ denote the number of positive divisors of the positive integer $n$. Prove: $d(n) < 2\sqrt{n}$. (10 points)
1.9 DO: Prove the Division Theorem. (Induction.)
1.10 DO: LN 1.2.5 (d)(f)(h) (logic and numbers)
1.11 DO: LN 4.1.27 (logic and gcd)
1.12 DO: (a) Define least common multiples in analogy with our definition of greatest common divisors.
(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|$.
1.13 HW ("Euclid's lemma"): Prove: $\gcd(a,b)=\gcd(a-b,b)$. (Hint: prove: $\Div(a,b)=\Div(a-b,b)$.) (6 points)
1.14 HW: Prove that consecutive Fibonacci number are relatively prime, i.e., $\gcd(F_n,F_{n+1})=1.$ (5 points) (Hint: use "Euclid's lemma" (preceding exercise))
1.15 HW (due Thu, Oct 10): Let $k,\ell \ge 1$ and let $d=\gcd(k,\ell)$. Prove: $\gcd(2^k-1,2^{\ell}-1)=2^d-1$. (8 points) (Hint: use "Euclid's lemma.")
1.16 CHALLENGE PROBLEM. Prove: $\gcd(F_k, F_{\ell})= F_d$ where $d=\gcd(k,\ell)$ and $F_n$ denotes the $n$-th Fibonacci number.
1.17 DO (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.)
1.18 DO (which primes are a sum of two squares?): (a) EXPERIMENT: decide, for each prime $p < 100$, whether or not it can be written as $p=a^2+b^2$. (b) Discover very simple pattern, make a conjecture: a prime $p$ is a sum of two squares if and only if (something very simple about $p$). (c) CHALLENGE PROBLEM: prove your conjecture in either direction. (Fermat) The proof in one direction is not difficult based on Fermat's Little Theorem (which we shall learn soon).
1.19 DO: Find a sequence of real numbers which is bounded but has no limit.
1.20 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}$.
1.21 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}$;
1.22 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$.
1.23 DO (due Thu, Oct 10): 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$.)
1.24 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}$.
1.25 HW (Due Thu, Oct 10): 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."
1.26 CHALLENGE PROBLEM: LN 4.3.4. (Determinant of gcd-s.)
1.27 CHALLENGE PROBLEM: LN 4.2.13 (Integer-preserving polynomials)
1.28 CHALLENGE PROBLEM: LN 4.2.2, part 2. (Divisor game)
1.29 CHALLENGE PUZZLE: PZ 14 (unique sums)
1.30 CHALLENGE PUZZLE: PZ 3 (infection)