Find all $x\in \Bbb Z_{85}$ s.t. $(x+2)^{100}=0$.
I: Taking Logarithm
Solving $(x+2)^{100}=0$ for $x\in \Bbb Z_{85}$ is equivalent to finding $x\in \Bbb Z_{85}$ s.t. $(x+2)^{100}=85y$. $$\begin{align}(x+2)^{100}&=85y\\ 100\log(x+2)&=\log(85y)\\ \log(x+2)&=\dfrac{\log(85y)}{100}\\ x+2&=10^{\log(85y)/100}\end{align}$$ The only integer values of $10^{\log(85y)/100}$ are $85,85^2,\cdots,$ (powers of $85$). [For example, when $y=85^{99}$, $10^{\log(85y)/100}=10^{\log(85)}=85$. When $y=85^{199}$, $10^{\log(85y)/100}=10^{2\log(85)}=85^2$.] It follows that $x=85-2,85^2-2,\cdots,$ (powers of $85$)$-2$. But all these values are equal to $-2\equiv_{85} 83$. Therefore, the only $x\in \Bbb Z_{85}$ satisfying the equation is $83$.
II: Solving System of Congruences
Solving $(x+2)^{100}=0$ for $x\in \Bbb Z_{85}$ is equivalent to solving $(x+2)^{100}\equiv_{85} 0$. Note that $85=5\cdot 17$. We can solve the following system of congruences: $$(x+2)^{100}\equiv_5 0\\ (x+2)^{100}\equiv_{17} 0.$$ Some calculations reveal that $$x\equiv_5 3\\ x\equiv_{17} 15.$$ Therefore, there exists $y\in \Bbb Z$ s.t. $x=3+5y$ and thus $$3+5y\equiv_{17} 15\\ 5y\equiv_{17} 12\\ y\equiv_{17} 12\cdot 7\\ y\equiv_{17} 16.$$ Finally, there exists $z\in \Bbb Z$ s.t. $x=3+5(16+17y)=83+85z\equiv_{85} 83$. Alternatively, by Chinese Remainder Theorem, the system has a unique solution $x$ modulo $85$. We have $$n_1=5,n_2=17;\;\;\;\text{and}\;\;\;n_1'=17,n_2'=5\\t_1=-2,t_2=7\\x=a_1t_1n_1'+a_2t_2n_2'=3\cdot -2\cdot 17+15\cdot 7\cdot 5=423\equiv_{85} 83.$$
Saturday 30 April 2016
Friday 29 April 2016
Dimension of Vector Space
Determine whether each of the following is a vector space and find the dimension and a basis for each that is a vector space:
i) $\mathbb{C}$ over $\mathbb{C}$.
ii) $\mathbb{C}$ over $\mathbb{R}$.
iii) $\mathbb{R}$ over $\mathbb{C}$.
iv) $\mathbb{R}$ over $\mathbb{Q}$.
v) $\mathbb{Q}$ over $\mathbb{R}$.
vi) $\mathbb{Q}$ over $\mathbb{Z}$.
vii) $\mathbb{S}=\{a+b\sqrt{2}+c\sqrt{5}\:|\:a,b,c \in \mathbb{Q}\}$ over $\mathbb{Q,R,\text{or}\: C}$.
Answers:
i) Yes. $\{1\}$ is a basis. Dimension is $1$.
[Say $1+2i,1+i\in \Bbb C$. $(1+2i)\cdot (1+i)=-1+3i=1\cdot (-1+3i)$, where $1$ is the basis element and $-1+3i$ is in the field $\Bbb C$.]
ii) Yes. $\{1,i\}$ is a basis. Dimension is $2$.
[Say $1+i\in \Bbb C$ and $2\in \Bbb R$. $2\cdot (1+i)=2+2i=2\cdot 1+2\cdot i$, where $1,i$ are elements in the basis and $2$ is in the field $\Bbb R$.]
iii) No. $i\in \Bbb C$ and $1\in \Bbb R$, but $i \cdot 1=i\notin \Bbb R$.
iv) Yes. $\{1,\pi,\pi^2,\cdots\}$ are linearly independent over $\Bbb Q$. Dimension is infinite.
v) No. $\sqrt{2}\in \Bbb R$ and $1\in \Bbb Q$, but $\sqrt{2} \cdot 1=\sqrt{2}\notin \Bbb Q$.
vi) No. $\Bbb Z$ is not a field.
vii) Yes only over $\Bbb Q$. $\{1,\sqrt{2},\sqrt{5}\}$ is a basis. Dimension is $3$.
From iii and v, we know that the field is always 'smaller' than its vector space. In fact, this is related to the concept of field extension (to be discussed in our next post).
Let $V=\{(x,y)\:|\:x,y\in \Bbb C\}$. Under the standard addition and scalar multiplication for ordered pairs of complex numbers, is $V$ a vector space over $\Bbb C$? Over $\Bbb R$? Over $\Bbb Q$? If so, find the dimension of $V$.
Answers:
From the previous question, we know $\{(1,0),(0,1)\}$ form a basis for $V$ over $\Bbb C$. Dimension is $2$. $\{(1,0),(i,0),(0,1),(0,i)\}$ form a basis for $V$ over $\Bbb R$. Dimension is $4$. Lastly, the dimension of $V$ over $\Bbb Q$ is infinite.
i) $\mathbb{C}$ over $\mathbb{C}$.
ii) $\mathbb{C}$ over $\mathbb{R}$.
iii) $\mathbb{R}$ over $\mathbb{C}$.
iv) $\mathbb{R}$ over $\mathbb{Q}$.
v) $\mathbb{Q}$ over $\mathbb{R}$.
vi) $\mathbb{Q}$ over $\mathbb{Z}$.
vii) $\mathbb{S}=\{a+b\sqrt{2}+c\sqrt{5}\:|\:a,b,c \in \mathbb{Q}\}$ over $\mathbb{Q,R,\text{or}\: C}$.
Answers:
i) Yes. $\{1\}$ is a basis. Dimension is $1$.
[Say $1+2i,1+i\in \Bbb C$. $(1+2i)\cdot (1+i)=-1+3i=1\cdot (-1+3i)$, where $1$ is the basis element and $-1+3i$ is in the field $\Bbb C$.]
ii) Yes. $\{1,i\}$ is a basis. Dimension is $2$.
[Say $1+i\in \Bbb C$ and $2\in \Bbb R$. $2\cdot (1+i)=2+2i=2\cdot 1+2\cdot i$, where $1,i$ are elements in the basis and $2$ is in the field $\Bbb R$.]
iii) No. $i\in \Bbb C$ and $1\in \Bbb R$, but $i \cdot 1=i\notin \Bbb R$.
iv) Yes. $\{1,\pi,\pi^2,\cdots\}$ are linearly independent over $\Bbb Q$. Dimension is infinite.
v) No. $\sqrt{2}\in \Bbb R$ and $1\in \Bbb Q$, but $\sqrt{2} \cdot 1=\sqrt{2}\notin \Bbb Q$.
vi) No. $\Bbb Z$ is not a field.
vii) Yes only over $\Bbb Q$. $\{1,\sqrt{2},\sqrt{5}\}$ is a basis. Dimension is $3$.
From iii and v, we know that the field is always 'smaller' than its vector space. In fact, this is related to the concept of field extension (to be discussed in our next post).
Let $V=\{(x,y)\:|\:x,y\in \Bbb C\}$. Under the standard addition and scalar multiplication for ordered pairs of complex numbers, is $V$ a vector space over $\Bbb C$? Over $\Bbb R$? Over $\Bbb Q$? If so, find the dimension of $V$.
Answers:
From the previous question, we know $\{(1,0),(0,1)\}$ form a basis for $V$ over $\Bbb C$. Dimension is $2$. $\{(1,0),(i,0),(0,1),(0,i)\}$ form a basis for $V$ over $\Bbb R$. Dimension is $4$. Lastly, the dimension of $V$ over $\Bbb Q$ is infinite.
Saturday 23 April 2016
A problem on diagonalisation
Give examples of the following types of operators defined by a $2\times 2$ matrix or explain why such an operator can't exist:
i) diagonalisable, invertible,
ii) diagonalisable, not invertible,
iii) not diagonalisable, invertible,
iv) not diagonalisable, not invertible.
Let's just consider the case in $\Bbb R$.
i) $$\boxed{\begin{pmatrix}a&0\\0&b\end{pmatrix},\quad \text{a and b are not necessarily different},\quad a,b\neq 0}$$ Any diagonal matrix $D$ is diagonalisable: $$I_n DI_n=D.\\ \boxed{\begin{pmatrix}a&b\\b&a\end{pmatrix},\quad a\neq b,\quad a\neq -b,\quad\text{a can be zero.}}$$ Calculations: $(a-\lambda)^2-b^2=0\Rightarrow \lambda=a-b,a+b$. $$\ker\begin{pmatrix}a-(a+b)&b\\b&a-(a+b)\end{pmatrix}=\text{span}\bigg\{\begin{pmatrix}1\\1\end{pmatrix}\bigg\}\\ \ker\begin{pmatrix}a-(a-b)&b\\b&a-(a-b)\end{pmatrix}=\text{span}\bigg\{\begin{pmatrix}1\\-1\end{pmatrix}\bigg\}$$ The two eigenvectors form an eigenbasis. Alternatively, one can use the result: if $A\in M_{n\times n}(\Bbb F)$ has $n$ distinct eigenvalues in $\Bbb F$, then $A$ is diagonalisable over $\Bbb F$. $$\boxed{\begin{pmatrix}a&b\\b&c\end{pmatrix},\quad a\neq c,\quad b\neq 0,\quad\text{a can be zero.}}$$ The calculation is similar, but involves the use of quadratic formula. Since $a\neq c$ and $b\neq 0$, we have two distinct eigenvalues. Symmetric matrices are thus diagonalisable. $$\boxed{\begin{pmatrix}a&b\\0&c\end{pmatrix},\quad a\neq c,\quad b\neq 0}$$ Upper triangular matrices with distinct diagonal entries are diagonalisable because of the same reason: they have distinct eigenvalues. The above matrices are invertible since their determinants are non-zero.
ii) $$\boxed{\begin{pmatrix}a&0\\0&0\end{pmatrix},\quad a\neq 0}$$ Again, any diagonal matrix is diagonalisable. $$\boxed{\begin{pmatrix}a&a\\a&a\end{pmatrix},\quad a\neq 0}$$ Calculation: $(a-\lambda)^2-a^2=0\Rightarrow \lambda=0,2a$. When $a=1$, the matrix is called matrix of ones. $$\boxed{\begin{pmatrix}a&a\\b&b\end{pmatrix}, \begin{pmatrix}a&b\\a&b\end{pmatrix},\quad a+b\neq 0,\;\;\text{a,b not both zero.}}$$Calculation: $(a-\lambda)(b-\lambda)-ab=0\Rightarrow \lambda=0,a+b$.
iii) $$\boxed{\begin{pmatrix}a&b\\0&a\end{pmatrix},\begin{pmatrix}a&0\\b&a\end{pmatrix},\quad \text{a and b are not necessarily different},\quad a,b\neq 0}$$ These are known as the shear transformations, which are not diagonalisable. Proof by contradiction: Suppose $\begin{pmatrix}a&b\\0&a\end{pmatrix}$ is diagonalisable. Then there exist a diagonal matrix $D$ and an invertible matrix $V$ s.t. $$\begin{pmatrix}a&b\\0&a\end{pmatrix}=V^{-1}DV.$$ We know just by looking at the matrix that $a$ is an eigenvalue with multiplicity $2$. So $D=\begin{pmatrix}a&0\\0&a\end{pmatrix}=aI_2$. We then have $\begin{pmatrix}a&b\\0&a\end{pmatrix}=aV^{-1}I_2V=aI_2=\begin{pmatrix}a&0\\0&a\end{pmatrix}$ which is a contradiction.
iv) $$\boxed{\begin{pmatrix}0&a\\0&0\end{pmatrix},\quad a\neq 0}$$ Its only eigenvalue is $0$ of multiplicity $2$.
From this problem, we see that invertibility does not necessarily nor sufficiently imply diagonalisability! Another important fact that one can observe from (ii) and (iv) is that if a square matrix $A$ is not invertible, then $\lambda=0$ is an eigenvalue of $A$. The converse also holds: if $\lambda=0$ is an eigenvalue of $A$, then $A$ is not invertible.
Claim: $A\in M_{n\times n}(\Bbb F)$ is singular iff $\lambda=0$ is an eigenvalue of $A$.
Proof: $\lambda=0$ is a solution of the characteristic equation $\lambda^n+c_1\lambda^{n-1}+\cdots+c_n=0$ iff $c_n=0$. By definition, $\det(\lambda I-A)=\lambda^n+c_1\lambda^{n-1}+\cdots+c_n$. When $\lambda=0$, we have $\det(\lambda I-A)=\det(-A)=(-1)^n\det(A)=c_n$. We thus have $\det(A)=0$ iff $c_n=0$ iff $\lambda=0.\;\Box$
Here's a summary:
i) diagonalisable, invertible: symmetric, upper triangular, diagonal
ii) diagonalisable, not invertible: nilpotent, scalar multiples of matrix of ones
iii) not diagonalisable, invertible: shear
iv) not diagonalisable, not invertible: nilpotent.
I tried to enumerate all possibilities but failed. I can't imagine the amount of work it takes to characterise diagonalisation for $3\times 3$ matrices...
Questions:
$$\boxed{\begin{pmatrix}a&b\\c&d\end{pmatrix},\quad (a-d)^2=-4bc,\quad ad-bc\neq 0}$$ has repeated eigenvalues, so I consider it fitting (iii), but can the kernel corresponding to that one eigenvalue be spanned by two eigenvectors? Similar questions for $$\boxed{\begin{pmatrix}a&a\\a&b\end{pmatrix},\quad 5a^2+b^2=2ab,\quad a(b-a)\neq 0}\\
\boxed{\begin{pmatrix}a&a\\b&c\end{pmatrix},\quad a^2+c^2=2ac-4ab,\quad a(c-b)\neq 0}\\
\boxed{\begin{pmatrix}0&a\\b&c\end{pmatrix},\quad c^2=-4ab,\quad ab\neq 0}$$ I'm not even sure if there are other possibilities for (iii) and (iv).
i) diagonalisable, invertible,
ii) diagonalisable, not invertible,
iii) not diagonalisable, invertible,
iv) not diagonalisable, not invertible.
Let's just consider the case in $\Bbb R$.
i) $$\boxed{\begin{pmatrix}a&0\\0&b\end{pmatrix},\quad \text{a and b are not necessarily different},\quad a,b\neq 0}$$ Any diagonal matrix $D$ is diagonalisable: $$I_n DI_n=D.\\ \boxed{\begin{pmatrix}a&b\\b&a\end{pmatrix},\quad a\neq b,\quad a\neq -b,\quad\text{a can be zero.}}$$ Calculations: $(a-\lambda)^2-b^2=0\Rightarrow \lambda=a-b,a+b$. $$\ker\begin{pmatrix}a-(a+b)&b\\b&a-(a+b)\end{pmatrix}=\text{span}\bigg\{\begin{pmatrix}1\\1\end{pmatrix}\bigg\}\\ \ker\begin{pmatrix}a-(a-b)&b\\b&a-(a-b)\end{pmatrix}=\text{span}\bigg\{\begin{pmatrix}1\\-1\end{pmatrix}\bigg\}$$ The two eigenvectors form an eigenbasis. Alternatively, one can use the result: if $A\in M_{n\times n}(\Bbb F)$ has $n$ distinct eigenvalues in $\Bbb F$, then $A$ is diagonalisable over $\Bbb F$. $$\boxed{\begin{pmatrix}a&b\\b&c\end{pmatrix},\quad a\neq c,\quad b\neq 0,\quad\text{a can be zero.}}$$ The calculation is similar, but involves the use of quadratic formula. Since $a\neq c$ and $b\neq 0$, we have two distinct eigenvalues. Symmetric matrices are thus diagonalisable. $$\boxed{\begin{pmatrix}a&b\\0&c\end{pmatrix},\quad a\neq c,\quad b\neq 0}$$ Upper triangular matrices with distinct diagonal entries are diagonalisable because of the same reason: they have distinct eigenvalues. The above matrices are invertible since their determinants are non-zero.
ii) $$\boxed{\begin{pmatrix}a&0\\0&0\end{pmatrix},\quad a\neq 0}$$ Again, any diagonal matrix is diagonalisable. $$\boxed{\begin{pmatrix}a&a\\a&a\end{pmatrix},\quad a\neq 0}$$ Calculation: $(a-\lambda)^2-a^2=0\Rightarrow \lambda=0,2a$. When $a=1$, the matrix is called matrix of ones. $$\boxed{\begin{pmatrix}a&a\\b&b\end{pmatrix}, \begin{pmatrix}a&b\\a&b\end{pmatrix},\quad a+b\neq 0,\;\;\text{a,b not both zero.}}$$Calculation: $(a-\lambda)(b-\lambda)-ab=0\Rightarrow \lambda=0,a+b$.
iii) $$\boxed{\begin{pmatrix}a&b\\0&a\end{pmatrix},\begin{pmatrix}a&0\\b&a\end{pmatrix},\quad \text{a and b are not necessarily different},\quad a,b\neq 0}$$ These are known as the shear transformations, which are not diagonalisable. Proof by contradiction: Suppose $\begin{pmatrix}a&b\\0&a\end{pmatrix}$ is diagonalisable. Then there exist a diagonal matrix $D$ and an invertible matrix $V$ s.t. $$\begin{pmatrix}a&b\\0&a\end{pmatrix}=V^{-1}DV.$$ We know just by looking at the matrix that $a$ is an eigenvalue with multiplicity $2$. So $D=\begin{pmatrix}a&0\\0&a\end{pmatrix}=aI_2$. We then have $\begin{pmatrix}a&b\\0&a\end{pmatrix}=aV^{-1}I_2V=aI_2=\begin{pmatrix}a&0\\0&a\end{pmatrix}$ which is a contradiction.
iv) $$\boxed{\begin{pmatrix}0&a\\0&0\end{pmatrix},\quad a\neq 0}$$ Its only eigenvalue is $0$ of multiplicity $2$.
From this problem, we see that invertibility does not necessarily nor sufficiently imply diagonalisability! Another important fact that one can observe from (ii) and (iv) is that if a square matrix $A$ is not invertible, then $\lambda=0$ is an eigenvalue of $A$. The converse also holds: if $\lambda=0$ is an eigenvalue of $A$, then $A$ is not invertible.
Claim: $A\in M_{n\times n}(\Bbb F)$ is singular iff $\lambda=0$ is an eigenvalue of $A$.
Proof: $\lambda=0$ is a solution of the characteristic equation $\lambda^n+c_1\lambda^{n-1}+\cdots+c_n=0$ iff $c_n=0$. By definition, $\det(\lambda I-A)=\lambda^n+c_1\lambda^{n-1}+\cdots+c_n$. When $\lambda=0$, we have $\det(\lambda I-A)=\det(-A)=(-1)^n\det(A)=c_n$. We thus have $\det(A)=0$ iff $c_n=0$ iff $\lambda=0.\;\Box$
Here's a summary:
i) diagonalisable, invertible: symmetric, upper triangular, diagonal
ii) diagonalisable, not invertible: nilpotent, scalar multiples of matrix of ones
iii) not diagonalisable, invertible: shear
iv) not diagonalisable, not invertible: nilpotent.
I tried to enumerate all possibilities but failed. I can't imagine the amount of work it takes to characterise diagonalisation for $3\times 3$ matrices...
Questions:
$$\boxed{\begin{pmatrix}a&b\\c&d\end{pmatrix},\quad (a-d)^2=-4bc,\quad ad-bc\neq 0}$$ has repeated eigenvalues, so I consider it fitting (iii), but can the kernel corresponding to that one eigenvalue be spanned by two eigenvectors? Similar questions for $$\boxed{\begin{pmatrix}a&a\\a&b\end{pmatrix},\quad 5a^2+b^2=2ab,\quad a(b-a)\neq 0}\\
\boxed{\begin{pmatrix}a&a\\b&c\end{pmatrix},\quad a^2+c^2=2ac-4ab,\quad a(c-b)\neq 0}\\
\boxed{\begin{pmatrix}0&a\\b&c\end{pmatrix},\quad c^2=-4ab,\quad ab\neq 0}$$ I'm not even sure if there are other possibilities for (iii) and (iv).
Tuesday 19 April 2016
Evaluate $\lim_n \dfrac{\sqrt[n]{n!}}{n}$
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
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
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
Subscribe to:
Posts (Atom)