Back Matter
- Page ID
- 26364
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Classical Unsolved Problems
- Is every even number > 2 the sum of two primes? (Goldbach)
- Is every number of the form \(4n + 2\) (\(n > 1\)) the sum of two primes of the form \(4n + 1\)? (Euler)
- Obtain an asymptotic formula for the number of representations of \(2n\) as the sum of two primes.
- Can every even number be expressed as the difference of two primes?
- Can every even number be expressed as the difference of two primes in infinitely many ways?
- In particular, are there infinitely many prime pairs?
- Find an asymptotic formula for the number of prime pairs \(\le x\).
- Do there exist infinitely many primes of the form \(x^2 + 1\)?
- Does any polynomial of degree > 1 represent infinitely many primes?
- Are there infinitely many Fermat primes?
- Are there infinitely many Mersenne primes (primes of the form \(2^p − 1\))?
- Are there infinitely many primes of the form \(2p + 1\), where \(p\) is a prime?
- Is there at least one prime between every pair of consecutive squares?
- Are there odd perfect numbers?
- Are there infinitely many multiply perfect numbers?
- Are there infinitely many pairs of amicable numbers?
- Let \(f(n) = \sigma (n) - n\). Does the sequence \(f_0 (n) = n\), \(f_{k + 1} (n) = f(f_k(n))\), \(k = 1, 2, 3, ...\) remain bounded for every \(n\)? (Poulet)
- Are there infinitely many primes \(p\) for which \(2^{p−1} − 1\) is divisible by \(p^2\)?
- Are there infinitely many primes \(p\) for which \((p − 1)! + 1\) is divisible by \(p^2\)?
- Is \(x^n + y^n = z^n\) solvable for every \(n > 2\)? (Fermat)
- Is \(x_1^n + x_2^n + \cdot\cdot\cdot + x_{n - 1}^n = x_n^n\) solvable for any \(n > 2\)? (Euler)
- Is 2 a primitive root of infinitely many primes? (Artin conjectures that 2 is a primitive root of about one third of all primes.)
- is Euler's constant \(\gamma\) irrational?
- Is \(\pi^{e}\) irrational?
- Are 8 and 9 the only powers (exceeding 1) of integers that differ by 1? (Catalan.)
- For what values of \(k\) is \(x^2 + k = y^3\)?
Miscellaneous Problems
- Show that \(\sum_{d = 1}^n (2d - 1) \lfloor \dfrac{n}{d} \rfloor = \sum_{d = 1}^{n} \lfloor \dfrac{n}{d} \rfloor^2\).
- Show that \(\sum_{d\ |\ n} \tau(d)^3 = (\sum_{d\ |\ n} \tau (d))^2\).
- Show that \(\sum_{(a, b) = 1} \dfrac{1}{(ab)^2} = \dfrac{5}{2}\).
- Show that \(\prod \dfrac{p^2 + 1}{p^2 - 1} = \dfrac{5}{2}\).(The product runs over all primes.)
- Generalize the results of Problems 3 and 4 above.
- Show that \(\text{lim}_{n \to \infty} \sum_{d\ |\ (n! + 1)} \dfrac{1}{d} = 1\).
- Show that \(\text{lim}_{n \to \infty} \sum_{d\ |\ F_n} \dfrac{1}{d} = 1\), where \(F_n = 2^{2^n} + 1\).
- Prove that \(\pi(x) = \sum_{n = 1}^x \sum_{j = 1}^n e^{2\pi i ((n - 1)! + 1)j / n}\).
- Prove that \((a, b) = \sum_{m = 0}^{a - 1} \sum_{n = 1}^{a - 1} \dfrac{1}{a} e^{2\pi i bmn /a}\).
- Show that the least absolute remainder of \(a\) (mod \(b\)) is \(a - b \lfloor \dfrac{2a}{b} \rfloor + b \lfloor \dfrac{a}{b} \rfloor.\)
- Prove that \(\sum_{n = 1}^{\infty} \dfrac{\varphi (n)}{n!}\) is irrational.
- Prove that \(\sum_{n = 1}^{\infty} \dfrac{\sigma (n)}{n!}\) is irrational.
- Prove that \(\sum_{n = 1}^{\infty} \dfrac{\sigma_2 (n)}{n!}\) is irrational.
- Show that \(\sum_{n = 1}^x \dfrac{n}{\sigma(n)} \ge x + 1\).
- Show that \(\sum_{d^2\ |\ n} \mu (d) = |\mu(n)|\).
- Show that for \(g \ne 3, 1 + g + g^2 + g^3 + g^4\) is not a square.
- For \(n\) an integer and \(a \ge 0\) prove that \(\sum_{k = 1}^{n - 1} \lfloor a + \dfrac{k}{n} \rfloor = \lfloor na \rfloor\).
- Show that \(\dfrac{1}{\phi (n)} = \dfrac{1}{n} \sum_{d\ |\ n} \dfrac{\mu^2 (d)}{\phi (d)}\).
- Prove that \(\sum_{n = 1}^{\infty} \dfrac{\mu(n) x^n}{1 + x^n} = x - 2x^2\).
- Prove that \(\dfrac{\lambda (n) x^n}{1 - x^n} = \sum_{n = 1}^{\infty} x^{n^2}.\)
- Prove that \(F(n) = \prod_{d\ |\ n} f(d)\) if and only if \(f(n) = \prod_{d\ |\ n} F(\dfrac{n}{d})^{\mu(d)}\).
- Show that the sum of the odd divisors of \(n\) is \(-\sum_{d\ |\ n} (-1)^{(\dfrac{n}{d})} d.\)
- Prove that the product of the integers \(\ge n\) and relatively prime to \(n\) is \(n^{\varphi(n)} \prod_{d\ |\ n} (\dfrac{d!}{d^d})^{\mu(\dfrac{n}{d})}\).
- Show that every integer has a multiple of the form 11 ... 1100 ... 00.
- Prove that there are infinitely many square-free numbers of the form \(n^2 + 1\).
- Prove that \({m \choose 0} + {m \choose 3} + {m \choose 6} + \cdot\cdot\cdot \not\equiv 0) (mod 3).
- Show that the number of representations of \(n\) as the sum of one or more consecutive positive integers is \(\tau(n_1)\) where n1 is the largest odd divisor of \(n\).
- Prove that \(\varphi (x) = n!\) is solvable for every \(n\).
- Prove that \(\varphi(x) = 2 \cdot 7^n\) is not solvable for any positive \(n\).
- Prove that 30 is the largest integer such that every integer less than it and relatively prime to it is 1 or a prime.
- Let \(a, b, x\) be integers and let \(x_0 = x\), \(x_{n + 1} = ax_n + b\) \(n > 0\). Prove that not all the \(x\)’s are primes.
- Show that the only solutions of \(\varphi(n) = \tau(n)\) are \(n = 2, 3, 4, 8, 14, 20, 90\).
- Show that \(\varphi (n + 1) = p_{n + 1} - p_n\) is valid only for \(1 \le n \le 5\).
- Show that \(\dfrac{(2a)! (2b)!}{a! b!(a+ b)!}\) is an integer.
- show that if \((a, b) = 1\) then \(\dfrac{(a + b - 1)!}{a! b!}\) is an integer.
- Show that an integral polynomial of at least the first degree cannot represent only primes.
- Show that if \(f(x)\) is an integral polynomial of degree > 0, then \(f(x)\) for \(x = 1, 2, ...\) has an infinite number of distinct prime divisors.
- Find the number of integers prime to \(m\) in the set \({1 \cdot 2, 2 \cdot 3, ..., m \cdot (m + 1)}\).
- Prove that the Fermat numbers are relatively prime in pairs.
- Let \(T_1 = 2\), \(T_{n + 1} = T_n^2 - T_{n - 1}\). Prove that \(T_i, T_j) = 1, i \ne j\).
- Prove that \(2 \zeta (3) = \sum_{n = 1}^{\infty} \dfrac{1}{n^2} (1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}).\)
- Prove that the density of numbers for which \((n, \varphi(n)) = 1\) is zero.
- Show that for some \(n\), \(2^n\) has 1000 consecutive 7’s in its digital representation.
- Prove that infinitely many squares do not contain the digit 0.
- Show that for some \(n\), \(p_n\) contains 1000 consecutive 7’s in its digital representation.
- Show that the density of the numbers \(n\) for which \(\varphi(x) = n\) is solvable is zero.
- Show that if \(\varphi(x) = n\) has exactly one solution then \(n > 10^{100}\).
- Prove that \(e_p(n) = \dfrac{n - s_p(n)}{p - 1}\).
- Let \(a_1\), \(a_2\), ..., \(a_{p - 1}\) be ordered by not necessarily distinct nonzero residue classes (mod \(p\)). Prove that there exist \(1 \le i \le j \le p- 1\) such that \(a_i \cdot a_{i + 1} \cdot\cdot\cdot\cdot\cdot a_j \equiv 1\) (mod \(p\)).
- Show that the \(n^{\text{th}}\) prime is the limit of the sequence.
\(n_0 = n, n_{k + 1} = n_0 + \pi(n_0 + n_1 + \cdot\cdot \cdot + n_k).\) - Show that the \(n^{\text{th}}\) nonprime is the limit of the sequence
\(n, n + \pi(n), n + \pi(n + \pi (n)), ... .\) - Prove that every positive integer is either of the form \(n + \pi(n − 1)\) or of the form \(n + p_n\), but not both.
- Show that \((3 + 2 \sqrt{2})^{2n - 1} + (3 - 2\sqrt{2})^{2n - 1} - 2\) is square for every \(n \ge 1\).
- Prove that for every real \(\epsilon > 0\) there exists a real \(\alpha\) such that the fractional part of \(\alpha^n\) is greater than \(1 − \epsilon\) for every integer \(n > 0\).
- Show that if \(p\) and \(q\) are integers \(\le n\), then it is possible to arrange \(n\) or fewer unit resistances to give a combined resistance of \(\dfrac{p}{q}\).
- Show that \((a, n) = 1\) and \(x = a - 12 \sum_{k \ge 1} k [\dfrac{ka}{n}]\) imply \(ax \equiv 1\) (mod \(n\)).
- If \((a, b) = d\) prove that \(\sum_{x = 1}^{a - 1} [\dfrac{bx}{a}] = \dfrac{(a - 1)(b - 1)}{2} + \dfrac{d - 1}{2}\).
- Show that the sum of reciprocals of integers representable as sums of two squares is divergent.
- Show that the sum of reciprocals of integers whose digital representation does not include 1000 consecutive 7’s is convergent.
- Prove that every \(n > 1\) can be expressed as the sum of two deficient numbers.
- Prove that every \(n > 10^5\) can be expressed as the sum of two abundant numbers.
- Prove that every sufficiently large \(n\) can be expressed as the sum of two \(k\)-abundant numbers.
- Prove that the \(n^{\text{th}}\) nonsquare is \(n + {\sqrt{n}}\). {\(x\)} denotes the integer closest to \(x\).)
- Prove that the \(n^{\text{th}}\) nontriangular number is \(n + {\sqrt{2n}}\).
- Prove that the \(n^{\text{th}}\) non-\(k^{\text{th}}\) power is
\(n + \lfloor \sqrt[k]{n + \lfloor \sqrt[k]{n} \rfloor} \rfloor.\) - Show that the binary operation \(\circ\) defined on nonnegative integers by
\(m \circ n = m + n + 2 \lfloor \sqrt{m} \rfloor \lfloor \sqrt{n} \rfloor\)
is associative. - Prove the same for the operation \(m \times n = m + n + 2 {\sqrt{m} } {\sqrt{n} }.\)
- Prove that for \(p > 5\), \((p - 1)! + 1\) contains a prime factor \(\ne p\).
- Show that the only solutions of \((n - 1)! = n^k - 1\) are \((n, k) = (2, 1), (3, 1)\) and (5, 2).
- Show that \(x^{2^{\alpha}} \equiv 2^{2^{\alpha - 1}}\) (mod \(p\)) has a solution for every prime \(p\) if \(\alpha \ge 3\).
- Show that if \(f(x)\) is a polynomial with integer coefficients and \(f(a)\) is a square for each \(a\), then \(f(x) = (g(x))^2\), where \(g(x)\) is a polynomial with integer coefficients.
- Given integers \(a_1 < a_2 \cdot\cdot\cdot < a_k \le n\) with \(k \ge \lfloor \dfrac{n}{2} \rfloor\), prove that for some \(i \le j \le k\), \(a_i \ |\ a_j\).
- Show that two of the \(a_i\)’s of Problem 72 are relatively prime.
- With the \(a\)’s of Problem 72, show that \(a_i + a_j = a_k\) is solvable.
- Show that the number of solutions of \(x + 2y + 3z = n\) in non negative integers is
\({\dfrac{(n + 3)^2}{12}}.\) - Show that the number of solutions of \(x + 2y + 4z = n\) in non negative integers is \({\dfrac{(n + 2)(n + 5)}{16} + (-1)^n \dfrac{n}{16}}\).
- Show that n and n + 2 are simultaneously prime if and only if
\(\sum_{m \ge 1} {\lfloor \dfrac{n + 2}{m} \rfloor + \lfloor \dfrac{n}{m} \rfloor - \lfloor \dfrac{n + 1}{m} \rfloor - \lfloor \dfrac{n - 1}{m} \rfloor} = 4.\) - Show that \(n\) and \(n + 2\) are simultaneously prime if and only if
\(4(n - 1)! + 1 + n \equiv 0\) (mod \(n(n + 2)\)), \((n > 1).\) - Show that for every \(n\), \(6 \cdot 10^{n+2}\), and \(1125 \cdot 10^{2n+1} \pm 8\) are Pythagorean triples.
- Show that the number of ordered pairs of integers whose l.c.m. is \(n\) is \(\tau(n^2)\).
- Show that \(\dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}\) is never an integer.
- Show that \(\dfrac{x^2 + 2y^2}{2x^2 + y^2}\) is a square if and only if \(x = y\).
- Prove that
\(\sum_{n = 1}^{\infty} \dfrac{\varphi(n) x^n}{1 + x^n} = \dfrac{x(1 + x^2)}{(1 - x^2)^2}.\) - show that the number of regular \(n\)-gons of unit edge is \(\dfrac{\varphi(n)}{2}\).
- Prove that the \(n^{\text{th}}\) order determinant with \(a_{ij} = (i, j)\) has value \(\prod_{i = 1}^{n} \varphi(i)\).
- Prove that
\(\sum_{i = 1}^{n} {\sqrt{i}} = {\sqrt{n}} \dfrac{3n + 1 - {\sqrt{n}}^2}{3}.\) - Prove that if \(p = 4n + 3\) and \(q = 8n + 7\) are both prime then \(q\ |\ 2^p − 1\).
- Show how to split the positive integers into two classes so that neither class contains all the positive terms of any arithmetic progression with common difference exceeding 1.
- Show that the reciprocal of every integer \(n > 1\) can be expressed as the sum of a finite number of consecutive terms of the form \(\dfrac{1}{j(j + 1)}\)
- In how many ways can this be done? (Answer: \(\dfrac{1}{2}(\tau(n^2) - 1)\).)
- Show that every rational can be expressed as a sum of a finite number of distinct reciprocals of integers.
- Show that the density of integers for which (\(n\), \(\lfloor \sqrt{n} \rfloor\)) = 1 is \(\dfrac{1}{\pi^2}\).
- Show that the expected value of (\(n\), \(\lfloor \sqrt{n} \rfloor\)) is \(\dfrac{\pi^2}{6}\).
- Prove that \(x^2 \equiv a\) (mod \(p\)) for every prime \(p\) implies that \(a\) is a square.
- Prove that \(f(a, b) = f(a) f(b)\) for \((a, b) = 1\) and \(f(a + 1) \ge f(a)\) for every \(a\) imply that \(f(a) = a^k\).
- Find all primes in the sequence 101, 10101, 1010101, . . . .
- Find all primes in the sequence 1001, 1001001, 1001001001, . . . .
- Show that if \(f(x) > 0\) for all \(x\) and \(f(x) \to 0\) as \(x \to \infty\) then there exists at most a finite number of solutions in integers of \(f(m) + f(n) + f(p) = 1\).
- Prove that the least nonresidue of every prime \(p > 23\) is less than \(\sqrt{p}\).
- Prove the existence of infinite sequences of 1’s, 2’s, and 3’s, no finite part of which is immediately repeated.
- Let \(d^{*}(n)\) denote the number of square divisors of \(n\). Prove that
\(\text{lim}_{n \to \infty} \dfrac{1}{n} \sum_{m = 1}^{n} d^{*} (m) = \dfrac{\pi^2}{6}\). - Find all \(r\) such that \(n!\) cannot end in \(r\) zeros.
- Let \(a_1, a_2, ..., a_n\) be integers with \(a_1 = 1\) and \(a_i < a_{i + 1} \le 2a_i\). Prove that there exists a sequence \({\epsilon_i}\) of \(\pm 1\)'s such that \(\sum_{i = 1}^{n} \epsilon_i a_i = 0\) or 1.
- Show that for \(p\) a prime, \(p \equiv 1\) (mod 4)
\(\lfloor \sqrt{p} \rfloor + \lfloor \sqrt{2p} \rfloor + \cdot\cdot\cdot + \lfloor \sqrt{\dfrac{p - 1}{4} \cdot p} \rfloor = \dfrac{p^2 - 1}{12}.\) - Prove that \(\pi^2\) is irrational.
- Prove that \(\cos \dfrac{p}{q}\) is irrational.
- If \(\dfrac{n_i}{n_1 n_2 ... n_{i - 1}} \to \infty\) prove that \(\sum \dfrac{1}{n_i}\) is irrational.
- Prove that \(ae^2 + be + c \ne 0\) if \(a, b, c\) are integers.
- Prove that
\(\tau(n) = \lfloor \sqrt{n} \rfloor - \lfloor \sqrt{n - 1} \rfloor + 2 \sum_{d = 1}^{\lfloor \sqrt{n - 1} \rfloor} (\lfloor \dfrac{n}{d} \rfloor - \lfloor \dfrac{n - 1}{d} \rfloor).\) - Let \(n= a_0 + a_1 p + a_2 p^2 + \cdot \cdot \cdot + a_k p^k\) where \(p\) is a prime and \(0 \le a_i <p\). Show that the number of binomial coefficients of order \(n\) that are relatively prime to \(p\) is \(\prod (a_i + 1)\).
- Show that if \(r_1, r_2, ..., r_{p - 1}\) form a complete residue system (mod \(p\)) then \(1r_1, 2r_2, ..., (p - 1)r_{p - 1}\) do not.
- Show that 3 is a primitive root of every Fermat prime.
- Show that the number of ways in which \(n\) can be represented as the product of two relatively prime factors is \(2^{\omega(n) - 1}\).
- Prove that every even perfect number is of the form \(2^{p - 1} (2^p - 1)\).
- Show that if \(f(x)\) is a polynomial with integral coefficients and there are \(\psi(m)\) integers relatively prime to m in the set \({f(1), f(2), ..., f(m)}\) then \(\psi\) is a weakly multiplicative function.
- If \(p = 4n + 1\) is a prime, show that \((2n)!^2 + 1 \equiv 0\) (mod \(p\)).
- Show that 128 is the largest integer not representable as the sum of distinct squares.
- Show that \(x^3 + y^4 = z^5\) has infinitely many solutions.
- Show that \(x^n + y^n = x^{n+1}\) has infinitely many solutions.
- Show that for every \(k > 0\) there exists a lattice point (\(x_1, y_1\)) such that for every lattice point (\(x, y\)) whose distance from (\(x_1, y_1\)) does not exceed \(k\), the g.c.d. \((x, y) > 1\).
- Prove that no four distinct squares are in arithmetic progression.
- Prove that for \(n\) composite, \(\pi(n) < \dfrac{n}{\log n}\).
- Prove that \(2^n\ |\ {(n + \sqrt{5})^n}\).
- Prove that an odd \(p\) is prime if and only if \(p + k^2\) is not a square for \(k = 1, 2, ..., \dfrac{p - 3}{2}.\)
Unsolved Problems and Conjectures
- Does \(\varphi (n) = \varphi (n + 1)\) have infinitely many solutions?
- Does \(\sigma(n) = \sigma (n + 1)\) have infinitely many solutions?
- Does \(\varphi (n) = \varphi (n + 1) = \cdot\cdot\cdot = \varphi (n + k)\) have solutions for every \(k\)? (Erd\(\ddot{o}\)s)
- Conjecture: There is no \(n\) for which \(\varphi (x) = n\) has a unique solution. (Carmichael)
- Conjecture: For every positive integer \(k > 1\) there exist infinitely many \(n\) for which \(\varphi (x) = n\) has exactly \(k\) solutions.
- Do there exist solutions of \(\sigma (n) = 2n + 1\)?
- Is \(\varphi (x) = \varphi (y) = 2n\) solvable for every \(n\)? (Moser)
- Are there infinitely many solution of \(\tau (n) = \tau (n + 1)\)?
- Are there infinitely many numbers not of the form \(\phi (n) + n\)? (Erd\(\ddot{o}\)s)
- Are there infinitely many numbers not of the form \(\sigma (n) + n\)? (Erd\(\ddot{o}\)s)
- Do there exist solutions of \(\sigma (x) = m\sigma (y)\) for every integer \(m\)? (Sierpinski)
- Are 1, 2, 4, 8, and 128 the only powers of 2, all of whose digits are powers of 2? (Starke)
- Does there exist for every \(n\), \(n\) distinct integers all of whose sums in pairs are squares? (This is true for \(n \le 5\).)
- Does there exist a sequence of \({\epsilon_i}\) of \(\pm 1\)'s such that \(\sum_{i = 1}^{n} \epsilon_{i \cdot k}\) is bounded for every \(k\)? (Erd\(\ddot{o}\)s)
- If \(f(n)\) is an arithmetic function of period \(k\) and not identically 0, is it true that \(\sum \dfrac{f(n)}{n} \ne 0\)? (Erd\(\ddot{o}\)s)
- Conjecture: For \(n\) sufficiently large, \(n\) can be partitioned \(n = a + b + c + d = d + e + f\) with \(abc = def\). (Motzkin)
- Is \(\sum_{n = 1}^{\infty} \dfrac{\sigma_k (n)}{n!}\) irrational for every \(k\)? (Erd\(\ddot{o}\)s and Kac)
- Is \(\dfrac{1}{x} + \dfrac{1}{y} + \dfrac{1}{z} = \dfrac{4}{n}\) sovable for every \(n\)? (Erd\(\ddot{o}\)s)
- Has \(n! + 1 = x^2\) any solutions with \(n > 7\)? (Brochard)
- Is \(\dfrac{(2n)!}{(n + 2)!^2}\) an integer for infinitely many \(n\)? (Erd\(\ddot{o}\)s)
- Is \(\dfrac{(2n)!}{n! (n + k)!}\) an integer for every \(k\) and infinitely many \(n\)? (Erd\(\ddot{o}\)s)
- Does there exist an \(A\) such that \(\lfloor A^n \rfloor\) is prime for every \(n\)? (Mills)
- Does \(\lfloor e^n \rfloor\) represent infinitely many primes?
- Does \(\lfloor e^n \rfloor\) represent infinitely many composite numbers? (Erd\(\ddot{o}\)s)
- The number 105 has the property that \(105 − 2^n\) is prime whenever it is positive. Is 105 the largest number with this property?
- Is 968 the largest number \(n\) such that for all \(k\) with \((n, k) = 1\) and \(n > k^2\), \(n - k^2\) is prime? (Erd\(\ddot{o}\)s)
- Does there exist a prime \(p > 41\) such that \(x^2 − x + p\) is prime for \(1 \le x \le p−1\)?
- Let \(\alpha (n)\) denote the number of 1’s in the binary representation of \(n\). Does there exist a \(k\) such that for infinitely many primes \(p\), \(\alpha (p) < k\)? (Bellman)
- If \(f(x)\) is a polynomial with integer coefficients, \(f_0 (a) = a\), and \(f_{n+1} (a) = f ( f_n (a))\), can a sequence \(f_n (a)\), \(n = 1, 2, ...\) consist entirely of primes?
- For \(p\) sufficiently large and \(ab \ne 0\), \(n > 2\), does the polynomial \(x^n + ax + b\) assume more than \(\dfrac{p}{2}\) values (mod \(p\))? (Chowla)
- Find pairs of integers \(m\), \(n\) such that \(m\), \(n\) have the same prime factors and \(m + 1\), \(n + 1\) have the same prime factors; e.g., \(m = 2^k - 2\) and \(n = 2^k (2^k - 2)\). Are these the only cases? (Strauss)
- What is the largest integer not representable as the sum of distinct cubes?
- Let \(1 < u_1 < u_2 < \cdot\cdot\cdot\) be the sequence of integers of the form \(x^2 + y^2\). Conjecture:
\(\text{lim}_{n \to \infty} \dfrac{u_{n + 1} - u_n}{u_n^{1/4}} = 0.\) (Chowla and Davenport) - Conjecture: \(|\sum_{n \le x} (-1)^{n - 1} p_n| \thicksim \dfrac{p_x}{2}.\) (Pillai)
- Can every prime \(p \equiv 3\) (mod 8), \(p > 163\), be written as the sum of three distinct squares? (Chowla)
- Is \(\zeta (3)\) irrational? Is \(\zeta (2s + 1)\) irrational?
- Conjecture: The only solution of \(1^n + 2^n + \cdot\cdot\cdot + m^n = (m + 1)^n\) is 1 + 2 = 3. (Bowen)
- Conjecture: the only solutions of \(a^n + (a + 1)^n + \cdot\cdot\cdot + (a + b)^n = (a + b + 1)^n\) are \(1 + 2 = 3\), \(3^2 + 4^2 = 5^2\), and \(3^3 + 4^3 + 5^3 = 6^3\). (Erd\(\ddot{o}\)s)
- Does the equation \(1^2 + 2^2 + \cdot\cdot\cdot + m^2 = (m + 1)^2 + \cdot\cdot\cdot + n^2\) have solutions? (Kelly)?
- The product of \(n > 1\) consecutive integers is not a \(k^{\text{th}}\) power.
- Conjecture: If \(\alpha > 0\) is not an integer then the density of solutions of \((n, n^{\alpha}\) = 1\) is \(6/ \pi^2\). (Lambek and Moser)
- Conjecture: The only solutions of
\(\dfrac{1}{x_1} \dfrac{1}{x_2} + \cdot\cdot\cdot + \dfrac{1}{x_n} + \dfrac{1}{x_1 x_2 ... x_n} = 1\)
are\(^3\)
\(\dfrac{1}{2} + \dfrac{1}{2} = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{6} = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{7} + \dfrac{1}{42} = 1\) (Erd\(\ddot{o}\)s) - Is it true that for all pairs of primes \(p\), \(q\) all sufficiently large numbers can be written as the sum of distinct numbers of the form \(p^{\alpha}q^{\beta}\)? (Erd\(\ddot{o}\)s)
- Let \(a_1, a_2, ...\) be integers not exceeding \(n\) such that the l.c.m. of any two is \(> n\). What in the maximum of \(\sum \dfrac{1}{a_i}\)? Conjecture: 31/30. (Erd\(\ddot{o}\)s)
- Let \(0 < a_1 < a_2 < \cdot\cdot\cdot < a_k \le n\) be such that the sums of distinct \(a_i\)'s are distinct. conjecture: \(k - \log_2 n\) is bounded. (Erd\(\ddot{o}\)s)
- Give a relatively simple proof of Van der Waerden’s theorem for the case of two classes.
- Give a relatively simple proof of Roth’s theorem: Any sequence that does not contain an arithmetic progression has zero density.
- Give an elementary proof of Dirichlet’s theorem on quadratic residues:
\(\sum (\dfrac{n}{p}) > 0\) for \(p \equiv 3\) (mod 4). - Let \(a_1 < a_2 < ...\) be a sequence of positive integers and let \(f(n)\) denote the number of solutions of \(a_i + a_j = n\). Conjecture: If \(f(n) > 0\) for every \(n\) then \(f(n)\) is unbounded. (Erd\(\ddot{o}\)s and Turan)
- If the \(f(n)\) of Problem 49 is > 0 for every \(n\) then every sufficiently large \(n\) can be written as the sum of three distinct \(a\)’s. (Kelly)
- Construct a sequence of a’s for which the \(f(n)\) of Problem 49 is > 0 and for which \(f(n) < \log n\) for every \(n\). (Erd\(\ddot{o}\)s has shown that such sequences exist.)
- Does there exist a sequence \(A\) with counting function \(A(n) < cn/ \log n\) such that every integer can be represented in the form \(a + 2^{i}, a \in A\)?
- Improve the bound \([n!e]\) in Schur’s theorem in combinatorial number theory.
- Conjecture. If \(a_1 < a_2 < \cdot\cdot\cdot\) is a sequence of integers with \(a_n/a_{n+1} \to 1\) and if for every \(d\), every residue (mod \(d\)) is representable as the sum of distinct \(a\)’s, then at most a finite number of integers are not representable as the sum of distinct \(a\)’s. (Erd\(\ddot{o}\)s)
- Is the sum of the reciprocals of those integers that are representable as the sum of \(k\) \(k^{\text{th}}\) powers divergent? (Klamkin and Newman)
- Conjecture: For every \(\epsilon > 0\) there exits an \(N = N(\epsilon)\) such that for \(n > N\) the \(n\)-dimensional game of tic-tac-toe played on a \(3 \times 3 \times \cdot\cdot\cdot \times 3\) board must terminate before \(\epsilon 3^n\) moves have been played. (Moser)
- Same as Problem 56 with 3 replaced by \(k\).
- Every integer belongs to one of the arithmetic progressions {\(2n\)}, {\(3n\)}, {\(4n + 1\)}, {\(6n + 5\)}, {\(12n + 7\)}, \(n = 1, 2, ...\). This is the simplest example of a finite set of arithmetic progressions, each with different common difference, all of whose common differences are greater than one, that contain all integers. Does there exist for every \(c > 0\) such a set of progressions, each common difference being \(> c\)? (Erd\(\ddot{o}\)s)
- Give an explicit representation of \(n\) as the sum of four squares.
- Do there exist for every \(n\), \(n\) primes that are consecutive terms of an arithmetic progression?
- Let \(\dfrac{1}{1 + x + 2x^2} = \sum_{n = 1}^{\infty} a_n x^n\). Conjecture: \(|a_n| > c \log \log n\).
- Are there infinitely primes of the form \(11 \cdot\cdot\cdot 11\)?
- Are there infinitely many Euclid primes \(2 \cdot 3 \cdot \cdot \cdot \cdot \cdot p_n +1\)?
- Conjecture: The least nonresidue of a prime \(p\) is \(< c \log p\).
- Conjecture: The least primitive root of a prime \(p\) is \(< p^{\epsilon}\), \(p > p_0 (\epsilon)\).
- Conjecture: The number of perfect numbers \(\le n\) is \(< c \log n\).
- Find good bounds for the density of the abundant numbers.
- Prove that the ratio of residues to nonresidues in the range \((1, [\sqrt{p}])\) approaches 1 as \(p \to \infty\).
- Give an elementary proof of \(\prod_{p \le n} p < 3^n\).
- Conjecture: \(\text{lim}_{n \to \infty} (a_{n + 1} - a_{n}) = \infty\) implies \(\sum_{n = 1} \dfrac{a_n}{2^{a_n}}\) irrational. (Erd\(\ddot{o}\)s)
- Find all solutions of \(x^4 + y^4 = z^4 + t^4\).
- Find all solutions of \(x^4 + y^4 + z^4 = t^4\).
- Find all solutions of \(x^xy^y = z^z\).
- Let \(\ell (n)\) be the least \(r\) for which there exists a chain of integers
\(a_0 = 1 < a_1 < a_2 < \cdot\cdot\cdot < a_r = n\),
where for each \(i > 0\), \(a_i = a_j + a_k\) for some \(j\), \(k < i\) (\(j = k\) permitted). Conjecture: \(\ell (2^q - 1) \le q + \ell (q) - 1\). (Scholz) - Conjecture: \(\ell (n) < \ell (2n)\) for all \(n > 0\). (Utz)
- Let \(S(n)\) denote the number of solutions of \(\ell (x) = n\). Is it true that \(S(n) < S(n + 1)\) for all \(n > 0\)? (Utz)
- Polya's conjecture: \(\sum_{n = 1}^x \lambda (n) \le 0\), \(x > 1\). (Checked for \(x < 800000.\))
- Turan's conjecture: \(\sum_{n = 1}^{x} \dfrac{\lambda (n)}{n} > 0\). (Checked for \(x < 50000.\))
- Pillai's conjecture: \(|x^m - y^n| < N\), \(m, n > 1\) has for every \(N\) only a finite number of solutions.
- \(2^e\) is irrational.
- Find a reasonable estimate for the number of solutions in positive integers of
\(\dfrac{1}{x_1} + \dfrac{1}{x_2} + \dfrac{1}{x_3} + \cdot\cdot\cdot + \dfrac{1}{x_n} = 1.\)