Prove that $$\lim_{n\to \infty} \dfrac{\sqrt[n]{n!}}{n}=e^{-1}.$$
I: Taking logarithm
Since $\ln \dfrac{\sqrt[n]{n!}}{n}=\ln \sqrt[n]{\dfrac{n!}{n^n}}=\dfrac{1}{n}\bigg(\ln \dfrac{1}{n}+\ln \dfrac{2}{n}+\cdots+\ln \dfrac{n}{n}\bigg)$, we have $$\begin{align}\lim_{n\to \infty} \dfrac{\sqrt[n]{n!}}{n} &=\exp\bigg(\lim\limits_{n\to \infty}(\dfrac{1}{n}\sum\limits_{k=1}^n\ln \dfrac{k}{n})\bigg)\\ &=\exp\bigg(\int_0^1 \ln x\;dx\bigg)\\ &=e^{-1}\;\Box\end{align}$$
II: Sandwich theorem
For any sequence $(a_n)$ of positive real numbers, we have $$\liminf_n \dfrac{a_{n+1}}{a_n}\leq \liminf_n a_n^{1/n}\leq \limsup_n a_n^{1/n}\leq \limsup_n \dfrac{a_{n+1}}{a_n}$$ Pick $a_n=\dfrac{n!}{n^n}$. Then $\dfrac{a_{n+1}}{a_n}=(1+\dfrac{1}{n})^{-n}$ and $a_n^{1/n}=\dfrac{\sqrt[n]{n!}}{n}$. It follows that $$\liminf_n (1+\dfrac{1}{n})^{-n}\leq \liminf_n \dfrac{\sqrt[n]{n!}}{n}\leq \limsup_n \dfrac{\sqrt[n]{n!}}{n}\leq \limsup_n (1+\dfrac{1}{n})^{-n}.$$ We know $$\liminf_n (1+\dfrac{1}{n})^{-n}=\limsup_n (1+\dfrac{1}{n})^{-n}=e^{-1}.$$ By sandwich theorem, we have $$\liminf_n \dfrac{\sqrt[n]{n!}}{n}=\limsup_n \dfrac{\sqrt[n]{n!}}{n}=\lim_n \dfrac{\sqrt[n]{n!}}{n}=e^{-1}\;\Box$$
III: Stirling approximation $$n!\sim \sqrt{2\pi n}(\dfrac{n}{e})^n\\ \dfrac{\sqrt[n]{n!}}{n}\sim \dfrac{\sqrt[2n]{2\pi}e^{-1}n^{1+1/(2n)}}{n}\to e^{-1}\;\Box$$
IV: Lemma: If $\lim_{n\to\infty}a_n=a$ and $a_n>0$ for all $n$, then we have $$ \lim_{n\to\infty}\sqrt[n]{a_1a_2\cdots a_n}=a.$$ Pick $a_n=\bigg(1+\dfrac{1}{n}\bigg)^n$. Since $a_n>0$ for all $n$ and $\lim_{n\to \infty}a_n=e$, we can apply the lemma: $$\begin{align} e&=\lim_{n\to\infty}\sqrt[n]{a_1a_2\cdots a_n}\\ &=\lim_{n\to\infty}\sqrt[n]{\left(\frac{2}{1}\right)^1\left(\frac{3}{2}\right)^2\cdots\left(\frac{n+1}{n}\right)^n}\\ &=\lim_{n\to\infty}\sqrt[n]{\frac{(n+1)^n}{n!}}\\&= \lim_{n\to\infty}\frac{n+1}{\sqrt[n]{n!}}\\&=\lim_{n\to\infty}\frac{n}{\sqrt[n]{n!}}+\lim_{n\to\infty}\frac{1}{\sqrt[n]{n!}} \tag{*}\\&=\lim_{n\to\infty}\frac{n}{\sqrt[n]{n!}},\end{align}$$ where in $(*)$ we have also used the lemma for $a_n=\dfrac{1}{n}\to 0$. It follows that $$\lim_{n\to \infty} \dfrac{\sqrt[n]{n!}}{n}=e^{-1}\;\Box$$
Reference
mse
Tuesday, 19 April 2016
Saturday, 2 April 2016
Primitive Roots, Discrete Logarithms
(a) Show that for each element $x\in \Bbb Z_{19}^\times$ there is a number $n\in \Bbb N$ s.t. $x=[2]^n.$
(b) Show that the function $$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [2]^n&\mapsto n\end{align}$$ is well-defined and has the property that $\log(xy)=\log x+\log y,\log(x/y)=\log x-\log y$ and $\log x^r=r\log x$ for all $x,y\in \Bbb Z_{19}^\times$ and all $r\in \Bbb Z$.
(c) List the values of this function and use them to determine $30^{14}\;\text{mod}\;19$ and $25^{11}\;\text{mod}\;19$.
Food for thought:
Intuition for (a)? Is it related to period?
Why choose $2$ in particular? Will other numbers work? [Yes! Read till the end.]
Any applications in modular exponentiation? [Yes, discrete logarithms are used in cryptography!]
I only worked on (a) and (c).
(a) My failed attempts: I expressed $x$ as $x=2^n+19y\;\exists\; y\in \Bbb Z$ and tried to use the fact that $(2,19)=1$, which didn't work. The next day I thought of proving $$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [2]^n&\mapsto n\end{align}$$ is surjective, but I can't find $n$ in terms of $x$ explicitly. A simple proof is to prove that $\Bbb Z_{19}$ is a cyclic group with generator $2$, which follows from the results in (c).
This problem is actually related to primitive roots. If $a$ is a primitive root modulo $n$, then every element of $\Bbb Z_n$ is a power of $a$. Or in the language of group theory: $a$ is a primitive root modulo $n$ if $a$ is a generator of the multiplicative group on non-zero objects modulo $n$. Here we state without proof a handy result for proving (a): $a$ is a primitive root modulo $p$ if it has order $p-1$. [To be proved later]
Recall Fermat's little theorem: if $p$ is a prime, $x\in \Bbb Z$ and $p\not\mid a$, then $a^{p-1}\equiv_p 1$. Recall also the definition of order of $a$ modulo $n$, $\text{ord}_n a$, for positive integer $n>1$ and integer $x$, if there exists a least positive integer $k$ s.t. $a^k\equiv_n 1$, then $\text{ord}_n a=k$ is the order. When we have $\text{ord}_p a=p-1$, $a$ is a primitive root modulo $p$.
Therefore, to prove (a), we need to prove that $2$ is a primitive root modulo $19$, which is true because $2^{18}\equiv_{19}1$.
(c) I used matlab to generate powers of two modulo 19.
'Logarithm table' form:
n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
log(2^n): 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10
We now find $30^{14}\;\text{mod}\;19$ and $25^{11}\;\text{mod}\;19$: $$\begin{align}30^{14}&\equiv_{19}2^{14}\;15^{14}\\
&\equiv_{19}2^{14}\;34^{14}\\
&\equiv_{19}2^{14}\;2^{14}\;17^{14}\\
&\equiv_{19}2^{14}\;2^{14}\;(-2)^{14}\\
&\equiv_{19}2^{6}\quad \qquad [2^{18}=1]\\
&\equiv_{19}7\;\;\Box
\end{align}$$
$$\begin{align}25^{11}&\equiv_{19}6^{11}\\
&\equiv_{19}2^{11}\;3^{11}\\
&\equiv_{19}2^{11}\;22^{11}\\
&\equiv_{19}2^{11}\;2^{11}\;(-8)^{11}\\
&\equiv_{19}2^4\;(-2^{33})\\
&\equiv_{19}-2\\
&\equiv_{19}17\;\;\Box
\end{align}$$
Lessons learnt:
At first I thought $[2]^n\mapsto n$ means $n$ is one value, namely, $[2]^1\mapsto 1$, but later I realised it doesn't make sense! The values of the range are just the values of $2^n\;\text{mod}\;19$, which are $1,2,3,\cdots,18$. This makes sense because there are $\phi(19)=19-1=18$ elements in $\Bbb Z_{19}^\times$, which explains why the range is $\Bbb Z_{18}$.
Also, I should rely on my brain rather than matlab: $\text{mod}(30^{14},19)$ in matlab gives $0$ but the answer is really $7$. ($\text{mod}(11^{14},19)$ in matlab gives $7$ though...)
Extensions:
Replacing $2$ by $3$ works.
$$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [3]^n&\mapsto n\end{align}\\ 30^{14}\equiv_{19}3^{14}\;(-3)^{28}\equiv_{19}3^6\equiv_{19}7\\ 25^{11}\equiv_{19}6^{11}\equiv_{19}2^{11}3^{11}\equiv_{19}15\cdot 10\equiv_{19}17$$ In fact, $10,13,14,15$ also work because they are also primitive roots. (Question: How to find all primitive roots modulo a number?)
More to learn:
cryptography
an advanced proof that $\Bbb Z_p^\times \cong \Bbb Z_{p-1}$
cyclicity of $\Bbb Z_p^\times$
using primitive roots to solve problems
(b) Show that the function $$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [2]^n&\mapsto n\end{align}$$ is well-defined and has the property that $\log(xy)=\log x+\log y,\log(x/y)=\log x-\log y$ and $\log x^r=r\log x$ for all $x,y\in \Bbb Z_{19}^\times$ and all $r\in \Bbb Z$.
(c) List the values of this function and use them to determine $30^{14}\;\text{mod}\;19$ and $25^{11}\;\text{mod}\;19$.
Food for thought:
Intuition for (a)? Is it related to period?
Why choose $2$ in particular? Will other numbers work? [Yes! Read till the end.]
Any applications in modular exponentiation? [Yes, discrete logarithms are used in cryptography!]
I only worked on (a) and (c).
(a) My failed attempts: I expressed $x$ as $x=2^n+19y\;\exists\; y\in \Bbb Z$ and tried to use the fact that $(2,19)=1$, which didn't work. The next day I thought of proving $$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [2]^n&\mapsto n\end{align}$$ is surjective, but I can't find $n$ in terms of $x$ explicitly. A simple proof is to prove that $\Bbb Z_{19}$ is a cyclic group with generator $2$, which follows from the results in (c).
This problem is actually related to primitive roots. If $a$ is a primitive root modulo $n$, then every element of $\Bbb Z_n$ is a power of $a$. Or in the language of group theory: $a$ is a primitive root modulo $n$ if $a$ is a generator of the multiplicative group on non-zero objects modulo $n$. Here we state without proof a handy result for proving (a): $a$ is a primitive root modulo $p$ if it has order $p-1$. [To be proved later]
Recall Fermat's little theorem: if $p$ is a prime, $x\in \Bbb Z$ and $p\not\mid a$, then $a^{p-1}\equiv_p 1$. Recall also the definition of order of $a$ modulo $n$, $\text{ord}_n a$, for positive integer $n>1$ and integer $x$, if there exists a least positive integer $k$ s.t. $a^k\equiv_n 1$, then $\text{ord}_n a=k$ is the order. When we have $\text{ord}_p a=p-1$, $a$ is a primitive root modulo $p$.
Therefore, to prove (a), we need to prove that $2$ is a primitive root modulo $19$, which is true because $2^{18}\equiv_{19}1$.
| 2^0 = 1 (mod 19) 2^1 = 2 (mod 19) 2^2 = 4 (mod 19) 2^3 = 8 (mod 19) 2^4 = 16 (mod 19) 2^5 = 13 (mod 19) 2^6 = 7 (mod 19) | 2^7 = 14 (mod 19) 2^8 = 9 (mod 19) 2^9 = 18 (mod 19) 2^10 = 17 (mod 19) 2^11 = 15 (mod 19) 2^12 = 11 (mod 19) 2^13 = 3 (mod 19) | 2^14 = 6 (mod 19) 2^15 = 12 (mod 19) 2^16 = 5 (mod 19) 2^17 = 10 (mod 19) 2^18 = 1 (mod 19) 2^19 = 2 (mod 19) 2^20 = 4 (mod 19) |
'Logarithm table' form:
n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
log(2^n): 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10
We now find $30^{14}\;\text{mod}\;19$ and $25^{11}\;\text{mod}\;19$: $$\begin{align}30^{14}&\equiv_{19}2^{14}\;15^{14}\\
&\equiv_{19}2^{14}\;34^{14}\\
&\equiv_{19}2^{14}\;2^{14}\;17^{14}\\
&\equiv_{19}2^{14}\;2^{14}\;(-2)^{14}\\
&\equiv_{19}2^{6}\quad \qquad [2^{18}=1]\\
&\equiv_{19}7\;\;\Box
\end{align}$$
$$\begin{align}25^{11}&\equiv_{19}6^{11}\\
&\equiv_{19}2^{11}\;3^{11}\\
&\equiv_{19}2^{11}\;22^{11}\\
&\equiv_{19}2^{11}\;2^{11}\;(-8)^{11}\\
&\equiv_{19}2^4\;(-2^{33})\\
&\equiv_{19}-2\\
&\equiv_{19}17\;\;\Box
\end{align}$$
Lessons learnt:
At first I thought $[2]^n\mapsto n$ means $n$ is one value, namely, $[2]^1\mapsto 1$, but later I realised it doesn't make sense! The values of the range are just the values of $2^n\;\text{mod}\;19$, which are $1,2,3,\cdots,18$. This makes sense because there are $\phi(19)=19-1=18$ elements in $\Bbb Z_{19}^\times$, which explains why the range is $\Bbb Z_{18}$.
Also, I should rely on my brain rather than matlab: $\text{mod}(30^{14},19)$ in matlab gives $0$ but the answer is really $7$. ($\text{mod}(11^{14},19)$ in matlab gives $7$ though...)
Extensions:
| 3^0 = 1 (mod 19) 3^1 = 3 (mod 19) 3^2 = 9 (mod 19) 3^3 = 8 (mod 19) 3^4 = 5 (mod 19) 3^5 = 15 (mod 19) 3^6 = 7 (mod 19) | 3^7 = 2 (mod 19) 3^8 = 6 (mod 19) 3^9 = 18 (mod 19) 3^10 = 16 (mod 19) 3^11 = 10 (mod 19) 3^12 = 11 (mod 19) 3^13 = 14 (mod 19) | 3^14 = 4 (mod 19) 3^15 = 12 (mod 19) 3^16 = 17 (mod 19) 3^17 = 13 (mod 19) 3^18 = 1 (mod 19) 3^19 = 3 (mod 19) 3^20 = 9 (mod 19) |
Replacing $2$ by $3$ works.
$$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [3]^n&\mapsto n\end{align}\\ 30^{14}\equiv_{19}3^{14}\;(-3)^{28}\equiv_{19}3^6\equiv_{19}7\\ 25^{11}\equiv_{19}6^{11}\equiv_{19}2^{11}3^{11}\equiv_{19}15\cdot 10\equiv_{19}17$$ In fact, $10,13,14,15$ also work because they are also primitive roots. (Question: How to find all primitive roots modulo a number?)
More to learn:
cryptography
an advanced proof that $\Bbb Z_p^\times \cong \Bbb Z_{p-1}$
cyclicity of $\Bbb Z_p^\times$
using primitive roots to solve problems
Monday, 21 March 2016
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$$
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$$
Tuesday, 8 March 2016
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
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'.
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)$.
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
 |
| 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
Subscribe to:
Posts (Atom)