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
Tuesday, 8 March 2016
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
Thursday, 11 February 2016
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:
More to know:
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:
binary gcd algorithm 1
Thursday, 4 February 2016
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}$$ [...]
Wednesday, 3 February 2016
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
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
Subscribe to:
Posts (Atom)