Several inequalities

Let $m,n\in \Bbb N, x\in \Bbb R, x\geq 0, x\neq 1$. Prove the followings: if $m>n$, then $\dfrac{x^m-1}{m}>\dfrac{x^n-1}{n}$; if $m<n$, then $\dfrac{x^m-1}{m}<\dfrac{x^n-1}{n}$.

Proof:
Consider the case when $m>n$. The other case is similar. It suffices to show that $n(x^m-1)-m(x^n-1)> 0$ for $x>1$. $$\begin{align}n(x^m-1)-m(x^n-1)&=n(x-1)(x^{m-1}+x^{m-2}+\cdots+1)-m(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&=n(x-1)(x^{m-1}+x^{m-2}+\cdots+x^n)+n(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&\quad-m(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&=n(x-1)(x^{m-1}+x^{m-2}+\cdots+x^n)\\&\quad-(m-n)(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&> (x-1)[n\underbrace{(x^n+\cdots+x^n)}_{m-n\; terms}-(m-n)\underbrace{(x^n+\cdots+x^n)}_{n\; terms}]\qquad(*)\\&=(x-1)x^n[n(m-n)-(m-n)n]\\&=0\qquad \Box\end{align}$$ In $(*)$, we have used the facts that $x^{m-i}\geq x^n$ when $i=1,\cdots,m-n$ and $-x^{n-j}\geq -x^n$ where $j=1,\cdots,n$. The case for $0\leq x<1$ also holds because we have $-x^{m-i}\geq -x^n$ when $i=1,\cdots,m-n$ and $-x^{n-j}\leq -x^n$ where $j=1,\cdots,n$.

Remark: This result implies that the sequence of functions $f_n(x)=\dfrac{x^n-1}{n}$ is increasing when $x$ is fixed and $x>1$. The term $-1$ there is crucial. Recall the taylor series of $e^x$ and exponential functions: $$e^x=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots\\ 2^x=e^{(\ln 2)x}=1+(\ln 2)x+\dfrac{((\ln 2)x)^2}{2!}+\cdots.$$ Then $\dfrac{e^x-1}{x}=1+\dfrac{x}{2}+\dfrac{x^2}{6}+\dfrac{x^3}{24}+\cdots$, whereas $\dfrac{e^x}{x}$ or $\dfrac{e^x+5}{x}$ contains the expression $\dfrac{1}{x}$, which means there will be asymptotes.

We can use the proved inequalities to prove some other inequalities.

Let $a,b\in \Bbb R, a>0, b>0, a\neq b, r\in \Bbb Q$ Then $$rb^{r-1}(a-b)<a^r-b^r<ra^{r-1}(a-b)\quad r>1\\ ra^{r-1}(a-b)<a^r-b^r<rb^{r-1}(a-b)\quad 0<r<1.$$ Proof:
When we divide the inequalities by $b^r$, we will see that they resemble the inequalities that we have proved. We just prove the case when $r>1$. Let $r=\dfrac{m}{n}$, where $m,n\in \Bbb N$. $r>1\Rightarrow m>n$. Substituting $x=(\dfrac{a}{b})^{1/n}$ gives $$\dfrac{(\dfrac{a}{b})^{m/n}-1}{m}>\dfrac{(\dfrac{a}{b})^{m/n}-1}{n}\\ \dfrac{a^r-b^r}{mb^r}>\dfrac{a-b}{bn}\\ a^r-b^r>rb^{r-1}(a-b).$$ Similarly, substituting $x=(\dfrac{b}{a})^{1/n}$ yields $$\dfrac{(\dfrac{b}{a})^{m/n}-1}{m}>\dfrac{(\dfrac{a}{b})^{n/n}-1}{n}\\ \dfrac{b^r-a^r}{ma^r}>\dfrac{b-a}{an}\\ a^r-b^r<ra^{r-1}(a-b).\qquad \Box$$

Evaluating Vandermonde Determinants

Suppose we have four points $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$. If we want to find a cubic polynomial $a+bx+cx^2+dx^3$ passing through these points, we have to solve $$\underbrace{\begin{pmatrix}1&x_1&x_1^2&x_1^3\\1&x_2&x_2^2&x_2^3\\1&x_3&x_3^2&x_3^3\\1&x_4&x_4^2&x_4^3\end{pmatrix}}_{=A}\begin{pmatrix}a\\b\\c\\d\end{pmatrix}=\begin{pmatrix}y_1\\y_2\\y_3\\y_4\end{pmatrix}.$$ There is always a unique solution when $A$ is invertible. $A$ is actually a Vandermonde matrix, which is invertible if all the $x_i$'s are distinct. How do we evaluate a Vandermonde determinant? As an example, let's consider $$A=\begin{pmatrix}1&3&9&27\\1&2&4&8\\1&4&16&64\\1&5&25&125\end{pmatrix}.$$ Replace the last row with the variable $x$. Let $$f(x)=\begin{pmatrix}1&3&9&27\\1&2&4&8\\1&4&16&64\\1&x&x^2&x^3\end{pmatrix}.$$ We see that $f(2)=f(3)=f(4)=0$ and $\det(A)=f(5)$. Since $f(x)$ is a cubic polynomial, we must have $f(x)=k(x-2)(x-3)(x-4)$, where $k$ is a constant. Now we perform cofactor expansion along the last row: $$f(x)=1\cdot c_{41}+x\cdot c_{42}+x^2\cdot c_{43}+x^3\cdot c_{44}.$$ Comparing the coefficients of $x^3$ of the two expressions, we have $$k=c_{44}=\begin{vmatrix}1&3&9\\1&2&4\\1&4&16\end{vmatrix}.$$Do you notice something? This problem is related to recursion! Using the same trick, we can argue that $c_{44}=(4-3)(4-2)(2-3)=-2$. Finally, $f(5)=-2(5-2)(5-3)(5-4)=-12$.

Reference:
vandermonde

Cosets and Decimal Expansions

Let us take a deeper look at fractions and their decimal expansions. $$\dfrac{1}{2}=0.5,\quad \dfrac{1}{3}=0.3333\cdots=0.\bar{3},\quad \dfrac{1}{4}=0.25,\quad \dfrac{1}{5}=0.2,\quad \dfrac{1}{6}=0.1666\cdots=0.1\bar{6},\\ \dfrac{1}{7}=0.142857142857\cdots=0.\overline{142857},\quad \dfrac{1}{8}=0.125,\quad \dfrac{1}{9}=0.1111\cdots=0.\bar{1},\quad \dfrac{1}{10}=0.1$$ Observe that the decimal expansions of $\dfrac{1}{3},\dfrac{1}{5},\dfrac{1}{6},\dfrac{1}{7},\dfrac{1}{9}$ are periodic. We claim that if the denominator $b$ of a fraction $a/b$ is relatively prime to $10$, then the fraction has a decimal expansion that is purely periodic. Note that the converse of this claim is not true as seen above: $(6,10)=2\neq 1$ but $1/6$ has a periodic decimal expansion. To prove this, recall a useful tool from high school: geometric series. Here's a special case for illustration: $$\dfrac{1}{7}=0.\overline{142857}=0.142857\cdot (1+10^{-6}+10^{-12}+\cdots)=\dfrac{0.142857}{1-10^{-6}}\\ 10^6-1=7(142857)\\ 10(10^5)-7(142857)=1\\ (7,10)=1$$ Let us now modify the arguments to prove our claim. We only prove the case when $a=1$. When $a$ is not $1$, $a/b$ is just $\underbrace{1/b+1/b+1/b+\cdots}_{a\; times}$ and it has a periodic decimal expansion when $1/b$ does. $$(b,10)=1 \Rightarrow \; \exists\; x,y\in \Bbb Z\; s.t.\; bx+10y=1\\ 10y-1=b(-x)\\ \dfrac{1}{b}=\dfrac{-x}{10y-1}=\dfrac{x}{1-10y}=x(1+10y+10y^2+\cdots)\; \Box$$ Consider $\dfrac{1}{7}$ and some of its multiples: $$\color{blue}{\dfrac{2}{7}=0.\overline{285714}},\quad \dfrac{3}{7}=0.\overline{428571},\quad \color{forestgreen}{\dfrac{4}{7}=0.\overline{571428}},\quad \color{red}{\dfrac{5}{7}=0.\overline{714285}},\quad \color{gray}{\dfrac{6}{7}=0.\overline{857142}}\\ \color{gray}{\dfrac{20}{7}=2.\overline{857142}},\quad \color{blue}{\dfrac{30}{7}=4.\overline{285714}},\quad \color{red}{\dfrac{40}{7}=5.\overline{714285}},\quad \dfrac{50}{7}=7.\overline{142857},\color{forestgreen}{\quad \dfrac{60}{7}=8.\overline{571428}}$$ Observe that if we cyclically shift the digits in the repeating part of the decimal expansions of a reduced fraction, we get the repeating part of the decimal expansion of another reduced fraction with the same denominator. It is by no means a coincidence. This phenomenon is actually related to cosets. We have $$\dfrac{30}{7}=\dfrac{2}{7}+4\\ \dfrac{60}{7}=\dfrac{4}{7}+8\\ \dfrac{20}{7}=\dfrac{6}{7}+2\\ \cdots$$ Rephrase these in modular arithmetic: $$30\equiv_7 2\\ 60\equiv_7 4\\ 20\equiv_7 6.$$ Recall that two integers being equal in modulo $n$ means they have the same remainder when divided by $n$. It makes sense now that $30/7$ and $2/7$ differ by an integer and have the same repeating part (remainder). Another observation is that when we shift the digits of $3/7=0.\overline{428571}$ to the left once, we get $2/7=0.\overline{285714}$. Note that $30\equiv_7 2$ is actually $3\cdot 10\equiv_7 2$. When we multiply a number by $10$, the digits are shifted to the left by a place. What if we shift two or three places to the left? Just multiply by $100$ or $1000$. In general, we have $$3\cdot 10^n \equiv_7 r,$$ where $0\leq r<7$, then $r/7$ will have a decimal expansion whose repeating part is the digits for $3/7$ shifted to the left $n$ times. We can display this cyclic behavior by placing the six digits on a 'circle diagram'.

circle digram for 1/7

From the diagram, the decimal expansion of any proper fraction with denominator $7$ can be read off by going around the wheel. As an example, to find the decimal expansion of $5/7$, start at digit $7$ and go around clockwise to obtain $0.\overline{714285}$.

Let's consider one more example: $1/13$ and its multiples. $$\dfrac{1}{13}=0.\overline{076923},\quad \dfrac{3}{13}=0.\overline{230769},\quad \dfrac{4}{13}=0.\overline{307692},\quad \dfrac{9}{13}=0.\overline{692307},\quad \dfrac{10}{13}=0.\overline{769230},\quad \dfrac{12}{13}=0.\overline{923076}\\ \dfrac{2}{13}=0.\overline{153846},\quad \dfrac{5}{13}=0.\overline{384615},\quad \dfrac{6}{13}=0.\overline{461538},\quad \dfrac{7}{13}=0.\overline{538461},\quad \dfrac{8}{13}=0.\overline{615384},\quad \dfrac{11}{13}=0.\overline{846153}$$This time there are two distinct classes of decimal digits. Six of them contain the repeating digits $076923$; the other six $153846$. Why is this? Indeed, the fractions on the first row are congruent to $10^k \;(\text{mod}\; 13)$; those on the second row are congruent to $2\cdot 10^k\;(\text{mod}\; 13)$.

circle diagrams for 1/13

We see that $$(10)=\{10^k\;(\text{mod}\; 13)\mid k\in \Bbb Z^+\}=\{1,10,9,12,3,4\}\\ 2(10)=\{2\cdot 10^k\;(\text{mod}\; 13)\mid k\in \Bbb Z^+\}=\{2,7,5,11,6,8\}$$ are two disjoint sets whose union is $Z_{13}$. $(10)$ is a cyclic subgroup $H$ generated by the congruence class of $10$ in $\Bbb Z_{13}$, whereas $2(10)$ represent the coset $2H$.

We conclude that if $a/b$ is a reduced fraction where $(10,b)=1$, then the other reduced fractions whose decimal has a repeating block that is a shift of the repeating block of the decimal for $a/b$ are precisely those fractions with denominator $b$ and numerator in the coset $a\cdot 10\;(\text{mod}\; b)$ of $\Bbb Z_b$.

Questions to be answered:
In the circle diagrams for $13$, why does any pair of opposite decimal digits adds up to $9$? Why does any pair of opposite fractions adds up to $1$? These two questions can be answered by Midy's theorem.
How do we know how many cosets there should be?

Reference:
notes by Keith Conrad
7th decimal wheel

More to know:
cyclic number
primitive root modulo n

Finding gcd by Euclidean algorithm and extended Euclidean algorithm

Task: find the greatest common divisor of two integers a and b using python

The first program relies on the fact that if $d\mid a$ and $d\mid b$, then $d|(a-b)$. In the third program, we need to ensure that b is not zero because division by zero is not defined. Line 21 follows from Euclidean algorithm. (In fact, it does not matter whether a or b is the larger number. Here is an example for illustration. When a = 210 and b = 7, 210 is assigned to 7 and 7 to 0. The program then stops and returns 7. When a = 7 and b = 210, 7 is assigned to 210 and 210 is assigned to 7 % 210. 7 % 210 is 0 with remainder 7. Now, 210 is assigned to 7 and 7 to 0. The program terminates and returns 7.)

The fourth program is known as the extended Euclidean algorithm and it takes some time to understand. Note that for integers $a,b$ where $a>b$, $a=qb+r=\lfloor a/b \rfloor b+a-\lfloor a/b \rfloor b$, or in python $a=a//b*b+a\%b$. Recall that each iteration in the Euclidean algorithm replaces $(a,b)$ by $(b,a\;\text{mod}\; b)$. We can formulate this as a matrix multiplication: $$\begin{pmatrix}b & a\;\text{mod}\;b\end{pmatrix}=\begin{pmatrix}a&b\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q\end{pmatrix},\qquad q=\lfloor a/b \rfloor.$$Suppose that the algorithm terminates after $k$ iterations, then the operations performed on $\text{gcd}(a,b)$ can be summarised in matrix notation by $$\begin{pmatrix}\text{gcd}(a,b)&0\end{pmatrix}=\begin{pmatrix}a&b\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q_1\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q_2\end{pmatrix}\cdots\begin{pmatrix}0 & 1\\ 1 & -q_k\end{pmatrix}$$ or $$\begin{pmatrix}\text{gcd}(a,b)&0\end{pmatrix}=\begin{pmatrix}a&b\end{pmatrix}\begin{pmatrix}x & u\\ y & v\end{pmatrix}.$$Since we want to find the triple $(d,x,y)$, namely, the gcd and the first column of the resulting matrix, we want to keep track of the product of matrices along with the remainder computation. Therefore, we start with the matrix $$\begin{pmatrix}x & u\\ y & v\\ a & b\end{pmatrix}=\begin{pmatrix}1 & 0\\ 0 & 1\\ a & b\end{pmatrix},$$ or set $x,y,u,v=1,0,0,1$. Note that $$\begin{pmatrix}x & u\\ y & v\\ a & b\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q\end{pmatrix}=\begin{pmatrix}u & x-uq\\ v & y-vq\\ b & a-bq\end{pmatrix}$$ It is then natural to assign $x$ to $u$, $y$ to $v$; $u$ to $x-uq$, $v$ to $y-vq$. The rest is similar to program $3$. Here's a second interpretation. The algorithm aims to compute the tuple $(d,x,y)$ such that $ax+by=d$. We know that $$a\cdot 1+b\cdot 0=a\\ a\cdot 0+b\cdot 1=b.$$ We then set $$a\cdot x+b\cdot y=a\quad(1)\\ a\cdot u+b\cdot v=b\quad(2)$$ where $x,y,u,v$ are $1,0,0,1$. Note that $\text{gcd}(a,b)=\text{gcd}(b,r=a\;\text{mod}\; b)$. We thus have a new pair of equations: $$(1)-(2)\cdot q,\quad a\cdot(x-uq)+b\cdot(y-vq)=r,\quad q=\lfloor a/b \rfloor. \\ a\cdot x+b\cdot y=b$$ Assigning $a$ to $b$, $b$ to $r$ and changing the values of $x,y,u,v$ accordingly, the program will eventually terminate when $b$ becomes $0$. It follows that $$a\cdot u+b\cdot v=0\\ a\cdot x+b\cdot y=\text{gcd}(a,b).$$Then we take the second equation and we have $(d,x,y)$.

In the sixth program, we are still relying on the fact that $\text{gcd}(a,b)=\text{gcd}(b,r=a\;\text{mod}\; b)$. We have $$ax+by=\text{gcd}(a,b)\\ bx'+ry'=\text{gcd}(a,b).$$ Put $x=y',y=x'$. Then $$\begin{align}ax+by&=ay'+bx'\\ &=(qb+r)y'+bx'\\ &=qby'+(ry'+bx')\\ ay'+bx'&=qby'+\text{gcd}(a,b)\\ \Rightarrow ay'+b(x'-qy')&=\text{gcd}(a,b).\end{align}$$ Finally, we put $x=y',y=x'-qy'$, where $x,y$ are the values we want.

Lessons learnt:

• = vs ==: The first one assigns a value to the variable on the left; the second one means that the value of the variable is that on the right.
• % // operators
• while loop
• iterative (loop) vs recursive (a function calling itself repeatedly)
• multiple assignment: In python, we don't need a swap function because a, b = b, a works sufficiently without defining a temp variable, c. This is useful when we want a to be larger than b:

if a < b:

    a, b = b, a
else:
    pass

More to know:

subtractive algorithm 1, 2, 3

binary gcd algorithm 1

extended Euclidean algorithm

Reference:
program 4 1, 2, 3
program 6 1, 2, 3

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}$$ [...]