# COT 3100 - Homework 3 *Michael Akinyemi* *Tue/Thu 9:00 AM* ### Problem 1: Division Review (10) State the quotient and remainder when dividing $a$ by $b$ for each of the following examples: 1. $a = 147; b = 6$ - $q=24$ - $r=3$ 2. $a = 12,345; b = 106$ - $q=116$ - $r=49$ 3. $a = 77; b = 96$ - $q=0$ - $r=77$ 4. $a = 421$; $b = 77$ - $q=5$ - $r=36$ 5. $a = 176$; $b = 148$ - $q=1$ - $r=28$ ### Problem 2: Greatest Common Divisor and Least Common Multiple (25) Determine the GCD and LCM of: 1. $123$ and $67$ 123 = 1(67) + 56 67 = 1(56) + 11 56 = 5(11) + 1 11 = 11(1) + 0 gcd(123, 67) = 1 --- 2. $609$ and $377$ $609 = 1(377) + 232$ $377 = 1(232) + 145$ $232 = 1(145) + 87$ $145 = 1(87) + 58$ $87 = 1(58) + 29$ $58 = 2(29) + 0$ $gcd(609, 377) = 29$ --- 3. $135$ and $198$ $198 = 1(135) + 63$ $135 = 2(63) + 9$ $63 = 7(9) + 0$ $gcd(135, 198) = 9$ --- 4. $923$ and $7,238$ $7238 = 7(923) + 777$ $923 = 1(777) + 146$ $777 = 5(146) + 47$ $146 = 3(47) + 5$ $47 = 9(5) + 2$ $5 = 2(2) + 1$ $2 = 2(1) + 0$ $gcd(923, 7238) = 1$ ### Problem 3: Modulo Rules (25) Find the remainders when dividing a by b for each of the following examples. Don't use a calculator except for individual steps. You are required to show your work. 1. $a = 7^{15}$; $b = 5$ $7^{15} = 7 \cdot 7^{14}$ $= 7 \cdot (7^2)^7$ $= 7 \cdot 49^7$ $\equiv 2 \cdot 4 \cdot 4^6 \pmod 5$ $=2 \cdot 4 \cdot 4^6$ $=8 \cdot (4^2)^3$ $=8 \cdot 16^3$ $\equiv 3 \cdot 1^3 \pmod 5$ $r=3$ --- 2. $a = 11^{21}$; $b = 7$ $11^{21} = 11 \cdot 11^{20}$ $=11 \cdot (11^2)^{10}$ $= 11 \cdot 121^{10}$ $\equiv 4 \cdot 2^{10} \pmod 7$ $=4 \cdot (2^2)^5$ $=4 \cdot 4^5$ $= 4 \cdot 4 \cdot (4^2)^2$ $=16 \cdot 16^2$ $\equiv 2 \cdot 2^2 \pmod 7$ $=8$ $\equiv 1 \pmod 7$ $r=1$ --- 3. $a = 2^{22}$; $b = 13$ $2^{22}=(2^2)^{11}$ $=4^{11}$ $= 4 \cdot (4^2)^5$ $=4 \cdot 16^5$ $\equiv 4 \cdot 3^5 \pmod {13}$ $=4 \cdot 3 \cdot (3^2)^2$ $=12 \cdot 81$ $\equiv 12 \cdot 3$ $= 36$ $\equiv 10 \pmod {13}$ $r=10$ --- 4. $a = 13^{30}$; $b = 11$ $13^{30}=(13^2)^{15}$ $=169^{15}$ $\equiv 4^{15} \pmod {11}$ $=4 \cdot (4^2)^7$ $=4 \cdot 8 \cdot 8^6$ $=32 \cdot (8^2)^3$ $=32 \cdot 64^3$ $\equiv 10 \cdot 9^3 \pmod {11}$ $= 10 \cdot 9 \cdot 81$ $= 90 \cdot 81$ $\equiv 2 \cdot 4 \pmod {11}$ $r=8$ (I probably should have used mod at the very start on $13^{30}$ to start with an easier base but redoing this doesn’t seem fun at all) --- 5. $a = 3^{31}$; $b = 17$ $3^{31}= 3 \cdot (3^2)^{30}$ $=3 \cdot 9^{30}$ $=3 \cdot (9^2)^{15}$ $=3 \cdot 81^{15}$ $\equiv 3 \cdot 13^{15} \pmod {17}$ $= 3 \cdot (13^2)^7$ $=3 \cdot 169^7$ $\equiv 3 \cdot 16^7 \pmod {17}$ $=3 \cdot 16 \cdot (16^2)^3$ $=48 \cdot 256^3$ $\equiv 14 \cdot 1^3 \pmod {17}$ $r=14$ ### Problem 4: Divisibility (40) 1. Prove that if $3$ divides an integer $n$ with a remainder of $1$, $9$ divides $n^3$ with a remainder of $1$. For some arbitrary $q \in Z$ $n = 3q + 1$ $3 \vert (n-1)$ $n^3 = 9q + 1$ $n^3 - 1 = 9q$ $9 \vert n^3-1$ Goal is to create: $n^3-1=9(\text{some integer stuff})$ $n^3-1=(n-1)(n^2+n+1)$ $=((3q+1)-1)((3q+1)^2+3q+1+1)$ $=(3q)(9q^2+6q+1+3q+1+1)$ $=(3q)(9q^2+9q+3)$ $=18q^2+27q^2+9q$ $n^3-1=9(2q^2+3q^2+q)$ $\therefore 9 \vert n^3 -1$ --- 2. Prove that if $7$ divides an integer $n$ with a remainder of $4$, $21$ divides $3n^2$ with a remainder of $6$. For some arbitrary $q \in Z$ $n=7q+4$ $n-4=7q$ $7 \vert (n-4)$ $3n^2=21q+6$ $3n^2-6 = 21q$ $21 \vert 3n^2-6$ Goals is to create: $3n^2-6=21(\text{some integer stuff})$ $3n^2-6= 3(7q+4)^2-6$ $=3(49q^2+28q+28q+16)-6$ $=147q^2+168q + 42$ $3n^2-6=21(7q^2+8q+2)$ $\therefore 21 \vert 3n^2-6$ --- 3. Prove that if $5$ divides an integer n with a remainder of $4$, $10$ divides $2n^2+4n+3$ with a remainder of $1$. For some arbitrary $q \in Z$ $n=5q+4$ $n-4=5q$ $5 \vert n-4$ $2n^2+4n+3=10q+1$ $2n^2+4n+2=10q$ $10 \vert 2n^2+4n+2$ Goal is to create: $2n^2+4n+2=10(\text{some integer stuff})$ $2n^2+4n+2=2(5q+4)^2+4(5q+4)+2$ $=2(25q^2+40q+16)+20q+16+2$ $=50q^2+80q+32+20q+18$ $=50q^2+100q+50$ $2n^2+4n+2=10(5q^2+10q+5)$ $\therefore 10 \vert 2n^2 + 4n +2$ --- 4. Determine, with proof, any and all pairs of $(x,y)$ integers that satisfy the equation $93,411x+2844y=12,345$. (HINT: Using common divisibility rules will be faster than the various forms of the Euclidean algorithm.) - Use induction?