\documentclass[% version=last,% a5paper, 10pt,% %headings=small,% twoside,% reqno,% parskip=half,% %draft=false,% draft=true,% %DIV=classic,% DIV=12,% headinclude=false,% %titlepage=true,% pagesize] {scrartcl} %\usepackage[utf8]{inputenc} %\usepackage[T1]{fontenc} %\usepackage{pstricks} \usepackage{hfoldsty,url} \usepackage[neverdecrease]{paralist} \usepackage{amsmath,amsthm,amssymb} \newtheorem{problem}{Problem} \newtheorem*{bonus}{Bonus} \theoremstyle{remark} \theoremstyle{definition} \newtheorem*{solution}{Solution} \theoremstyle{remark} \newtheorem*{remark}{Remark} \begin{document} \title{Exam solutions} \date{November 21, 2012} \author{David Pierce} \publishers{Number Theory in English (MAT 221)\\ Mathematics Department\\ Mimar Sinan Fine Arts University, Istanbul\\ \url{dpierce@msgsu.edu.tr}\\ \url{http://mat.msgsu.edu.tr/~dpierce/}} \maketitle \begin{problem} What is wrong with the following argument? \begin{compactenum} \item All positive integers are odd. \item We shall prove this by mathematical induction. \item Obviously $1$ is odd. \item As an inductive hypothesis, we suppose that $1$, $2$, \dots, $n-1$, $n$ are all odd. \item If $n+1$ is odd, we are done. \item Suppose $n+1$ is even. \item We have $n+1\equiv n-1\pmod 2$. \item By inductive hypothesis, $n-1$ is odd. \item Therefore $n+1$ is odd. \item By induction, all positive integers are odd. \end{compactenum} \end{problem} \begin{solution} Step 8 is wrong, since $n$ could be $1$, and in this case $n-1$ is not covered by the inductive hypothesis. \end{solution} \begin{remark} This is the only correct answer. Step 8 is wrong, and Step 8 is wrong \emph{because} the set $\{1,2,\dots,n-1,n\}$ does not actually contain $n-1$ if $n=1$. (The reason why Step 8 is wrong is not that $n-1$ is not always odd.) Step 1 contains an incorrect statement, but it is not an error in the argument as a whole. (If the argument in Steps 2--10 were correct, then Step 1 would be correct.) Step 4 makes the inductive hypothesis that all elements of the set $\{x\in\mathbb Z\colon 1\leqslant x\leqslant n\}$ are odd. Steps 5 and 6 are not actually needed for the argument, but they are not incorrect. Step 7 contains an obviously correct statement. If Step 8 were correct, then Step 9 would be correct. \end{remark} \begin{problem} Recall that the triangular numbers are defined recursively by \begin{align*} t_1&=1,& t_{n+1}&=t_n+n+1. \end{align*} Prove by induction that, for all positive integers $n$, \begin{equation*} t_n+t_{n+1}=(n+1)^2. \end{equation*} \end{problem} \begin{solution} We have \begin{equation*} t_1+t_2=2t_2+2=4=2^2. \end{equation*} Thus the claim holds when $n=1$. Suppose the claim holds when $n=k$, that is, \begin{equation*} t_k+t_{k+1}=(k+1)^2. \end{equation*} Then \begin{align*} t_{k+1}+t_{k+2} &=t_k+k+1+t_{k+1}+k+2\\ &=t_k+t_{k+1}+2k+3\\ &=(k+1)^2+2k+3\\ &=k^2+2k+1+2k+3\\ &=k^2+4k+4\\ &=(k+2)^2. \end{align*} Thus the claim holds when $n=k+1$. Therefore, by induction, the claim holds for all positive integers $n$. \end{solution} \begin{remark} The claim can be proved \emph{directly} (without induction) if one knows $t_n=(t+1)t/2$. However, the problem does not provide this information. When one uses induction, one should \emph{not} present the argument as follows: \begin{gather*} t_{k+1}+t_{k+2}\stackrel?=(k+2)^2\\ t_k+k+1+t_{k+1}+k+2\stackrel?=k^2+4k+4\\ t_k+t_{k+1}\stackrel?=k^2+2k+1\\ t_k+t_{k+1}=(k+1)^2 \end{gather*} \emph{Do not write this way.} Why not? Because nothing here is known to be correct, except the last line. The logical connection between the lines is not clear. One should rearrange the lines and write \begin{equation*} t_k+t_{k+1}=(k+1)^2=k^2+2k+1, \end{equation*} therefore \begin{equation*} t_k+k+1+t_{k+1}+k+2=k^2+4k+4, \end{equation*} that is, \begin{equation*} t_{k+1}+t_{k+2}=(k+2)^2. \end{equation*} \end{remark} \begin{problem} The following is a variant of a famous problem (discussed in class) from the ancient Chinese work called \emph{Mathematical Classic of Master Sun.} \begin{quote} Now there are an unknown number of things. If we count by threes, there is a remainder $1$; if we count by fives, there is a remainder $2$; if we count by sevens, there is a remainder $3$. Find the number of things. \end{quote} \end{problem} \begin{solution} We have to solve \begin{align*} x&\equiv1\pmod3,& x&\equiv2\pmod5,& x&\equiv3\pmod7. \end{align*} The moduli $3$, $5$, and $7$ are pairwise coprime. (In fact they are all distinct primes.) We compute some inverses: \begin{gather*} 5\cdot7=35\equiv2\pmod3,\\ 2\cdot2\equiv1\pmod3,\\ 3\cdot7=21\equiv1\pmod5,\\ 3\cdot5=15\equiv1\pmod7. \end{gather*} Also $3\cdot5\cdot7=21\cdot5=105$. Therefore \begin{equation*} x\equiv35\cdot2+2\cdot21+3\cdot15=70+42+45=157\equiv52\pmod{105}. \end{equation*} The number of things is $52$, or $52+105n$ for some positive integer $n$. \end{solution} \begin{problem} Compute $9^{1815}$ \emph{modulo} $19$. That is, find all integers $x$ such that \begin{align*} 0\leqslant x&<19&&\text{and}&19&\mid 9^{1815}-x. \end{align*} \end{problem} \begin{solution} Since $19$ is prime, by Fermat's Theorem we have, \emph{modulo} $19$, \begin{gather*} 9^{1815}\equiv(9^{18})^{100}\cdot9^{15}\equiv 9^{15}=9^{8+4+2+1}=9^8\cdot9^4\cdot9^2\cdot9,\\ 9^2=81\equiv5,\\ 9^4\equiv5^2=25\equiv6,\\ 9^8\equiv6^2=36\equiv-2,\\ 9^{1815}\equiv-2\cdot6\cdot5\cdot9=-18\cdot30\equiv30\equiv11. \end{gather*} \end{solution} \begin{remark} I believe the foregoing solution is the most efficient. It is less efficient to compute, for example, \begin{equation*} 9^{1815}\equiv(9^{19})^{95}\cdot 9^{10} \equiv9^{95}\cdot9^{10} %\equiv9^{105} \equiv(9^{19})^5\cdot9^{10} \equiv9^{15}. \end{equation*} In any case, one must not remember Fermat's Theorem incorrectly. \end{remark} \begin{problem} Solve the congruence \begin{equation*} 12x\equiv 6\pmod{18}, \end{equation*} that is, find all integers $k$ such that \begin{align*} 12k&\equiv 6\pmod{15}& &\text{and}& 0&\leqslant k\leqslant15. \end{align*} \end{problem} \begin{solution} Because $\gcd(12,6)=6$ and $\gcd(6,15)=3$, we have \begin{align*} 12x\equiv 6\pmod{15} &\iff 2x\equiv1\pmod5\\ &\iff 6x\equiv3\pmod5\\ &\iff x\equiv3\pmod5\\ &\iff x\equiv 3,8,13\pmod{15}. \end{align*} \end{solution} \begin{bonus} List the odd primes in increasing order: \begin{equation*} 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ \dots \end{equation*} Prove that the sum of any two consecutive numbers on this infinite list is the product of three integers that are greater than $1$. For example, \begin{align*} 3+5&=2\cdot2\cdot2,& 17+19&=3\cdot3\cdot4,& 19+23&=2\cdot3\cdot7. \end{align*} \end{bonus} \begin{solution} Suppose $p$ and $q$ are consecutive odd primes. Then $p+q$ is even, and \begin{equation*} p<\frac{p+q}2