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
Ko Chao with Paul Erdős at Manchester Maths around 1938. Photo from AMS Notices.
Ko Chao with Paul Erdős, Harold Davenport and Ko's adviser Louis Mordell at Manchester Maths.
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).
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$.
\( \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.
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.
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 \).
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.
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
# download package
wget https://github.com/sparkle-project/Sparkle/releases/download/1.14.0/Sparkle-1.14.0.tar.bz2
# 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
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/
/usr/local/opt/openssl/ can be replaced with
$(brew --prefix openssl).
make -j17 # num of jobs = num of cpu cores + 1
sudo make -j1 install # avoid competing install jobs, use '-j1'
Finally build the Nextcloud client itself.
# build happens in ~/client_theming
cd ~/
# check out theming code
git clone https://github.com/nextcloud/client_theming.git
cd client_theming
# pull client code from ownCloud repo
git submodule update --init --recursive
# copy Sparkle keys to both ./osx and ~/
cp -rv /path/to/Sparkle/keys/dsa_*.pem ./osx
cp -rv /path/to/Sparkle/keys/dsa_*.pem ~/ # ./osx/build.sh pulls keys in ~/ during final stage
Modify ./osx/build.sh if necessary. For example, user name of my OSX
machine is osxbuilder not builder as in the script. I
also changed Qt version, OSX SDK version and deploy platform. As of now, I
don't know
how to codesign the package so I expect signing error.
Client package is in ~/install. Install the package and the about page of
the client is similar to this, note the openssl is not the version shipped with Mac OS X.
Nextcloud client 2.4.1 package can be downloaded
here. It was compiled against
Qt version 5.11.0 beta 2, OpenSSL 1.1.0h for deployment on Mac OS X 10.10 or above, so older platforms
may not work.
To verify the package, use my signature (sha256)
$0.99 (Why? Update: Free now as of Aug 25, 2017) on App Store but open sourced on
github. Xcode is supposed to be able to sideload
the app for personal use.
Key differences between Python 2.x and Python 3.x.
Note: the comment on next method is not correct. Generator has method __next__() in Python 3.5.3.
as in Debian Stretch.
Generated by Python + Pandas with data compiled from
nobelprize.org. I was curious about the claim that babies born in winters are smarter
or more successful. In the case of Nobel laureates, it seems to be false.
