Review Exercises (Set A)

  1. Prove that the product of two numbers that take the form $5k+3$, where $k$ is some integer, takes the form $5k+4$.  

    Suppose $a$ and $b$ are numbers of the form $5k+3$, where $k$ is some integer. Then we can find integers $k_1$ and $k_2$, such that

    $$\begin{array}{rcl} ab &=& (5k_1 + 3)(5k_2 + 3)\\ &=& 25k_1 k_2 + 15k_1 + 15k_2 + 9\\ &=& 25k_1 k_2 + 15k_1 + 15k_2 + 5 + 4\\ &=& 5(5k_1 k_2 + 3k_1 + 3k_2 + 1) + 4 \end{array}$$

    We know $5k_1 k_2 + 3k_1 + 3k_2 + 1$ is an integer, by the closure of the integers under addition and multiplication. Hence, $ab$ takes the form $5k+4$ where $k$ is an integer.

    QED.

  2. Prove the irrationality of the following values:

    1. $\sqrt{5}$
    2. $\sqrt[3]{3}$
    3. $\log_7 3$  

      We argue indirectly. Suppose $\log_7 3$ is rational. If so, then we can find integers $p$ and $q$ so that $\log_7 3 = \frac{p}{q}$, where $gcd(p,q) = 1$. Consequently, $7^{(p/q)} = 3$. Raising both sides to the $q^{th}$ power, we have $7^p = 3^q$. However, $7$ and $3$ are both prime -- so we have a single positive integer with two very different prime factorizations. This contradicts the fundamental theorem of arithmetic. Thus, we reject our original assumption and conclude $\log_7 3$ must be irrational.

    4. $\sqrt{3} + \sqrt{7}$, assuming $\sqrt{3}$ is known to be irrational
  3. Use induction to prove the following is true for every positive integer $n$:

    $$1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + 4 \cdot 4! + \cdots + n \cdot n! = (n+1)! - 1$$

    Recall, $n!$ is the factorial of $n$, defined by:

    $$n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1$$

    So for example, the fourth term in the sum above would be $4 \cdot 4! = 4 \cdot (4 \cdot 3 \cdot 2 \cdot 1) = 96$.

    We argue inductively.

    To establish the basis step, note that both $1 \cdot 1! = 1$ and $(1+1)! - 1 = 2 - 1 = 1$. Now, to show the inductive step, assume that

    $$1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + 4 \cdot 4! + \cdots + k \cdot k! = (k+1)! - 1$$ We seek to show $$1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + 4 \cdot 4! + \cdots + k \cdot k! + (k+1) \cdot (k+1)! = (k+2)! - 1$$ To that end, note: $$\begin{array}{rcl} 1 \cdot 1! + 2 \cdot 2! + \cdots + k \cdot k! + (k+1) \cdot (k+1)! &=& \left[ (k+1)! - 1 \right] + (k+1) \cdot (k+1)!\\ &=& (k+1)! + (k+1)(k+1)! - 1\\ &=& (1 + (k+1))(k+1)! - 1\\ &=& (k+2)(k+1)! - 1\\ &=& (k+2)! - 1 \end{array}$$

    Hence, by the principle of mathematical induction, the result holds for all positive integers $n$

  4. Use induction to prove that $7 \mid 13^n - 6^n$ for all positive integers $n$.  

    We argue inductively.

    To establish the basis step, note that if $n=1$, we have $13- 6 = 7$, which is clearly divisible by $7$.

    To establish the inductive step, we assume that $7 \mid 13^k - 6^k$ for some integer $k$. We then seek to show that $7 \mid 13^{k+1} - 6^{k+1}$. To this end, note: $$\begin{array}{rcl} 13^{k+1} - 6^{k+1} &=& 13 \cdot 13^k - 6 \cdot 6^k\\ &=& 7 \cdot 13^k + 6 \cdot 13^k - 6 \cdot 6^k\\ &=& 7 \cdot 13^k + 6 (13^k - 6^k) \end{array}$$

    As $7$ divides both of these terms, it divides their sum, and we have the desired result.

    Thus by the principle of mathematical induction, the claim holds for all positive integers $n$.

  5. Find two primitive Pythagorean triples $a$, $b$, and $c$ such that $a^2 +b^2 = c^2$, $a$ is odd, and $b+c = 81$.  

    Recall, all primitive Pythagorean triples take the form

    $$a=st, \quad b=\frac{s^2 - t^2}{2}, \quad \textrm{ and } \quad c=\frac{s^2 + t^2}{2} \textrm{ with } s\gt t \textrm{ both odd and relatively prime }$$

    Consequently, $b+c=81$ tells us that

    $$\frac{s^2-t^2}{2} + \frac{s^2+t^2}{2} = 81$$

    Simplifying by canceling the $t^2$ terms, we can solve the above to find $s=9$.

    Upon considering that $t$ must be less than $s$, odd, and relatively prime to $s$ -- consider the two possibilities: $t=5$ or $t=7$.

    Plugging $(s,t)=(9,5)$ and $(s,t)=(9,7)$ into the above formulas for $a$, $b$, and $c$ produces the triples sought:

    $$a=45, b=28, c=53 \quad \quad \textrm{ and } \quad \quad a=63, b=15, c=65$$

  6. A large version of the numbered grid shown below is drawn in chalk in a parking lot. 16 people arrange themselves, one person per square on the large grid. At the sound of a bell, if a person is standing on square $n$, they now move to the square whose number is congruent to $5n \pmod{16}$. How many bells must ring before everyone returns to their original squares?


    $$\begin{array}{c|c|c|c}
    1&2&3&4\\\hline
    5&6&7&8\\\hline
    9&10&11&12\\\hline
    13&14&15&16
    \end{array}$$
     

    We are essentially finding the order of a permutation here. The geometry is irrelevant -- consider where each integer goes under the mapping $n \rightarrow 5n \pmod{16}$:

    $$\begin{array}{cccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ 5 & 10 & 15 & 4 & 9 & 14 & 3 & 8 & 13 & 2 & 7 & 12 & 1 & 6 & 11 & 16 \end{array}$$

    This gives the following cycles:

    $$(1,5,9,13), (2,10), (3,15,11,7), (4), (6,14), (8), (12), (16)$$

    So when the bell has rung a multiple of 4 times, persons starting at 1, 5, 9, 13, 3, 15, 11, and 7 are back in their original positions. For 2, 10, 6, and 14, the bell need ring only a multiple of 2 times for these people to be back in their original positions. The rest of the people never leave their square. Consequently, the least common multiple of the cycle lengths 4 and 2 is the first time everyone is back where they started. So four bells ring before this happens.

  7. Find all integers $m$ and $n$ with greatest common divisor $18$ and least common multiple $720$.  

    Recall that the product of the least common multiple and the greatest common divisor of two integers is given by

    $$\textrm{lcm}(m,n) \cdot \gcd(m,n) = mn$$

    As such, the product of the particular value of $m$ and $n$ we seek must be $18 \cdot 720 = 2^5 \cdot 3^4 \cdot 5$.

    If we consider the prime factorization of $m$, note that it must contain at least $2 \cdot 3^2$, as this is the gcd of $m$ and $n$. If it contains more than a single $2$ in its factorization, it must contain $4$ of them, as otherwise, the gcd of $m$ and $n$ would be increased. Similarly, if it doesn't contain any more than a single $2$, $n$ has to contain the rest.

    Likewise, either $m$ or $n$ (but not both) must contain the $5$ in their prime factorization. This gives essentially two possibilities:

    • One number could be $(2 \cdot 3^2) \cdot 2^3 \cdot 5$, leaving the other to be $(2 \cdot 3^2)$, or
    • One number could be $(2 \cdot 3^2) \cdot 2^3$, leaving the other to be $(2 \cdot 3^2) \cdot 5$

    Multiplying things out, this produces the only possible pairs of values $\{720,18\}$ and $\{144,90\}$.

  8. Use the Euclidean Algorithm to find the greatest common divisor of the $12^{th}$ and $15^{th}$ Fibonacci numbers. For the purposes of counting, you may assume the first and second Fibonacci numbers are both equal to one.  

    Recall the Fibonacci numbers, $\{F_n\}$ are defined by the recursive relationship $F_{n+1} = F_n + F_{n-1}$ and $F_0 = F_1 = 1$. So the first few terms are:

    $$1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,\ldots$$

    The $12^{th}$ and $15^{th}$ values in this sequence are $144$ and $610$.

    Using the Euclidean Algorithm to find their greatest common denominator, we discover

    $$\begin{array}{rl} 610 &= 4 \cdot 144 + 34\\ 144 &= 4 \cdot 34 + 8\\ 34 &= 4 \cdot 8 + \fbox{2} \leftarrow gcd\\ 8 &= 4 \cdot 2 + 0 \end{array}$$

  9. Find all integer solutions to $153x+28y=1$  

    First, we observe by inspection that the greatest common divisor (gcd) of 153 and 28 is 1. We will need to go through the calculations required by Euclid's Algorithm to demonstrate this, however, as these calculations are the key to expressing the gcd as a linear combination of the numbers in question: $$\begin{align*} 153 &= 5 \cdot 28 + 13\\ 28 &= 2 \cdot 13 + 2\\ 13 &= 6 \cdot 2 + \fbox{1} \leftarrow \textrm{gcd}\\ 2 &= 2 \cdot 1 + 0 \end{align*}$$ Now, we write $1$ as linear combinations of the various pairs of numbers seen above, working our way backwards through Euclid's Algorithm, until we get $1$ as a linear combination of $153$ and $28$ $$\begin{align*} 1 &= 13 - 6 \cdot 2\\ &= 13 - 6(28 - 2 \cdot 13)\\ &= 13 \cdot 13 - 6 \cdot 28\\ &= 13 (153 - 5 \cdot 28) - 6 \cdot 28\\ &= 13 \cdot 153 - 71 \cdot 28 \end{align*}$$ The last line gives us the solution we seek:

    $$x=13 \quad , \quad y=-71$$

    Now that we have one solution, the set of all solutions is given by:

    $$x = 13 + \left(\frac{28}{\textrm{gcd}(153,28)}\right)k \quad , \quad y=-71 - \left(\frac{153}{\textrm{gcd}(153,28)}\right)k$$ where $k$ is an integer.

    Since $\textrm{gcd}(153,28)=1$, the above collapses to: $$x = 13 + 28k \quad , \quad y=-71 - 153k$$

  10. Solve $28x \equiv 30 \pmod{46}$  

    There are a couple of ways to work this problem. Below are two methods:

    First, upon seeing that $28x$ and $30$ are both even, we divide both sides (and the modulus) by $2$ to obtain

    $$14x \equiv 15\pmod{23}$$

    Then, we would like to know the multiplicative inverse of $14\pmod{23}$. Supposing $a \equiv 14^{-1}\pmod{23}$, we find the value of $a$ with the Euclidean Algorithm and backsolving:

    We know by virtue of being a multiplicative inverse that $14a \equiv 1\pmod{23}$. As such, there is some integer $b$ where: $$1-14a = 23b$$ Writing things in the form of a linear combination, we have: $$14a + 23b = 1$$ These numbers are small enough that we can assure ourselves by inspection that there is no (positive) common divisor of $14$ and $23$ besides $1$. Recall, if there was such a common divisor, we would need to make sure it also divided the right side of the equation).

    We could, of course, have ascertained the same using the Euclidean Algorithm. As we will need the work of the Euclidean Algorithm for the "back-solving" step, let us go ahead and perform it anyways:

    23 = 1 * 14 + 9
    14 = 1 * 9 + 5
    9 = 1 * 5 + 4
    5 = 1 * 4 + 1
    4 = 4 * 1 + 0
    
    gcd(23,14) = 1
    
    1 = 1 * 5 - 1 * 4
    1 = 1 * 5 - 1 * (9 - 1 * 5)
    1 = -1 * 9 + 2 * 5
    1 = -1 * 9 + 2 * (14 - 1 * 9)
    1 = 2 * 14 - 3 * 9
    1 = 2 * 14 - 3 * (23 - 1 * 14)
    1 = -3 * 23 + 5 * 14
    

    Thus, $14^{-1} \equiv a \equiv 5\pmod{23}$

    Returning to the earlier congruence, we have:

    $$5 \cdot 14a \equiv 5 \cdot 15\pmod{23}$$

    Equivalently,

    $$a \equiv 75 \equiv 6\pmod{23}$$

    In the original modulus, this of course equates to two solutions:

    $$a \equiv 6 \textrm{ or } 29\pmod{46}$$

    Here's another way to solve the same original problem:

    Solve $28x \equiv 30\pmod{46}$

    Translating this back to equation form, we have $28x - 30 = 46n$, or equivalently

    $$28x - 46n = 30$$

    We should verify that the gcd of $28$ and $46$ divides $30$, which we can do by inspection, noting $gcd(28,46)=2$. Recall, if the gcd didn't divide the $30$, we would have no solution here. If the numbers were bigger, we can use the Euclidean Algorithm to find the gcd -- and in truth, we should do this anyways, as the steps of the Euclidean Algorithm help us solve the congruence:

    $$\begin{array}{rl} 46 &= 1 \cdot 28 + 18\\ 28 &= 1 \cdot 18 + 10\\ 18 &= 1 \cdot 10 + 8\\ 10 &= 1 \cdot 8 + \fbox{2} \leftarrow gcd\\ 8 &= 4 \cdot 2 + 0 \end{array}$$

    Now we can find a linear combination of $28$ and $46$ that equals the gcd of $2$ by working backwards through the calculations above:

    $$\begin{array}{rl} 2 &= 10 - 8\\ &= 10 - (18 - 10)\\ &= 2 \cdot 10 - 18\\ &= 2 (28 - 18) - 18\\ &= 2 \cdot 28 - 3 \cdot 18\\ &= 2 \cdot 28 - 3 (46 - 28)\\ &= 5 \cdot 28 - 3 \cdot 46 \end{array}$$

    Hence, $x=5$, $n=3$ solves the simpler equation $28x-46n = 2$.

    Since we wish our linear combination of $28$ and $46$ to be fifteen times that (recall $30 = 2 \cdot 15$), we multiply both $x$ and $n$ by $15$ to obtain one solution for the equation we actually care about:

    $$x = 75, n= 45 \quad \quad \textrm{is one solution to} \quad \quad 28x - 46n = 30$$

    With one solution in hand, finding the rest is immediate:

    $$x = 75 + \frac{46}{2} k \quad , \quad n = 45 + \frac{28}{2} k \quad \quad \textrm{where $k$ is an integer}$$ Finally, upon noting that we never really cared about the value of $n$, and only wished to solve the original congruence (which has to do with $x$), and reducing the above in terms of $\pmod{46}$, we have our final solution:

    $$x \equiv 29 + 23k \pmod{46} \quad \quad \textrm{where $k$ is an integer}$$

    or equivalently (since there are only two such non-negative numbers less than $46$),

    $$x \equiv 6 \textrm{ or } 29 \pmod{46}$$