Probability that two randomly selected integers are relatively prime

We make use of this result: $$\bigg(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots \bigg)\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=1.$$ Why is this true? Note that $$\bigg(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots \bigg)\bigg(1-\dfrac{1}{2^2}\bigg)=1+\dfrac{1}{3^2}+\dfrac{1}{5^2}+\cdots$$ In the equation, all the multiples of $\dfrac{1}{2^2}$ in the first factor have been knocked out by $\bigg(1-\dfrac{1}{2^2}\bigg)$. Similarly, multiplying by $\bigg(1-\dfrac{1}{3^2}\bigg)$ cancels multiples of $\dfrac{1}{3^2}$. Recall that $$1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots=\dfrac{\pi^2}{6}.$$ We thus have $$\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=\dfrac{1}{\dfrac{\pi^2}{6}}=\dfrac{6}{\pi^2}.$$We are now ready to proceed with the solution of the original problem. Let $m, n$ be the given random numbers. Let $a$ be any prime. Since $a$ divides $1$ only, $1/a $ of all the integers are divisible by $a$. The probability of $a$ dividing $m$ is thus $1/a $. Similarly, that of $a$ dividing $n$ is $1/a $. We have the followings: $$P(a|m \wedge a|n) = 1/a \cdot 1/a=1/a^2\\ P(a\not\mid m \wedge a\not\mid n)=1-1/a^2\\ P((m,n)=1)=\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=\dfrac{6}{\pi^2}$$ [...]

Divisibility Criteria

You may already have been told how to tell when a number is divisible by $3$ or $9$: you add up the digits of the number and ask whether the sum of the digits is divisible by $3$ or $9$. For example, $$3\mid 1+1+3+1 \Rightarrow 3\mid 1131.$$ We actually have a theorem: let $n\in \Bbb N$, where $n$ can be expressed in base $10$ as $n=a_k a_{k-1} \cdots a_1 a_0$. (Here $a_0,a_1,\cdots,a_{k-1},a_k$ represent different digits, and they are not being multiplied together.) Then $$m=a_0+a_1+\cdots+a_{k-1}+a_k \Rightarrow n \equiv_3 m.$$
My approach to proving this theorem is first to express $n$ as $a_0+10a_1+\cdots+10^{k-1}a_{k-1}+10^ka_k$. We now look at some specific cases of this theorem: consider $n$ as a two-digit number. Then $n=a_0+10a_1$ and $m=a_0+a_1$. Observe that $n-m=9a_1$. Since $9a_1\equiv_9 0$, we have $n\equiv_9 m$. Now, consider $n$ as a three-digit number: $$\begin{align}n&=a_0+10a_1+10^2a_2\\ m&=a_0+a_1+a_2\\ n-m&=9a_1+99a_2\\ n&\equiv_9 m.\end{align}$$ Do you see a pattern? Is it clear to you now why the sum of digits works? This works because $10^k-1$ is a multiple of $9$: $$\begin{align}\vdash 10^k-1&\equiv_9 0\\ 10&\equiv_9 1\\ 10^k&\equiv_9 1^k\\ 10^k-1&\equiv_9 0\qquad\Box \end{align}$$ But then the question requires us to prove $n \equiv_3 m$. We actually have something stronger! Let us go ahead and prove that $\equiv_9\; \Rightarrow \; \equiv_3$. $$\begin{align}\vdash a\equiv_9 b &\Rightarrow a\equiv_3 b\\ a\equiv_9 b &\Rightarrow 9\mid (a-b)\\ &\Rightarrow 3\cdot 3\mid (a-b)\\ &\Rightarrow a-b=3\cdot 3k \quad \exists k\in \Bbb Z\\ &\Rightarrow a-b=3\cdot p \quad \exists p\in \Bbb Z\\ &\Rightarrow 3\mid (a-b) \\ &\Rightarrow a\equiv_3 b\qquad\Box \end{align}$$ We also have $\equiv_8\; \Rightarrow\; \equiv_4 \wedge \equiv_2$. We can generalise these results as $\equiv_n\; \Rightarrow\; \equiv_{\;\text{factors of n except 1}}$. It is still not the time to put this problem away. We can ask ourselves: are there extensions of this result? Are there related theorems provable using the same technique? Up to this point, we know when a number is divisible by $2,3,5,9$. What about the cases for $4,6,7,8$? Since we are still dealing with numbers in base $10$, we can modify our $10^k-1$ argument to $10^k-c^k$ for $c=4,6,7,8$. Observe that $$10^k\equiv_4 6^k\\ 10^k\equiv_6 4^k\\ 10^k\equiv_7 3^k\\ 10^k\equiv_8 2^k.$$ The key idea is to change the coefficients of the digits into powers of $c$. We state without proofs the followings: $$m=a_0+6a_1+\cdots+6^{k-1}a_{k-1}+6^ka_k \Rightarrow n \equiv_4 m\\
m=a_0+\color{blue}{2}a_1+\cdots+\color{blue}{2}^{k-1}a_{k-1}+\color{blue}{2}^ka_k \Rightarrow n \equiv_4 m\\
m=a_0+4a_1+\cdots+4^{k-1}a_{k-1}+4^ka_k \Rightarrow n \equiv_6 m\\ m=a_0+3a_1+\cdots+3^{k-1}a_{k-1}+3^ka_k \Rightarrow n \equiv_7 m\\ m=a_0+2a_1+\cdots+2^{k-1}a_{k-1}+2^ka_k \Rightarrow n \equiv_8 m.$$ You may then ask: when can we use these results? Here is an example. Say we want to divide $110$ by $7$. Using the above result and without resorting to division algorithm, we know that the remainder is $5$ because $110 \equiv_7 12 \equiv_7 5$. Here $12=3+3^2$ is our $m$. The 'beauty' of this result is that we are reducing a division problem into an addition problem! (Alternatively, we can argue that $110 \equiv_7 11\cdot 10 \equiv_7 4\cdot 3 \equiv_7 12 \equiv_7 5$ to have the same result.) There may still be something interesting about this theorem. Are there any applications if we switch to other number systems like hexadecimal or binary (by changing $n$)? Is there a relationship between modular arithmetic and change of base? Further extensions of the theorem: divisibility by $11,12,\cdots,n$?

More to read:
Fun With Modular Arithmetic

Reference:
Number Theory Through Inquiry by David C. Marshall, Edward Odell, and Michael Starbird

Reflecting on my math journey

Some days ago, a math professor asked us how we should define a differential operator -- are closed under addition and scalar multiplication together with product rule enough? To be honest, I still don't know the answer to this question. It dawned on me that 'How do we define integration? How do we define differentiation? What are the tools? What are the motivations for this?' are questions that I seldom ask. I realised I was not studying properly all these years. I was just being spoonfed everything. I accepted everything without a moment of thought. I memorised the definitions without thinking about why they are defined that way. I'm literally 'learning' everything but not studying any. On a positive note, it is not too late now for me to realise this! From now on, I will re-learn every single concept and really try to THINK! I hope I can develop more intuition about math.

Integrate using matrix representations

Has it ever occurred to you that we can integrate using matrix representations? If not, prepare to have your mind blown.

It works as follows: invert the matrix representation of the differentiation operator with respect to a clever choice of a basis and then apply the inverse of the operator to the function we wish to integrate.

Here's an example. Say we want to evaluate $$\int e^{ax}\cos bx\;dx.$$ Consider the basis $B=\{e^{ax}\cos bx,e^{ax}\sin bx\}.$ Now differentiate each basis element with respect to $x$: $$\dfrac{d}{dx}e^{ax}\cos bx=ae^{ax}\cos bx-be^{ax}\sin{bx}\\ \dfrac{d}{dx}e^{ax}\sin bx=ae^{ax}\sin bx+be^{ax}\cos{bx}.$$ The matrix representation of the differential operator is thus $$T=\begin{pmatrix}a & b\\ -b & a\end{pmatrix}.$$ To evaluate the given integral, we can calculate $$T^{-1}\begin{pmatrix}1\\0\end{pmatrix}=\dfrac{1}{a^2+b^2}\begin{pmatrix}a\\b \end{pmatrix}_B$$ As a result, $$\int e^{ax}\cos bx\;dx=\dfrac{a}{a^2+b^2}e^{ax}\cos bx+\dfrac{b}{a^2+b^2}e^{ax}\sin bx.$$ Note that there are elementary ways of evaluating this integral, but isn't this method amazing?

An integral with $\cos x$

Evaluate $$\int_{-\pi}^\pi \frac{3\; dx}{5-4\cos x}.$$

---

Method I: Real analysis
We use the half angle substitution $u=\tan \dfrac{x}{2}$. Then $du=\dfrac{1}{2}\sec^2 \dfrac{x}{2}\;dx\Rightarrow du=\dfrac{1}{2}(1+u^2)\;dx$. We evaluate the indefinite integral for illustration: $$\begin{align}\int \dfrac{3 \dfrac{2}{1+u^2}}{5-4\dfrac{1-u^2}{1+u^2}}\;du&=\int \dfrac{6\; du}{5(1+u^2)-4(1-u^2)}\\&=6\int \dfrac{du}{1+9u^2}\\&=2\int \;dt\\&=2\tan^{-1}(3u)+C\\&=2\tan^{-1}(3\tan \dfrac{x}{2})+C\end{align}$$

Let $F(x)=2\tan^{-1}(3\tan \dfrac{x}{2})$. This function is undefined for all real $x=(2k+1)\pi, k\in \Bbb Z$ because $\tan \dfrac{x}{2}$ is undefined at those points. We know the graph of $F(x)$ looks like that of a tangent function except that $F(x)$ is bounded. Since the range of $\tan^{-1} x$ is $(\dfrac{-\pi}{2},\dfrac{\pi}{2})$, that of $F(x)$ is $(-\pi,\pi)$. One cycle of $F(x)$ occurs between $(-\pi,\pi)$ just like the case in $\tan \dfrac{x}{2}$. Note also that

$$\lim_{x\to (2k+1)\pi^-} F(x)=2\cdot \dfrac{\pi}{2}=\pi\\ \lim_{x\to (2k+1)\pi^+} F(x)=2\cdot \dfrac{-\pi}{2}=-\pi.$$ Finally, to evaluate the given definite integral, we can use the continuous antiderivative $$\begin{align}\bar{F}(x)=\begin{cases}-\pi,&\quad x=-\pi^+\\2\tan^{-1}(3\tan \dfrac{x}{2}),&\quad -\pi<x<\pi\\ \pi,&\quad x=\pi^-\end{cases}\end{align}.$$ As a result, $$\int_{-\pi}^\pi \frac{3\; dx}{5-4\cos x}=\bar{F}(\pi^-)-\bar{F}(-\pi^+)=\pi-(-\pi)=2\pi.$$
Method II: Residue Theorem
Since the integrand is symmetric in $[0,2\pi]$ about $\theta=\pi$, the integral is the same as $$\int_0^{2\pi} \frac{3\; dx}{5-4\cos x}.$$Transforming this integral into a contour integral, we have $$\int_C \frac{3}{5-4\frac{1}{2}(z+z^{-1})}\dfrac{dz}{iz},$$ where $C$ is the unit circle. After some simplifications, we have $$\dfrac{-3}{i}\int_C \dfrac{dz}{(2z-1)(z-2)}=\dfrac{-3}{i} 2\pi i\bigg(\dfrac{1}{4z-5}\bigg|_{z=\frac{1}{2}}\bigg)=2\pi.$$ The singularity at $z=2$ is ignored because it is outside the unit circle.

Reference:
Improper Riemann Integrals Book by Ioannis Markos Roussos