8.28 Modular arithmetic tutorial
-
Find \(d=\text{gcd}(234,63)\) and write it as a linear combination of 234 and 63.=9=
Extended Euclidean Algorithm: Start with the last non-zero remainder.
\[ \begin{aligned} &234=63\times3+45 \\ &63=45\times1+18 \\ &45=18\times2+9 \\ &18=9\times2+0 \\ &d=9 \\ &\text{} 9=45-18\times2 \\ &=45-(63-45)\times2 \\ &=63\times(-2)+45\times3 \\ &=63\times(-2)+[234-63\times3]\times3 \\ &=63\times(-11)+234\times3 \end{aligned} \]
Corollary
Let \(a,b\in\Z\) with both 0, then \(gcd(a,b)=1\), if and only if, there exists \(m,n\in\Z\) such that \(ma+nb=1\)
Proof
\(\Rightarrow\)) It follows from the theorem with \(d=1\) 6.Bézout's Theorem 裴蜀定理
\(\Leftarrow\)) Suppose that there exist \(m,n\in\Z\) such that \(ma+nb=1\)
Let \(d=gcd(a,b)\) the \(d|a\) and \(d|b\), hence \(d|(ma+nb)=1\) and \(1|d\) we have that \(d=1\)
Remark
If \(d\neq 1\), \(ma+nb=d\) does not imply \(d=gcd(a,b)\).
For example, \(1*2+0*3=2\) but \(gcd(2,3)=1\neq 2\)
Show that congruence module m is an equivalence relation.
Proof
Let \(a,b,c\in\Z\). We need to prove
-
\(a\equiv a\) (mod m) since \(m|a-a=0\)
-
If \(a\equiv b\) (mod m) then \(m|a-b\), hence \(m|b-a\) and thus \(b\equiv a\)
-
If \(a\equiv b\) (mod m) and \(b\equiv c\) (mod m) then \(m|a-b\) and \(m|b-c\)
Hence \(m|(a-b)+(b-c)=a-c\)
Thus \(a\equiv c\) (mod m)
Therefore congruence module m is an equivalence relation
-
Show that \(64|49^n+16n-1\) for all \(n\in\N\)
Basic step: \(n=1\), \(64|49+16-1=64\)
Assume \(n-1\) is true, then \(64|49^{n-1}+16(n-1)-1\), thus \(64\equiv 49^{n-1}+16(n-1)-1 (mod~64)\) 1
\(49^n+16n-1\equiv k(mod~64)\) 2
2-1:
$49^{n-1}(49-1)+16=16(3\cdot 49^{n-1}+1)\equiv k-64(mod~64) $
\(32(\frac{3\cdot 7^{2n-2}+1}{2})\equiv k-64(mod~64)\)
Hence \(k-64\equiv32~or~64(mod~64)\)
Therefore \(k\equiv 32~or~64\)
Suppose \(k\equiv 32\), then \(\frac{3\cdot 7^{2n-2}+1}{2}\not \equiv 2\)
\(3\cdot 7^{2n-2}+1\not \equiv 4\)
\(3\cdot 7^{2n-2}\not \equiv 3\) Contradiction!
Hence \(k\equiv 64\), then \(64|49^n+16n-1\) is true
v2:
Proof
Base step
If \(n=1\) the result is true since \(64|49+16-1=64\)
Inductive step
Suppose that the result is true for \(n\), that is \(64|49^n+16n-1\)
Then \(49^n\equiv -16n+1~(mod~64)\)
\(49^{n+1}=(49)(49^n)\equiv (49)(-16n+1)~(mod~64)\)
Then \(49^{n+1}+16(n+1)-1\equiv (49)(-16n+1)+16(n+1)-1~(mod~64)\)
\(\equiv (-48)(16n)+64~(mod~64)\equiv (-12)(64n)+64~(mod~64)\equiv0~(mod~64)\)
Hence \(64|49^{n+1}+16(n+1)-1\) and thus the result is true for \(n+1\)
-
Show that \(a\equiv b\) (mod m), if and only if, a and b have the same remainder when divided by m
Since \(a\equiv b\), then by definition we have \(m|a-b\)
According to the theorem of integer division
Assume \(a=m\cdot q_a+r_a\) \(b=m\cdot q_b+r_b\), \(0\leq r_1<m\), \(0\leq r_2<m\)
Then, \(m|m\cdot q_a+r_a-(m\cdot q_b+r_b)\)
\(m|m\cdot (q_a-q_b)+(r_a- r_b)\)
Then by theorem \(m\cdot (q_a-q_b)\equiv-(r_a- r_b)~(mod~m)\)
And \(0\equiv(r_a- r_b)~(mod~m)\)
Hence \(r_a= r_b\)
\(\Leftarrow\)) Suppose that \(r_1=r_2\) then
\(a-b=(mq_1+r_1)-(mq_2+r_2)=m(q_1-q_2)\)
That is, \(m|a-b\) and thus \(a\equiv b~(mod~m)\)