Back Matter
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 ≤x.
- Do there exist infinitely many primes of the form x2+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 2p−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)=σ(n)−n. Does the sequence f0(n)=n, fk+1(n)=f(fk(n)), k=1,2,3,... remain bounded for every n? (Poulet)
- Are there infinitely many primes p for which 2p−1−1 is divisible by p2?
- Are there infinitely many primes p for which (p−1)!+1 is divisible by p2?
- Is xn+yn=zn solvable for every n>2? (Fermat)
- Is xn1+xn2+⋅⋅⋅+xnn−1=xnn 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 γ irrational?
- Is πe irrational?
- Are 8 and 9 the only powers (exceeding 1) of integers that differ by 1? (Catalan.)
- For what values of k is x2+k=y3?
Miscellaneous Problems
- Show that ∑nd=1(2d−1)⌊nd⌋=∑nd=1⌊nd⌋2.
- Show that ∑d | nτ(d)3=(∑d | nτ(d))2.
- Show that ∑(a,b)=11(ab)2=52.
- Show that ∏p2+1p2−1=52.(The product runs over all primes.)
- Generalize the results of Problems 3 and 4 above.
- Show that limn→∞∑d | (n!+1)1d=1.
- Show that limn→∞∑d | Fn1d=1, where Fn=22n+1.
- Prove that π(x)=∑xn=1∑nj=1e2πi((n−1)!+1)j/n.
- Prove that (a,b)=∑a−1m=0∑a−1n=11ae2πibmn/a.
- Show that the least absolute remainder of a (mod b) is a−b⌊2ab⌋+b⌊ab⌋.
- Prove that ∑∞n=1φ(n)n! is irrational.
- Prove that ∑∞n=1σ(n)n! is irrational.
- Prove that ∑∞n=1σ2(n)n! is irrational.
- Show that ∑xn=1nσ(n)≥x+1.
- Show that ∑d2 | nμ(d)=|μ(n)|.
- Show that for g≠3,1+g+g2+g3+g4 is not a square.
- For n an integer and a≥0 prove that ∑n−1k=1⌊a+kn⌋=⌊na⌋.
- Show that 1ϕ(n)=1n∑d | nμ2(d)ϕ(d).
- Prove that ∑∞n=1μ(n)xn1+xn=x−2x2.
- Prove that λ(n)xn1−xn=∑∞n=1xn2.
- Prove that F(n)=∏d | nf(d) if and only if f(n)=∏d | nF(nd)μ(d).
- Show that the sum of the odd divisors of n is −∑d | n(−1)(nd)d.
- Prove that the product of the integers ≥n and relatively prime to n is nφ(n)∏d | n(d!dd)μ(nd).
- 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 n2+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 τ(n1) where n1 is the largest odd divisor of n.
- Prove that φ(x)=n! is solvable for every n.
- Prove that φ(x)=2⋅7n 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 x0=x, xn+1=axn+b n>0. Prove that not all the x’s are primes.
- Show that the only solutions of φ(n)=τ(n) are n=2,3,4,8,14,20,90.
- Show that φ(n+1)=pn+1−pn is valid only for 1≤n≤5.
- Show that (2a)!(2b)!a!b!(a+b)! is an integer.
- show that if (a,b)=1 then (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⋅2,2⋅3,...,m⋅(m+1).
- Prove that the Fermat numbers are relatively prime in pairs.
- Let T1=2, Tn+1=T2n−Tn−1. Prove that Ti,Tj)=1,i≠j.
- Prove that 2ζ(3)=∑∞n=11n2(1+12+13+⋅⋅⋅+1n).
- Prove that the density of numbers for which (n,φ(n))=1 is zero.
- Show that for some n, 2n 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, pn contains 1000 consecutive 7’s in its digital representation.
- Show that the density of the numbers n for which φ(x)=n is solvable is zero.
- Show that if φ(x)=n has exactly one solution then n>10100.
- Prove that ep(n)=n−sp(n)p−1.
- Let a1, a2, ..., ap−1 be ordered by not necessarily distinct nonzero residue classes (mod p). Prove that there exist 1≤i≤j≤p−1 such that ai⋅ai+1⋅⋅⋅⋅⋅aj≡1 (mod p).
- Show that the nth prime is the limit of the sequence.
n0=n,nk+1=n0+π(n0+n1+⋅⋅⋅+nk). - Show that the nth nonprime is the limit of the sequence
n,n+π(n),n+π(n+π(n)),.... - Prove that every positive integer is either of the form n+π(n−1) or of the form n+pn, but not both.
- Show that (3+2√2)2n−1+(3−2√2)2n−1−2 is square for every n≥1.
- Prove that for every real ϵ>0 there exists a real α such that the fractional part of αn is greater than 1−ϵ for every integer n>0.
- Show that if p and q are integers ≤n, then it is possible to arrange n or fewer unit resistances to give a combined resistance of pq.
- Show that (a,n)=1 and x=a−12∑k≥1k[kan] imply ax≡1 (mod n).
- If (a,b)=d prove that ∑a−1x=1[bxa]=(a−1)(b−1)2+d−12.
- 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>105 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 nth nonsquare is n+√n. {x} denotes the integer closest to x.)
- Prove that the nth nontriangular number is n+√2n.
- Prove that the nth non-kth power is
n+⌊k√n+⌊k√n⌋⌋. - Show that the binary operation ∘ defined on nonnegative integers by
m∘n=m+n+2⌊√m⌋⌊√n⌋
is associative. - Prove the same for the operation m×n=m+n+2√m√n.
- Prove that for p>5, (p−1)!+1 contains a prime factor ≠p.
- Show that the only solutions of (n−1)!=nk−1 are (n,k)=(2,1),(3,1) and (5, 2).
- Show that x2α≡22α−1 (mod p) has a solution for every prime p if α≥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 a1<a2⋅⋅⋅<ak≤n with k≥⌊n2⌋, prove that for some i≤j≤k, ai | aj.
- Show that two of the ai’s of Problem 72 are relatively prime.
- With the a’s of Problem 72, show that ai+aj=ak is solvable.
- Show that the number of solutions of x+2y+3z=n in non negative integers is
(n+3)212. - Show that the number of solutions of x+2y+4z=n in non negative integers is (n+2)(n+5)16+(−1)nn16.
- Show that n and n + 2 are simultaneously prime if and only if
∑m≥1⌊n+2m⌋+⌊nm⌋−⌊n+1m⌋−⌊n−1m⌋=4. - Show that n and n+2 are simultaneously prime if and only if
4(n−1)!+1+n≡0 (mod n(n+2)), (n>1). - Show that for every n, 6⋅10n+2, and 1125⋅102n+1±8 are Pythagorean triples.
- Show that the number of ordered pairs of integers whose l.c.m. is n is τ(n2).
- Show that 12+13+⋅⋅⋅+1n is never an integer.
- Show that x2+2y22x2+y2 is a square if and only if x=y.
- Prove that
∑∞n=1φ(n)xn1+xn=x(1+x2)(1−x2)2. - show that the number of regular n-gons of unit edge is φ(n)2.
- Prove that the nth order determinant with aij=(i,j) has value ∏ni=1φ(i).
- Prove that
∑ni=1√i=√n3n+1−√n23. - Prove that if p=4n+3 and q=8n+7 are both prime then q | 2p−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 1j(j+1)
- In how many ways can this be done? (Answer: 12(τ(n2)−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, ⌊√n⌋) = 1 is 1π2.
- Show that the expected value of (n, ⌊√n⌋) is π26.
- Prove that x2≡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)≥f(a) for every a imply that f(a)=ak.
- 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)→0 as x→∞ 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 √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
limn→∞1n∑nm=1d∗(m)=π26. - Find all r such that n! cannot end in r zeros.
- Let a1,a2,...,an be integers with a1=1 and ai<ai+1≤2ai. Prove that there exists a sequence ϵi of ±1's such that ∑ni=1ϵiai=0 or 1.
- Show that for p a prime, p≡1 (mod 4)
⌊√p⌋+⌊√2p⌋+⋅⋅⋅+⌊√p−14⋅p⌋=p2−112. - Prove that π2 is irrational.
- Prove that cospq is irrational.
- If nin1n2...ni−1→∞ prove that ∑1ni is irrational.
- Prove that ae2+be+c≠0 if a,b,c are integers.
- Prove that
τ(n)=⌊√n⌋−⌊√n−1⌋+2∑⌊√n−1⌋d=1(⌊nd⌋−⌊n−1d⌋). - Let n=a0+a1p+a2p2+⋅⋅⋅+akpk where p is a prime and 0≤ai<p. Show that the number of binomial coefficients of order n that are relatively prime to p is ∏(ai+1).
- Show that if r1,r2,...,rp−1 form a complete residue system (mod p) then 1r1,2r2,...,(p−1)rp−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ω(n)−1.
- Prove that every even perfect number is of the form 2p−1(2p−1).
- Show that if f(x) is a polynomial with integral coefficients and there are ψ(m) integers relatively prime to m in the set f(1),f(2),...,f(m) then ψ is a weakly multiplicative function.
- If p=4n+1 is a prime, show that (2n)!2+1≡0 (mod p).
- Show that 128 is the largest integer not representable as the sum of distinct squares.
- Show that x3+y4=z5 has infinitely many solutions.
- Show that xn+yn=xn+1 has infinitely many solutions.
- Show that for every k>0 there exists a lattice point (x1,y1) such that for every lattice point (x,y) whose distance from (x1,y1) 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, π(n)<nlogn.
- Prove that 2n | (n+√5)n.
- Prove that an odd p is prime if and only if p+k2 is not a square for k=1,2,...,p−32.
Unsolved Problems and Conjectures
- Does φ(n)=φ(n+1) have infinitely many solutions?
- Does σ(n)=σ(n+1) have infinitely many solutions?
- Does φ(n)=φ(n+1)=⋅⋅⋅=φ(n+k) have solutions for every k? (Erd¨os)
- Conjecture: There is no n for which φ(x)=n has a unique solution. (Carmichael)
- Conjecture: For every positive integer k>1 there exist infinitely many n for which φ(x)=n has exactly k solutions.
- Do there exist solutions of σ(n)=2n+1?
- Is φ(x)=φ(y)=2n solvable for every n? (Moser)
- Are there infinitely many solution of τ(n)=τ(n+1)?
- Are there infinitely many numbers not of the form ϕ(n)+n? (Erd¨os)
- Are there infinitely many numbers not of the form σ(n)+n? (Erd¨os)
- Do there exist solutions of σ(x)=mσ(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≤5.)
- Does there exist a sequence of ϵi of ±1's such that ∑ni=1ϵi⋅k is bounded for every k? (Erd¨os)
- If f(n) is an arithmetic function of period k and not identically 0, is it true that ∑f(n)n≠0? (Erd¨os)
- Conjecture: For n sufficiently large, n can be partitioned n=a+b+c+d=d+e+f with abc=def. (Motzkin)
- Is ∑∞n=1σk(n)n! irrational for every k? (Erd¨os and Kac)
- Is 1x+1y+1z=4n sovable for every n? (Erd¨os)
- Has n!+1=x2 any solutions with n>7? (Brochard)
- Is (2n)!(n+2)!2 an integer for infinitely many n? (Erd¨os)
- Is (2n)!n!(n+k)! an integer for every k and infinitely many n? (Erd¨os)
- Does there exist an A such that ⌊An⌋ is prime for every n? (Mills)
- Does ⌊en⌋ represent infinitely many primes?
- Does ⌊en⌋ represent infinitely many composite numbers? (Erd¨os)
- The number 105 has the property that 105−2n 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>k2, n−k2 is prime? (Erd¨os)
- Does there exist a prime p>41 such that x2−x+p is prime for 1≤x≤p−1?
- Let α(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, α(p)<k? (Bellman)
- If f(x) is a polynomial with integer coefficients, f0(a)=a, and fn+1(a)=f(fn(a)), can a sequence fn(a), n=1,2,... consist entirely of primes?
- For p sufficiently large and ab≠0, n>2, does the polynomial xn+ax+b assume more than p2 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=2k−2 and n=2k(2k−2). Are these the only cases? (Strauss)
- What is the largest integer not representable as the sum of distinct cubes?
- Let 1<u1<u2<⋅⋅⋅ be the sequence of integers of the form x2+y2. Conjecture:
limn→∞un+1−unu1/4n=0. (Chowla and Davenport) - Conjecture: |∑n≤x(−1)n−1pn|∼px2. (Pillai)
- Can every prime p≡3 (mod 8), p>163, be written as the sum of three distinct squares? (Chowla)
- Is ζ(3) irrational? Is ζ(2s+1) irrational?
- Conjecture: The only solution of 1n+2n+⋅⋅⋅+mn=(m+1)n is 1 + 2 = 3. (Bowen)
- Conjecture: the only solutions of an+(a+1)n+⋅⋅⋅+(a+b)n=(a+b+1)n are 1+2=3, 32+42=52, and 33+43+53=63. (Erd¨os)
- Does the equation 12+22+⋅⋅⋅+m2=(m+1)2+⋅⋅⋅+n2 have solutions? (Kelly)?
- The product of n>1 consecutive integers is not a kth power.
- Conjecture: If α>0 is not an integer then the density of solutions of (n,nα = 1\) is 6/π2. (Lambek and Moser)
- Conjecture: The only solutions of
1x11x2+⋅⋅⋅+1xn+1x1x2...xn=1
are3
12+12=12+13+16=12+13+17+142=1 (Erd¨os) - 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αqβ? (Erd¨os)
- Let a1,a2,... be integers not exceeding n such that the l.c.m. of any two is >n. What in the maximum of ∑1ai? Conjecture: 31/30. (Erd¨os)
- Let 0<a1<a2<⋅⋅⋅<ak≤n be such that the sums of distinct ai's are distinct. conjecture: k−log2n is bounded. (Erd¨os)
- 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:
∑(np)>0 for p≡3 (mod 4). - Let a1<a2<... be a sequence of positive integers and let f(n) denote the number of solutions of ai+aj=n. Conjecture: If f(n)>0 for every n then f(n) is unbounded. (Erd¨os 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)<logn for every n. (Erd¨os has shown that such sequences exist.)
- Does there exist a sequence A with counting function A(n)<cn/logn such that every integer can be represented in the form a+2i,a∈A?
- Improve the bound [n!e] in Schur’s theorem in combinatorial number theory.
- Conjecture. If a1<a2<⋅⋅⋅ is a sequence of integers with an/an+1→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¨os)
- Is the sum of the reciprocals of those integers that are representable as the sum of k kth powers divergent? (Klamkin and Newman)
- Conjecture: For every ϵ>0 there exits an N=N(ϵ) such that for n>N the n-dimensional game of tic-tac-toe played on a 3×3×⋅⋅⋅×3 board must terminate before ϵ3n 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¨os)
- 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 11+x+2x2=∑∞n=1anxn. Conjecture: |an|>cloglogn.
- Are there infinitely primes of the form 11⋅⋅⋅11?
- Are there infinitely many Euclid primes 2⋅3⋅⋅⋅⋅⋅pn+1?
- Conjecture: The least nonresidue of a prime p is <clogp.
- Conjecture: The least primitive root of a prime p is <pϵ, p>p0(ϵ).
- Conjecture: The number of perfect numbers ≤n is <clogn.
- Find good bounds for the density of the abundant numbers.
- Prove that the ratio of residues to nonresidues in the range (1,[√p]) approaches 1 as p→∞.
- Give an elementary proof of ∏p≤np<3n.
- Conjecture: limn→∞(an+1−an)=∞ implies ∑n=1an2an irrational. (Erd¨os)
- Find all solutions of x4+y4=z4+t4.
- Find all solutions of x4+y4+z4=t4.
- Find all solutions of xxyy=zz.
- Let ℓ(n) be the least r for which there exists a chain of integers
a0=1<a1<a2<⋅⋅⋅<ar=n,
where for each i>0, ai=aj+ak for some j, k<i (j=k permitted). Conjecture: ℓ(2q−1)≤q+ℓ(q)−1. (Scholz) - Conjecture: ℓ(n)<ℓ(2n) for all n>0. (Utz)
- Let S(n) denote the number of solutions of ℓ(x)=n. Is it true that S(n)<S(n+1) for all n>0? (Utz)
- Polya's conjecture: ∑xn=1λ(n)≤0, x>1. (Checked for x<800000.)
- Turan's conjecture: ∑xn=1λ(n)n>0. (Checked for x<50000.)
- Pillai's conjecture: |xm−yn|<N, m,n>1 has for every N only a finite number of solutions.
- 2e is irrational.
- Find a reasonable estimate for the number of solutions in positive integers of
1x1+1x2+1x3+⋅⋅⋅+1xn=1.