Graded: 4.2 #32, 4.4 #8

4.2 #2

a) $(1\,0100\,0001)_2$, b) $(11\,1111\,1111)_2$, c) $(1\,1000\,1001\,0001\,1000)_2$

4.2 #4

a) 27, b) 693, c) 958, d) 31775

4.2 #8

\begin{align*} (BADFACED)_{16} &= 11(16^7)+10(16^6)+\cdots+13(16^0) \\ &= (2^3+2^1+2^0)(2^{28}) + (2^3+2^1)(2^{24}) + + \cdots + (2^3+2^2+2^0) \\ &= 2^{31}+2^{29}+2^{28}+2^{27}+2^{25}+\cdots+2^3+2^2+2^0 \\ &= (1011\,1010\,1101\,1111\,1010\,1100\,1110\,1101)_2 \end{align*}

4.2 #22(d)

$$\begin{array}{cccccc} 1&2&0&\stackrel10&\stackrel12&1 \\ + && 2&0&0&2 \\ \hline 1&2&2&1&0&0 \end{array}$$

$$\begin{array}{cccccccccc} &&&& 1&2&0&0&2&1 \\ \times &&&&&& 2&0&0&2 \\ \hline &&& 1&0&1&0&1&1&2 \\ 1&0&1&0&1&1&2 &&& \\ \hline 1&0&1&1&1&2&2&1&1&2 \end{array}$$

$\bigstar$ 4.2 #32

Let $n$ be a positive integer, and let the decimal representation of $n$ be $(a_ka_{k-1}\cdots a_1a_0)_{10}$, so that $$n = a_k(10^k)+a_{k-1}10^{k-1}+\cdots+a_1(10)+a_0.$$ Note that $10 \equiv -1\pmod{11}$, so $10^i\equiv (-1)^i\pmod{11}$ for all integers $i\ge 0$. Therefore, $$n \equiv a_k(-1)^k + a_{k-1}(-1)^{k-1} + \cdots – a_1 + a_0 \pmod{11}.$$ Note that $$(-1)^i = \begin{cases} 1 &\text{ if }i\text{ is even} \\ -1 &\text{ if }i\text{ is odd} \end{cases},$$ so $a_k(-1)^k + a_{k-1}(-1)^{k-1} + \cdots – a_1 + a_0$ is the difference of the sum of the digits of $n$ in even positions and the sum of the digits of $n$ in odd positions. That’s cumbersome to say, so we can call it the “alternating sum of the digits of $n$”.

We showed above that $n$ is congruent modulo 11 to the alternating sum of the digits of $n$. Thus, in particular, if $n$ is divisible by 11, then $n\equiv 0\pmod{11}$, so the alternating sum is 0 (mod 11), so the alternating sum is divisible by 11. Conversely, if the alternating sum is divisible by 11, then so is $n$. $\blacksquare$

4.3 #6

Note that $10^k$ divides $n$ if and only if there are $k$ zeroes at the end of $n$. Thus, we are seeking the highest power of 10 that divides $100!$.

Furthermore, $10^k$ divides $100!$ if and only if both $2^k$ and $5^k$ divide $100!$.

$100!$ is the product of the integers 1 to 100. Among these integers, there are 20 multiples of 5, of which 4 are multiples of $5^2$ (and none are multiples of $5^3$). Thus 5 occurs 24 times in the prime factorization of $100!$. It is clear that 2 appears many more times (in particular, at least 50 times, as 50 of the integers from 1 to 100 are even). Thus $10^{24}$ is the highest power of 10 that divides $100!$, and so the digits of $100!$ end with 24 zeroes.

Remark. If $p$ is prime and $n$ is a positive integer, it can be shown that the exponent of $p$ in the prime factorization of $n$ is $$\left\lfloor\frac np\right\rfloor + \left\lfloor\frac n{p^2}\right\rfloor + \left\lfloor\frac n{p^3}\right\rfloor + \cdots,$$ a sum which is finite because eventually all further terms are 0.

4.3 #12

Consider the $n$ consecutive integers $$(n+1)!+2,(n+1)!+3,(n+1)!+4,\ldots,(n+1)!+(n+1).$$ We’ll show that these integers are all composite.

In particular, consider $(n+1)!+k$, where $2\le k\le n+1$. Then $k~|~(n+1)!$ because $(n+1)!=1\cdot 2\cdot 3\cdot ~\cdots~ \cdot (n+1)$, and $k$ is one of the factors in this product. Therefore, $k~|~(n+1)!+k$. Moreover, $1 < k < (n+1)!+k$, so $(n+1)!+k$ has a divisor other than 1 and itself, which shows that it is composite. $\blacksquare$

4.3 #15 – See back of book

4.3 #28

The gcd is 125; the lcm is 5000. Their product is 625000, which is the same as $1000\cdot 625$.

4.3 #32

c) 1, d) 139

Here are the calculations for (d):

\begin{align*} 14039 &= 9(1529) + 278 \\ 1529 &= 5(278) + 139 \\ 278 &= 2(139) + 0 \end{align*}

4.3 #40

c) \begin{align*} 78 &= 2(35) + 8 \\ 35 &= 4(8) + 3 \\ 8 &= 2(3) + 2 \\ 3 &= 1(2) + 1 \\ 2 &= 2(1) + 0 \\ \\ 1 &= 1(3) – 1(2) \\ &= 1(3) – 1(8 – 2(3)) \\ &= 3(3) – 1(8) \\ &= 3(35 – 4(8)) – 1(8) \\ &= 3(35) – 13(8) \\ &= 3(35) – 13(78 – 2(35)) \\ &= 29(35) – 13(78) \end{align*}

(Note: All possible solutions can be given as $1=35s+78t$, where $s=29+78k$ and $t=-13-35k$ for $k\in\mathbb Z$.)

d) $1 = 21(21) – 8(55)$, or more generally $1 = 21s + 55t$ where $s = 21+55k$ and $t = -8-21k$.

Remark. You may have noticed that 21 and 55 are both Fibonacci numbers, and that the remainders that appear when the Euclidean algorithm is applied to them are also Fibonacci numbers. Not only that, but in the linear combination $(21)(21) – (8)(55)$, the coefficients are also Fibonacci numbers! This is not just a coincidence — and by the way, the Euclidean algorithm is never slower than when you feed it terms that are one or two places apart in the Fibonacci sequence. Can you see why?

4.3 #49 – See back of book

4.3 #50

Let $a,b,m$ be integers, where $m\ge 2$, such that $a\equiv b\pmod m$. By Theorem 4 on p. 241 of the book, $b = a+km$ for some integer $k$. By Lemma 1 on p. 268, $\gcd(b,m) = \gcd(m,a)$. $\blacksquare$

4.4 #6

a) 9, b) 55, c) 89, d) 996

Any other values congruent to these modulo $m$ will work. In particular, the inverse in part (d) can be $-5$, which is a lot easier to recognize than 996.

$\bigstar$ 4.4 #8

Suppose $a,m$ are integers, with $m > 2$, such that $\gcd(a,m) = g > 1$. Also suppose, aiming for a contradiction, that $a$ has an inverse modulo $m$, and call this inverse $b$. Then $ab\equiv 1\pmod m$, so $ab = 1+mk$ for some integer $k$. Therefore, $$ab-mk=1.$$ But $g$ divides $a$ and $m$, so the left side is divisible by $g$ and the right side isn’t; we have a contradiction. We conclude that $a$ has no inverse modulo $m$. $\blacksquare$

4.4 #12

a) Multiply both sides by 55, and reduce modulo 89, to get $x \equiv 52\pmod{89}$.

b) $x\equiv 123\pmod{233}$

c) $x\equiv 936\pmod{1001}$

4.4 #20

$$\begin{array}{ccccc} i & a_i & m_i & M_i & y_i \\ \hline 1 & 2 & 3 & 20 & 2 \\ 2 & 1 & 4 & 15 & 3 \\ 3 & 3 & 5 & 12 & 3 \end{array}$$ \begin{align*} x_0 &= a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3 \\ &= (2)(20)(2) + (1)(15)(3) + (3)(12)(3) \\ &= 233 \end{align*} General solution: $x \equiv 53\pmod{60}$

4.4 #22

If $x\equiv 3\pmod 6$, then $x=3+6k$ for an integer $k$. If, furthermore, $x\equiv 4\pmod 7$, then $$3+6k\equiv 4\pmod 7.$$ Subtracting 3 from both sides gives $6k \equiv 1 \pmod 7$. Multiplying both sides by 6 (which is its own inverse modulo 7) gives $k \equiv 6\pmod 7$, so $k=6+7\ell$ for an integer $\ell$. Substituting back into $x=3+6k$ gives \begin{align*} x &= 3+6(6+7\ell) \\ &= 39+42\ell. \end{align*} Thus the general solution is $x \equiv 39\pmod{42}$.

4.4 #26

This problem is not your standard Chinese Remainder Theorem problem, because the moduli 6, 10, and 15 are not relatively prime. The trick is to rewrite each congruence as an equivalent pair of congruences with prime moduli. For example, $x\equiv 5\pmod 6$ if and only if $x\equiv 1\pmod 2$ and $x\equiv 2\pmod 3$.

Likewise, $x\equiv 3\pmod{10}$ if and only if $x\equiv 1\pmod 2$ and $x\equiv 3\pmod 5$.

Likewise, $x\equiv 8\pmod{15}$ if and only if $x\equiv 2\pmod 3$ and $x\equiv 3\pmod 5$.

Therefore, our original system has become a system of six congruences: $$\begin{cases} x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 1\pmod 2 \\ x\equiv 3\pmod 5 \\ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 5 \end{cases}.$$ But there are really only three congruences there, each appearing twice. We can solve this system in the usual way, getting the solution $x\equiv 23\pmod{30}$.

Remark. In this case, the system of six congruences modulo 2, 3, and 5 turned out to be massively redundant. But there is another possible outcome: it might have been inconsistent, if for example it had included the congruences $x\equiv 3\pmod 5$ and $x\equiv 4\pmod 5$. In that case, there would have been no solutions.