Notes

# References

### Math

##### Lecture notes

Online books by Prof Ash.

Milne's course notes.

Blatter's books (German).

##### General math

Mathematical symbols on Wiki.

Prof Ash on expository writing.

Notes (Ellenberg, Kedlaya) for perspective math grads. “... it is necessary to work through a piece of maths before one is familiar with its logical prerequisites. It is a difficult transition.”

• First two chapters of Neukirch, Algebraic Number Theory
• First four chapters of Hartshorne, Algebraic Geometry, including all exercises
• Silverman, Arithmetic of Elliptic Curves
• Serre, Galois Cohomology and Milne notes, Étale Cohomology

International Math Olympiad on Art of Problem Solving.

Putnam Math Competition Archive (1985 - present) on Kedlaya's website.

##### Algebra

Math 417 Intro Abstract Algebra I, Tramel (Fall 2016), Loja (Spring 2017).

Math 427 Honor Intro Abstract Algebra, Lerman (Fall 2016).

Math 418 Intro Abstract Algebra II, Tramel (Spring 2016), Dunfield (Spring 2015).

[More ...]

##### Analysis

Math 448 Complex Analysis, Fall 2017.

• Derive the equation of the straight line passing two different given points $z_1, z_2$. Given $z_1$ and $z_2$, the points on the straight line passing $z_1, z_2$ is given by $z = s z_1 + (1 - s) z_2$, where $s \in \mathbb{R}$. (This is can be seen from a geometric point of view.) Solve for $s$ in terms of $z, z_1, z_2$ we have $s = \frac{1}{z_1 - z_2} (z - z_2)$. (This is possible since we assume $z_1 \neq z_2$ in the first place.) Note $s$ is real so we have $\Im (s) = 0$, i.e., $\Im \left( \frac{\overline{z_1 - z_2}}{\left\vert z_1 - z_2 \right\vert^2} (z - z_2) \right) = 0$. Further use the fact that $\left\vert z_1 - z_2 \right\vert^2$ and $z_2 \bar{z}_2 = | z_2 |^2$ are real, we can simplify this to $\Im ( (\bar{z}_1 - \bar{z}_2)z - \bar{z}_1 z_2 ) = 0$. This is the line equation.
• An open connected set is called a domain. But here, a connected set is referred to a polygonally connected set. In Math 447, a connected set is defined by negation of the definition of a disconnected set, i.e., there is not a union of two disjoint sets that separate the set of interest. For comparison, there are connected sets that are not polygonally connected, e.g., consider the graph of a circle, or consider the graph of function $f(x) = \sin (\frac{1}x)$.
• It is known that $\{ e^{2k \pi i} \in \mathbb{C} : k \in \mathbb{Z} \}$ is a closed set. So is the set $\{ e^{t i} \in \mathbb{C} : t \in \mathbb{R} \}$. But the set $\mathcal{S} = \{ e^{2 \sqrt{2} k \pi i} \in \mathbb{C} : k \in \mathbb{Z} \}$ is not a closed set since $e^0$ is a limit point but not in $\mathcal{S}$. As for $e^0$ being a limit point, it boils down to denseness of $\mathbb{Z} [\sqrt 2] = \{ \sqrt 2 a + b : a, b \in \mathbb{Z} \}$ in $\mathbb{R}$, which is indeed the case.
• Let $f(z) = u(x, y) + i v(x, y)$ be a complex valued function of $z$, where $z = x + i y$, $x, y \in \mathbb{R}$. Then the derivative of $f(z)$ in terms of $x, y$ can be written as $f'(z) = u_x + i v_x$. By the same similarity between Cauchy-Riemann equations in terms of $x, y$ and $r, \theta$, we have derivative at point $z = z_0$ in polar form, $f'(z_0) = - \frac{i}{z_0} (u_\theta + i v_\theta)$.
• Let $\gamma$ be a piecewise smooth positively oriented simple closed curve. Then we have $$\frac{1}{2 \pi i} \int_{\gamma} \frac{1}{z - z_0} dz = \left\{ \begin{array}{ll} 1 & \text{if z_0 is inside \gamma,} \\ 0 & \text{if z_0 is outside \gamma.} \end{array} \right.$$
• Green's Theorem. Consider a domain $\Omega$ whose boundary $\Gamma$ consists of a finite number of disjoint, piecewise smooth simple closed curves $\gamma_1$, $\gamma_2$, $\ldots$, $\gamma_n$ and $\Gamma$ is positively oriented. If a function $f$ is continuous (in order to make sense of integral of $f$) on $\Gamma$, we have $$\int_\Gamma f(z) dz = \sum_{j=1}^n \int_{\gamma_j} f(z) dz.$$ Further assume there is a domain $D$ ($\Gamma \subset \Omega \subset D$) on which $f$ has continuous partial derivatives with respect to $x$ and $y$, then $$\tag{*} \label{eqn:green} \int_\Gamma f(z) dz = i \iint_\Omega \left( \frac{\pdv f}{\pdv x} + i \frac{\pdv f}{\pdv y} \right) dx dy,$$ or in the more familiar form $$\int_\Gamma u dx + v dy = \iint_\Omega \left( \frac{\pdv v}{\pdv x} - \frac{\pdv u}{\pdv y} \right) dx dy.$$
• Cauchy's Theorem. If $f$ is analytic on a domain $D$. Let $\gamma$ be a piecewise smooth simple closed curve in $D$ whose interior $\Gamma$ also lies in $D$. Then, $$\int_\gamma f(z) dz = 0.$$ Green's Theorem is used to prove Cauchy's Theorem for analytic functions. Note if $f = u + iv$ is analytic, it satisfies Cauchy-Riemann equations $$\frac{\pdv u}{\pdv x} = \frac{\pdv v}{\pdv y}, \frac{\pdv u}{\pdv y} = - \frac{\pdv v}{\pdv x}.$$ Spell out the right hand side of $\eqref{eqn:green}$ then it follows the contour integral of $f$ along closed curve $\gamma$ is $0$. Cauchy-Goursat drops the requirement that $\gamma$ is piecewise smooth instead Goursat replaced it with any simple closed curve $\gamma$ composed of line segments.
• Cauchy's formula. Let $f$ be an analytic function on a domain $D$, $\gamma$ be a piecewise smooth positively oriented simple closed curve in $D$ whose interior $\Omega \subset D$. Then $$f(z) = \frac{1}{2 \pi i} \int_\gamma \frac{f(\zeta)}{\zeta - z} d\zeta$$ for all $z \in \Omega$. It says function value at each point can be related to an integral over a simple closed contour surrounding $z$. As a result of Cauchy's formula, a function being analytic is the same as having power series expansion, i.e., holomorphic: Suppose that $f$ is analytic in a domain $D$ and $z_0$ is a point in $D$. If the disc $\{z: |z - z_0| < R\}$ lies in $D$, then $f$ could be written as $$f(z) = \sum_{n = 0}^\infty a_n (z - z_0)^n$$ for $\forall~ z \in D$. $a_n = \frac{1}{2 \pi i} \int_\gamma \frac{f(\zeta)}{(\zeta - z_0)^{n+1}} d\zeta$, where $\gamma$ is the positively oriented circle $\{\zeta: |\zeta - z_0| = r\}$, $0 < r < R$. It follows further that if $f$ is analytic on a domain $D$, then $f'$ is also analytic on the same domain. Hence, $f$ has derivatives of all orders, each of which is analytic on $D$. That is why when a smooth curve is defined in the complex sense, only the first derivative of $\gamma(t)$ is continuous is required.
• Recall from calculus that Abel's test: Suppose $\sum a_n$ is a convergent series and $(b_n)$ is a bounded, monotone sequence. Then $\sum a_n b_n$ is also convergent. The related complex version is used to determine the convergence of a power series on the boundary of its circle of convergence: Suppose $(a_n)$ is a monotonically decreasing sequence in $\RR^+$ with $\lim_{n \to \infty} a_n = 0$. Then $f(z) = \sum_{n = 0}^\infty a_n z^n$ converges on $\{ z \in \CC \setminus \{1\} : |z| = 1\}$.

Math 447 Real Variables, Lerman (Fall 2016), Ruan (Spring 2017).

• Bolzano-Weierstrass: Every bounded sequence of reals has a convergent subsequence.
• Stone-Weierstrass: Weierstrass states every continuous function on a closed interval $[a, b]$ can be uniformly approximated by a polynomial function which is arbitrarily close to the continuous function in question. (Compare with the fact that a continuous function on a closed interval is uniformly continuous.) Stone generalizes Weierstrass by replacing real closed interval $[a, b]$ by compact Hausdorff space $X$ and algebra (vector space equipped with bilinear product) of polynomial functions with general subalgebras of $\text{C}(X)$. ($\text{C}(X)$ is the set of continuous functions on $X$.)
• If function $f$ is continuous on a closed interval $[a,b]$ then its image $f([a,b])$ is also an interval; also $f$ achieves maximum and minimum on $[a,b]$.
• The above claim has a partial converse if we restrict $f$ to strictly increasing or decreasing functions. If $f: I \rightarrow f(I)$, $f(I)$ is an interval and $f$ is strictly increasing or decreasing, then $f$ is continuous on $I$. $I$ can be open, closed, or half-open intervals.
• Every sequence has a monotone subsequence and also every sequence $(a_n)$ has a subsequence $(a_{n_k})$ such that $\lim_{k \to \infty} \frac{a_{n_{k+1}}}{a_{n_k}} \in \{0, 1, \infty \}$.
• A real valued function $f(x)$ is uniformly continuous if $\forall~ \varepsilon > 0$, $\exists~ \delta >0$ such that $\forall~ x, y \in \text{dom}(f)$ when $|x - y| < \delta$ we have $|f(x) - f(y)| < \varepsilon$. The negation of this statement is used for proving a function is not uniformly continuous, i.e., $\exists~ \varepsilon > 0$, $\forall~ \delta > 0$, $\exists~ x, y \in \text{dom}(f)$ such that $|x - y| < \delta \implies |f(x) - f(y)| \geqslant \varepsilon$. An equivalent negation uses “for each sequence $(\delta_n)$ with $\delta_n \to 0$” instead of “$\forall~ \delta >0$” in the previous statement. In practice, one can use one particular sequence $(\delta_n)$ with $\delta_n \to 0$, e.g., $\delta_n = \frac{1}n$. It is equivalent to “for each sequence $(\delta_n)$”. ($\Rightarrow$ direction is obvious; $\Leftarrow$ direction uses the fact that $\forall~ \delta > 0$, we can find $N > 0$ such that when $n>N$ we have $|\delta_n - 0| < \delta$ by $\delta_n \to 0$. So $\exists~ x, y \in \text{dom}(f)$ s.t. $|x - y| < \delta_n < \delta \implies |f(x) - f(y)| \geqslant \varepsilon$.)
• $f(x) = x$ is both continuous and uniformly continuous on $\mathbb{R}$ but $f(x) = x^2$ is continuous but not uniformly continuous. For the latter, consider a sequence with $x_n = \frac{1}{2n} + n$ and a sequence with $y_n = n$. When $x_n$ and $y_n$ are getting arbitrarily close, it is not guaranteed that ${x_n}^2 - {y_n}^2 \to 0$. Indeed, ${x_n}^2 - {y_n}^2 \to 2 \cdot \frac{1}{2n} \cdot n = 1$.
• Heine-Borel: In Euclidean space $\mathbb{R}^n$, a subset $S$ is closed and bounded iff $S$ is compact. Therefore, the consequences of Heine-Borel,
• If a set is compact, then it must be closed. A limit point of $S$ is in $S$.
• If a set is compact, then it must be bounded.
• A closed subset of a compact set is again compact.
• If a set is closed and bounded, then it is compact.
However in more general metric spaces, a subset of a metric space is compact iff it is complete (every Cauchy sequence converges to a point in the subset) and totally bounded (for any $\varepsilon > 0$, there exists a finite cover whose element is with radius at most $\varepsilon$). We do not use closedness + boundedness to define compactness in general metric space. A (general) metric space is said to have Heine-Borel property if every of its open cover has a finite subcover.
Analogies between intervals in $\mathbb{R}$ and subsets in a metric space:
$(\mathbb{R}, |\cdot|)$ $(S, d)$
intervals connected sets
closed intervals compact and connected
bounded closed sets compact sets
• The Mean Value Theorem states that for a function continuous on closed interval $[a, b]$, differentiable on open interval $(a, b)$, there is a point $c \in (a, b)$ s.t. $f'(c) = \frac{f(b) - f(a)}{b - a}$. An immediate implication of this is that the derivative of function $f$ on $(a, b)$ is bounded.
• Why $\mathbb{Q} \cap [0, 1] \subset \mathbb{R}$ is not compact? Consider a sequence $(x_n)$ in $\mathbb{Q} \cap [0, 1]$, where $x_n = \lfloor \frac{\sqrt{2} n}{2n} \rfloor$. It is easy to see that $x_n \to \frac{1}{\sqrt{2}} \notin \mathbb{Q} \cap [0, 1]$ as $n \to \infty$. So it is not closed, hence it is not compact.
• The Dirichlet function is defined as $$f(x) = \left\{ \begin{array}{rl} 1 & \mbox{if $x$ is rational, } \\ 0 & \mbox{if $x$ is irrational. } \end{array} \right.$$ The Dirichlet function is not continuous everywhere. The idea of the proof, is to look at point $x_0 \in \mathbb{R}$, If $x_0$ is rational, then find an irrational sequence $(x_n) = x_0 + \frac{1}{\sqrt{2}n}$, such that $f(x_n) \to 0$ as $x \to x_0$ but $f(x_0) = 1$ by the construction of Dirichlet function. Similar argument can be said about the case when $x_0$ is irrational. Therefore Dirichlet function is nowhere continuous.
The Riemann function on the other hand is defined as $$f(x) = \left\{ \begin{array}{rl} 1 & \mbox{if $x = 0$, } \\ \frac{1}q & \mbox{if $x$ is rational, $x = \frac{p}q$ in lowest terms and $q > 0$, } \\ 0 & \mbox{if $x$ is irrational. } \end{array} \right.$$ Thomae's function or a Riemann function, which is a modified version of Dirichlet function, has a complicated set of discontinuities; it is continuous at all irrational numbers and discontinuous at rational numbers.
• Fundamental Theorem of Calculus (FTC) has two parts; FTC (I) says that for a nice function $g(x)$, we have $$\int_a^b g'(t) \, dt = g(b) - g(a).$$ In particular, replacing $b$ with $x$, we have $$g(x) = \int_a^x g'(t) \, dt + g(a).$$ FTC (II) says for a nice function $g(x)$, we have $$\frac{d}{dx} \left( \int_a^x g(t) \, dt \right) = g(x).$$ Therefore if we denote differentiation of a function $g(x)$ as operation $D(g(x))$ and integration as operation $I(g(x))$, the composite operation of differentiation and integration with different order will be an identity operation up to a constant, i.e., $g(x) = D \circ I(g(x)) = I \circ D(g(x)) + \mbox{Constant}$.
• While Darboux integral associated with a function $f$ and partition $P$ is defined using upper sum and lower sum $$\mathcal{U}(f, P) = \sum_{k = 1}^n \sup_{t_{k-1} \leq x \leq t_k} f(x) (t_k - t_{k-1})$$ and $$\mathcal{L}(f, P) = \sum_{k = 1}^n \inf_{t_{k-1} \leq x \leq t_k} f(x) (t_k - t_{k-1})$$ respectively, Riemann integral is defined using Riemann sum $$\mathcal{S}(f, P) = \sum_{k = 1}^n f(x) (t_k - t_{k-1})$$ , where $x$ is arbitrarily chosen in the interval $[t_{k-1}, t_k]$. That means there are infinitely many Riemann sums associated with a partition $P$.

Math 540 Real Analysis, Tyson & Laugesen (Fall 2016).

• $\sigma$-algebra on a set $X$ is a collections $\Sigma$ of subsets of $X$ that is closed under countable union, intersection and complement. Borel $\sigma$-algebra on a topological space is a collections of all Borel sets (open sets that are formed by countable union, intersection and complement) in the topological space.
• Carathéodory Extension Theorem states that a measure defined on a ring $R$ of subsets of the set $\Omega$ can be extended to the $\sigma$-algebra generated by ring $R$; the extension is unique if the defined measure is $\sigma$-finite. It paves the way for existence of Lebesgue measure.
• Determine if $I=\iint_{\mathbb{R}^2} \frac{x^2}{(1+x^2)(x^2 + y^2)^{3/2}}\,dxdy$ converges.
Solution. The integral is on the entire $\RR^2$ plane. By symmetry, $I = 4I_{\substack{x>0 \\ y>0}}$, where $I_{\substack{x>0 \\ y>0}}$ is the integral of the same integrand but over the first quadrant. By change of variable $(x, y) \mapsto (u, uv)$, we have $dx dy = udu dv$. Therefore, \begin{align*} I & = \iint_{\substack{u>0 \\ v>0}} \frac{u^2}{(1+u^2)u^3(1+v^2)^{3/2}}\,udu dv \\ & = \int_0^\infty\frac{du}{1+u^2} \int_0^\infty\frac{dv}{(1+v^2)^{3/2}}. \end{align*} The second equality is due to Tonelli's theorem for non-negative functions.

[More ...]

##### Number Theory

Math 453 Elementary Number Theory, Allen (Spring 2017).

New! Elementary Number Theory in 40 Days with Prof. Allen on github.

• Open problems:
• Lehmer's totient problem. Does there exist a composite number $n$ such that $\varphi(n) \mid n-1$? A remark on Giuga Conjecture and this problem. See also Sierpiński and Carmichael numbers.
• Prime number race and Chebyshev bias. Tao's blog article Biases between consecutive primes. Rubinstein (1994). A survey by Granville (2006).
• Artin's conjecture on primitive roots. An integer $a$ which is not a perfect square or $-1$ is a primitive root modulo infinitely many primes $p$. A conditional proof assuming generalized Riemann Hypothesis by Hooley. See also a note on generalizing Artin's conjecture to composite moduli.
• Chinese Remainder Theorem: the proof given by Prof Allen is different from the one in Strayer (2001).
• Reciprocity Law: the proof given by Prof Allen is from Rousseau (1989). A note on the group notations used in the proof. $\mathbb{Z}/n\mathbb{Z}$ is a group of integers modulo $n$. Actually it is a quotient ring. It also has multiplication structure. $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ is used to denote the group of units of the aforementioned quotient ring, $$\left(\mathbb{Z}/n\mathbb{Z}\right)^\times = \left\{ r \in \mathbb{Z}/n\mathbb{Z} : \exists \, s \in \mathbb{Z}/n\mathbb{Z} \text{ such that } rs \equiv 1 \bmod{n} \right\}.$$ In the case of a prime modulus $p$, the reduced residue system differs from the complete residue system by $\{0\}$, $$\mathbb{Z}/p\mathbb{Z} = \left\{0, 1, 2, 3, \ldots, p-1 \right\}.$$ So we have $$\left(\mathbb{Z}/p\mathbb{Z}\right)^\times = \left\{ 1, 2, 3, \ldots, p-1 \right\},$$ because $1, 2, \ldots, p-1$ are all relative prime with $p$, i.e., the inverse of each element in $\mathbb{Z}/p\mathbb{Z}$ exists except for $0$. The direct product of $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times \times \left(\mathbb{Z}/q\mathbb{Z}\right)^\times$ will give ordered pairs $(i,j)$ for $i \in \left(\mathbb{Z}/p\mathbb{Z}\right)^\times$ and $j \in \left(\mathbb{Z}/q\mathbb{Z}\right)^\times$. The quotient group $G = \left(\mathbb{Z}/p\mathbb{Z}\right)^\times \times \left(\mathbb{Z}/q\mathbb{Z}\right)^\times / U$ was considered in the proof, where $U = \{(1,1), (-1,-1)\}$, a normal subgroup that specifies the rule (equivalence relation) by which we regroup the elements in $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times \times \left(\mathbb{Z}/q\mathbb{Z}\right)^\times$. The equivalence relation on $G$ defined by subgroup $U$ satisfies, $$x \sim y \in G \iff xy^{-1} \in U.$$ Coordinate-wise, e.g., if $ac^{-1} = 1$ with some $a, c \in \left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, we have $a = c$, meaning $c$ belongs to the same congruent class modulo $p$ as $a$; similarly we have $a = -c$ if $ac^{-1} = 1$, meaning $c$ belongs to the same congruent class modulo $p$ as $-a$, i.e. $a$ and $p - a$ are the same elements in $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times / \{ -1,1 \}$. ($ac^{-1} = 1$ in the sense of modular arithmetic, i.e., $ac^{-1} \equiv 1 \bmod p$.) So in the case of group $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times \times \left(\mathbb{Z}/q\mathbb{Z}\right)^\times$ with normal subgroup $U$ $$x = (a,b) \sim y = (c,d) \iff (a = c \text{ and } b = d) \text{ or } (a = -c \text{ and } b = -d).$$
• Solve for $\varphi(n) = 42$. First off, note that $42 = 2 \cdot 3 \cdot 7$. Start with the largest divisor $7$. Since $7$ is a prime divisor of $\varphi(n)$, consider the prime factorization of $n$, $n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}$, $p_i$'s are distinct primes, and $e_i \geqslant 1$ for $1 \leqslant i \leqslant k$, by the formula of $\varphi(n)$, $$\varphi(n) = \prod_i (p_i - 1) p_i^{e_i -1},$$ we have either $7 \mid p_i -1$ or $7 \mid p_i^{e_i -1}$.
Case 1. If $7 \mid p_i -1$, note that $p_i - 1$ is bounded by $42$ so write down all primes that are smaller than $43$ and are multiples of $7$ plus $1$. There are only two possible primes, namely $29, 43$. If $p_i = 29$, now write $n = 29 m$ with $\text{gcd}(29,m) = 1$. Rewrite $\varphi(n) = (29 - 1) \varphi(m)$ by Euler-$\varphi$ being multiplicative. It is easy to see that $28 \varphi(m) = 42$ has no solution. If $p_i = 43$, again by $\varphi(n) = \varphi(43) \varphi(m)$ we have $\varphi(m) = 1$. It has two solutions $m = 1, 2$. So $n = 43$ or $86$.
Case 2. If $7 \mid p_i^{e_i -1}$, note that $7^{e_i -1 }$ is also bounded by $42$, so $e_i \leqslant 2$. At the same time $e_i \geqslant 2$ (since the power of $7$ survived in the formula of $\varphi(n)$), by a similar argument $\varphi(m) = 1$. $m = 1, 2$. The possible $n$ in this case is $49$ or $98$. In conclusion, $\varphi(n) = 42 \iff n = 43, 86, 49 \text{ or } 98$.
• Let $m, n$ be odd integers. If $m^2 - n^2 + 1 \mid n^2 - 1$, show that $m^2 - n^2 + 1$ is a perfect square. (From Irish Maths Olympiad (2005), Day 2)
Proof. First, consider $n^2 - 1 = (d^2 - 1)(m^2 - n^2 + 1)$, where $d \mid m$, $d$ is a positive divisor of $m$. It is easy to see that in this case $m^2 - n^2 + 1 = \left( \frac{m}d \right)^2$. Then it suffices to show that these are the only possibilities of writing $$n^2 - 1 = k(m^2 - n^2 + 1), \tag{*} \label{453eq1}$$ where $k$ must be of the form $d^2 - 1$. Note by $\eqref{453eq1}$ we have that $k$ is bounded by $m^2 - 1$. (Since $k \leqslant n^2 -1 \leqslant m^2 - 1$.) Also by (*) we notice that $k m^2 = (k+1)(n^2 - 1)$. $k$ must be even otherwise $m$ cannot be odd. But $k+1 \nmid k$, it implies we must have $k + 1 \mid m^2$, i.e., (gap needs to be fixed) $k$ must be of the form $d^2 - 1$. Q.E.D.
• Let $a, b \in \mathbb{Z}$, $a, b >0$ such that $ab+1 \mid a^2 + b^2$. Show $\frac{a^2 + b^2}{ab+1}$ is a perfect square.
Proof. Since $ab+1$ divides $a^2+b^2$, denote $k = \frac{a^2 + b^2}{ab+1}$, for some $k \in \mathbb{Z}, k > 0$. For $k$ not a square and if such $k$ exists, out of all pairs $a, b$, there must be a pair $a_0, b_0$ with $a_0 + b_0 \leqslant a + b$ for all $a, b$ satisfying $k = \frac{a^2 + b^2}{ab+1}$. Without loss of generality, assume $a_0 \geqslant b_0$. Further notice that $$k = \frac{a^2 + b^2}{ab+1} \iff a^2 - (kb)a +(b^2 - k) = 0, \mbox{ for a, b > 0}.$$ $a_0$ is one of the two solutions to the quadratic equation $x^2 - (kb_0)x + ({b_0}^2 - k) = 0$. We want to derive a contradiction by claiming that the second solution to the aforementioned quadratic equation, say $c$, satisfies $c + b_0 < a_0 + b_0$, hence it breaks the minimality of $a_0 + b_0$ for such a $k$.
Indeed, by Vieta's formulas, $$c + a_0 = kb_0, c a_0 = {b_0}^2 - k.$$ So $c = kb_0 - a_0 = \frac{{b_0}^2 - k}{a_0}$. By our assumption, $k$ is not a square, therefore $c \neq 0$. The pair $c, b_0$ satisfies $k = \frac{c^2 + {b_0}^2}{cb_0 + 1} > 0$. It implies $c > 0$. (Otherwise $cb_0 + 1 < 0$ then $k < 0$.) But at the same time, $c = \frac{{b_0}^2 - k}{a_0} < a_0$ since ${b_0}^2 - {a_0}^2 \leqslant 0 < k$. Hence the contradiction. Such nonsquare $k$ does not exist. Q.E.D.
• Let $p$ be a prime, $a$ a primitive root modulo $p$. Then the order of $a$ modulo $p$ is by definition, $\text{ord}_p (a) = \varphi(p) = p - 1$. Since $a$ is a primitive root, the set of powers of $a$ $$A := \{ a, a^2, \ldots, a^{\varphi(p)} \},$$ defines a reduced system of residues modulo $p$. ($0$ has been left out.) Note that for a prime $p$, there are $p - 1$ nonzero incongruent residue classes and there are $p - 1$ incongruent powers of $a$ in the set of powers of $a$ above. If we want to check if another integer $b$ within the range $1 \leqslant b \leqslant p - 1$ is a primitive root, first off, $b$ must be congruent to one of the powers of $a$ in the set ; then the order of $b$ can be computed by computing the order of the congruent power of $a$, i.e., $$\text{ord}_p (b) = \text{ord}_p (a^k) = \frac{ \text{ord}_p (a) }{ \text{gcd}(k, \text{ord}_p (a) ) },$$ where $k$ is some integer $1 \leqslant k \leqslant \varphi(p)$. By $b$ being also a primitive root, we have $\text{ord}_p (b) = \text{ord}_p (a) = p - 1$. Therefore we have to max out the right hand side of the above equality by setting $\text{gcd} (k, p - 1) = 1$. The order of $a^k$ is sandwiched between the order of $a$ and order of $b$, so $a^k$ is also a primitive root. Then $$b \equiv a^k \bmod p \mbox{ for k coprime with p-1. }$$ Now consider the case where $\text{ord}_p (b) = d \mid p - 1$ but $d$ is a proper divisor of $p - 1$ i.e., $b$ is not a primitive root. The set of powers of $b$ $$B := \{ b, b^2, \ldots, b^d \},$$ defines $d$ incongruent classes modulo $p$. Are $A$ and $B$ disjoint? or $B \subset A$ or neither? Obviously \begin{align*} a^\varphi(p) & \equiv 1 \bmod p \\ & \equiv b^d \bmod p, \end{align*} so $A$ and $B$ are not disjoint. In fact $B \subset A$. Indeed, the set $A$ of powers of $a$ characterizes the solutions to the polynomial congruence $x^{p - 1} - 1 \equiv 0 \bmod p$. Similarly, the set $B$ of powers of $b$ characterizes the solutions to the polynomial congruence $x^d - 1 \equiv 0 \bmod p$. And by $d \mid p -1$, any solution to $x^d - 1 \equiv 0 \bmod p$ solves $x^{p - 1} - 1 \equiv 0 \bmod p$, i.e., $b \in B \implies b \in A$. Therefore $B \subset A$.
Note that this applies to composite moduli as well. In that case $A := \{a, a^2, \ldots, a^{\varphi(n)}\}$ and $B := \{ b, b^2, \dots, b^{\text{ord}_n(b)} \}$ and we have $B \subset A$.
• Assuming the knowledge that $a$ is a primitive root modulo $n$, looking for solutions to congruence $x^2 \equiv 1 \bmod n$ is equivalent to looking at the powers of $a$ such that $$(a^k)^2 \equiv 1 \bmod n$$ ranging $k$ from $1$ through $\varphi(n)$. This uses the fact that the set $\{ a, a^2, \ldots, a^{\varphi(n)} \}$ gives the reduced system of residues modulo $n$.
• Let $a,n \in \mathbb{Z}$ with $n \geqslant 1$ and $\text{gcd}(a,n)=1$. Is it true that $\text{ord}_d(a) \mid \text{ord}_n(a)$ for any positive divisor $d$ of $n$?
Proof. By division algorithm, $\text{ord}_n (a) = q \, \text{ord}_d (a) + r$ for some $q \in \mathbb{Z}$, and $0 \leqslant r < \text{ord}_d (a)$. $a^{\text{ord}_n (a)} \equiv 1 \bmod n$ implies $a^{\text{ord}_n (a)} \equiv 1 \bmod d$ since $d \mid n$. $a^{\text{ord}_n (a)} = a^{q \, \text{ord}_d (a) + r} \equiv 1 \bmod d$ further simplifies to $a^r \equiv 1 \bmod d$ by the fact that $a^{\text{ord}_d (a)} \equiv 1 \bmod d$. Therefore by both the order of $a$ modulo $d$ divides $r$ and $r$ is smaller than $\text{ord}_d (a)$, we have $r = 0$ hence the claim. Q.E.D.
• A useful trick to figure out the relationship between the digits of an integer and divisibility by another integer. See one problem. For example, say $$N = (abcd)_{10} = 1000a + 100b + 10c + d$$ is divisible by $11$, then $$11 \mid 1000a + 100b + 10c + d = (1001a - a) + (99b + b) + (11c - c) + d,$$ i.e., $(abcd)_{10} \equiv -a + b - c + d \equiv 0 \bmod 11$.
• Let $(p_n)$ be the sequence of prime numbers, $p_1 = 2, p_2 = 3, p_3 = 5, \ldots$, then $\lim_{n \to \infty} \frac{p_{n+1}}{p_n} = 1$. Use the fact that $p_n \sim n \log (n)$. For more info, see discussion.
• For solving higher order congruences such as $a x^n \equiv b \bmod m$, one can use mathematica's Reduce[]. If ones desires to do it by hand, consider a "taking logarithm" approach. Given there exists a primitive root modulo $m$, denoted $r$, the smallest positive integer such that $r^n \equiv a \bmod m$ holds for a given $a$ is called the "index" of $a$ relative to $r$ modulo $m$, denoted $\text{ind}_r a$. Then the original higher order congruence can be converted to linear congruence, i.e., $$n \, \text{ind}_r x \equiv \text{ind}_r b - \text{ind}_r a \bmod \varphi (m).$$ The solution for $x$ is independent of the choice of primitive root $r$ modulo $m$. One advantage of this approach is that it can also be used to solve exponential congruence, e.g., $a n^x \equiv b \bmod m$, which cannot be solved by Reduce[] in mathematica.
• Integer factorization of $10^{500} + 1$ in magma takes about 55 seconds however doing this in mathematica hangs. The online Wolfram Alpha however, returns the result almost instantly. See primality test and factorization for details. An odd composite which passes Miller-Rabin test will definitely be a composite, but for a single test, there is less than a quarter of chances the test is inconclusive, i.e., declaring a composite as a probable prime. However if an integer fails a series of independent Miller-Rabin tests, then chances of this integer being composite are miniscule, i.e., this integer is very likely to be a prime.
• Show that $x^3$ and $x^3 + x +1$ are coprime.
Proof. Use the fact that $\gcd (a, b) = \gcd (b, r)$ where $r = a - q b$ with $0 \leqslant r < b$ for $a, b, q, r \in \mathbb{Z}$.
$\gcd (x^3, x^3 + x + 1) = \gcd (x^3, x + 1)$ and we have $$x^3 = (x^2 - x + 1) (x + 1) - 1.$$ So we conclude that $\gcd (x^3, x^3 + x + 1) = \gcd (x^3, x + 1) = 1$.

Top

### IBM

IBM CPLEX

Use IBM CPLEX Studio to solve Linear Programming problems.

CPLEX provides interface to MATLAB. Optimization problems can be solved within MATLAB.

• Function calls
• Class APIs

IBM Data Science experience

Top

### GNU

GNU Project

AUCTeX reference card

New! Emacs + LaTeX portable set-up (for USB flash drive etc.) for Windows x86_64 on github. No installation is required, unpack and enjoy LaTeX-ing!

Top

### Debian

Debian

Nextcloud

Dropbox is replaced with self hosting Nextcloud.

• #### Nextcloud Server

Hardware: The server is a low powered PC based on Intel J3455 CPU and four spare spinning disks. Btrfs was used in RAID 10 so disks of different sizes is not an issue. It also has the advantage over hardware RAID/ZFS RAID that Btrfs RAID can grow without destroying existing RAID. It is now powering this website and my own cloud storage https://cloud.chipnotized.org.

Software prerequisite: LEMP stack

Nextcloud Server install

• On GNU/Linux Debian, Coming soon.
• On FreeBSD, see example here.

• #### Nextcloud Client

• ##### Desktop
• ###### Windows/Linux

Follow the guideline and don't mess up with anything on the repo page. For Windows, download the prebuilt binary and install. On Debian, add Nextcloud repo and package manager will take care of the install.

• ###### Mac OS

Don't follow repo guideline; use instead modern Xcode 7.3.1 and Qt 5.9.1. First, Xcode 7.3.1 supports sideload app to a personal device but Xcode 6.4 does not. Second, the reason why the official guide sticks to Qt 5.6.2 was it was a long term support release. Well, Qt 5.9.1 is the next LTS release. Build with Xcode 6.4 and Qt 5.6.2 with hack will result in a client that does not support connection to a TLS v1.2 only server. See original issue #13.

• Install VMware Workstation 12. Other VMware virtualization solutions like ESXi are also supposed to work the same way.
• Unlock Mac OS X guest using unlocker tool and create an OS X 10.11 virtual machine. The official guide stated 180GB was needed to build Qt 5.6.2 with hack but I only used a 80GB VM hard drive to custom build Qt 5.9.1 without patch. To expand the preset hard drive size,
sudo diskutil resizeVolume / R # on OS X 10.10 though, use diskutil GUI
The entire disk will be at disposal.
• Install Xcode 7.3.1. To find out the SDK path,
xcrun --show-sdk-path
• Install Homebrew.
• brew install openssl wget cmake.
• Install Sparkle framework.
# download package
# unpack, it will generate several folders and files under ./
tar -xf Sparkle-1.14.0.tar.bz2
mv Sparkle.framework ~/Library/Frameworks/ # needed to chmod 777 Sparkle.framework before mv in my case
# generate Sparkle keys, make sure the private key is kept to yourself
./bin/generate_keys

• Install Packages.
• Build Qt 5.9.1 against homebrew openssl. Host machine was an HP Z600 with dual Xeon X5675 and 48GB ECC 1333MHz RAM. VM was given 16 CPU cores and 32 GB RAM. It took about 2 hr and 40 min given only a single 7200 rpm spinning disk was used.
• # go to /tmp directory, remember /tmp will be flushed after reboot
cd /tmp
# unpack source code of Qt
tar -xjf /path/to/qt-everywhere-opensource-src-5.9.1.tar.xz
# build against openssl, need to specify -I and -L arguments as 'brew info openssl' suggests
./configure -sdk macosx10.11 -confirm-license -opensource -nomake examples -openssl -openssl-linked -I /usr/local/opt/openssl/include/ -L /usr/local/opt/openssl/lib/


Python

[More ...]

Top