Fun Problems in Number Theory

This is a collection of problems from Number Theory. What they all have in common is that the results involve concepts and operations we’re all familiar with, so anyone can go “huh, that’s a neat fact about numbers!“. Regarding difficulty, the “easy” problems should be solvable for anyone, though they may not be that easy. The “medium” problems actually all come from homeworks from early in my undergraduate Number Theory course. They’re quite solvable, but may require insights and ideas that are not reasonable to expect from the leyperson. The “hard” problems are quite hard.

Jump To

Easy Problems


Let nn be any natural number, and ss the sum of the digits of nn. Prove that nsn - s is a multiple of 99.

For example, if n=31n = 31, then s=3+1=4s = 3 + 1 = 4, and 314=2731 - 4 = 27, which is a multiple of 99.


Let n=a+10b+100c+n = a + 10b + 100c + \dots. Then s=a+b+c+s = a + b + c + \dots.
Then ns=aa+10bb+100cc+=0a+9b+99c+n - s = a - a + 10b - b + 100c - c + \dots = 0a + 9b + 99c + \dots, which is clearly a multiple of 9.


Prove that a natural number nn is prime1 if and only if nn is not divisible by any prime pp with 1<pn1 < p \leq \sqrt{n}.


Proving     \implies
This follows directly from the fact that integer primes are irreducible.

Proving     \impliedby
Clearly if there were such a prime pp in range (1,n](1, \sqrt{n}], nn would not be prime. So then it suffices to show why the range (n,n)(\sqrt{n}, n) need not be checked.
The largest value that can be produced by a pair in range (1,n](1, \sqrt{n}] is nn=n\sqrt{n} \cdot \sqrt{n} = n.
That means in order for a value greater than n\sqrt{n} to be a divisor, so too must there be a value less than n\sqrt{n}.
So if no such value less than n\sqrt{n} exists, no such value greater than n\sqrt{n} can exist.

Medium Problems



A number nZn \in \mathbb{Z} is divisible by 3 if and only if the sum of the digits of nn is divisible by 3.

Write n=a+10b+100c+n = a + 10b + 100c + \dots, where the digits of nn are a,b,c,a, b, c, \dots.
Since 101(mod3)10 \equiv 1 \pmod{3}, n=a+10b+100c+a+b+c+(mod3)n = a + 10b + 100c + \dots \equiv a + b + c + \dots \pmod{3}.
The proposition follows.


A number nZn \in \mathbb{Z} is divisible by 5 if and only if the rightmost digit is 5 or 0.


Write n=a+10b+100c+n = a + 10b + 100c + \dots.
Since 100(mod5)10 \equiv 0 \pmod{5}, n=a+10b+100c+a(mod5)n = a + 10b + 100c + \dots \equiv a \pmod{5}.
The only nonnegative integers less than 10 (i.e. that aa could be) are 5 or 0.
The propositon follows.


A number nZn \in \mathbb{Z} is divisible by 9 if and only if the sum of the digits is.


Write n=a+10b+100c+n = a + 10b + 100c + \dots.
Since 101(mod9)10 \equiv 1 \pmod{9}, n=a+10b+100c+a+b+c+(mod9)n = a + 10b + 100c + \dots \equiv a + b + c + \dots \pmod{9}.
The propositon follows.


A number nZn \in \mathbb{Z} is divisible by 11 if and only if the difference between the sum of the digits at even indices and the ones at odd indices are congruent to 0(mod11)0 \pmod{11}.


Write n=a+10b+100c+n = a + 10b + 100c + \dots.
Since 101(mod11)10 \equiv -1 \pmod{11}, n=a+10b+100c+a+bc+(mod11)n = a + 10b + 100c + \dots \equiv -a + b - c + \dots \pmod{11}.
The propositon follows.

Additional Note

Definition (Palindrome): let the digits of n(mod11)n \in \pmod{11} be of the form Then nn is a palindrome.
Remark: From the proof above, it follows that all even-length palindromes are divisible by 11.
Conjecture: All palindromes divisible by 11 are such that the product of their digits is a perfect square.


Prove that if n>4n > 4 is composite then n(n1)!n | (n - 1)!.


An equivalent statement: if n>4n > 4 is composite, then nn is a factor of (n1)!(n-1)!.
nn is a product of prime factors.
If all such factors are unique in the product, then trivially they are all present in the product (n1)!(n-1)!.
If there are duplicates, they can be thought of as multiplying to unique composite numbers less than nn, due to the fundamental theorem of arithmetic.
The only time this is not true is for the composite n=4n = 4, since 3!3! is divisible by no composite numbers.
Hence, all prime factors of nn can be accounted for in (n1)!(n-1)! when n>4n > 4, so nn is a factor of (n1)!(n-1)!


Prove that if a positive integer n is a perfect square, then n cannot be written in the form 4k+34k + 3 for kk an integer.


Compute the remainder upon division by 4 of each of (4m)2(4m)^2, (4m+1)2(4m + 1)^2, (4m+2)2(4m + 2)^2, and (4m+3)2(4m + 3)^2.


Any positive integer of the form 4k+34k+3 is congruent to 3(mod4)3 (mod 4).
If nn is even, then n2n^2 is even, and trivially cannot be of the form 4k+34k+3.
If nn is odd, then n=2m+1n = 2m + 1, mNm \in \mathbb{N}.
Then (2m+1)2=4m2+4m+1(2m+1)^2 = 4m^2 + 4m + 1, which is congruent to 3 (mod 4), so cannot be of the form 4k+34k+3.


(Follow-up to 2.3)

Prove that no integer in the sequence below is a perfect square.

1111, 111111, 11111111, 1111111111, \dots


111111=111108+3=4k+3111 \dots 111 = 111 \dots 108 + 3 = 4k+ 3.


Per the hint, all integers in the given sequence are of the form 4k+34k + 3, and we just showed that no positive integer of that form may be a perfect square, so we are done.


Prove that if pp is a positive integer such that both pp and p2+2p^2 + 2 are prime, then p=3p = 3.


Trivially, 2 does not satisfy the conditons and 3 does.
Now we consider only primes p>3p > 3.
Every third integer is a multiple of 3, yet no pp is.
So for all pp, it is either that 3p+13 \mid p + 1 or 3p+23 \mid p + 2.
That is, p1(mod3)p \equiv 1 \pmod{3} or p1(mod3)p \equiv -1 \pmod{3}.
In either case, this gives p21(mod3)p^2 \equiv 1 \pmod{3}, so p2+20(mod3)p^2 + 2 \equiv 0 \pmod{3}.
Therefore, for all primes greater than 3, 3p2+23 | p^2 + 2, and p2+2p^2 + 2 is composite.

Hard Problems

Fermat’s Last Theorem

Prove that no triple a,b,cNa, b, c \in \mathbb{N} satisfy the equation an+bn=cna^n + b^n = c^n, where nNn \in \mathbb{N} is greater than 22.


I am unable to find a copy of the original proof by Andrew Wiles, but this source should be pretty close. Yes, the proof is that long.

Read more about the theorem and its incredible story here.

Collatz Conjecture

Consider the following operation on an arbitrary positive integer:

f(n)={n/2,if n0(mod2)3n+1,if n1(mod2)}f(n) = \left\{ \begin{array}{lr} n / 2, & \text{if } n \equiv 0 \pmod{2}\\ 3n + 1, & \text{if }n \equiv 1 \pmod{2} \end{array} \right\}

Prove that for all nn, this function will eventually return 1.


There is no known proof of this conjecture. Read more about it here.

Goldbach’s Conjecture

Prove that every even nNn \in \mathbb{N} greater than 2 is the sum of two primes.


There is no known proof to this conjecture. Read more about it here.


  1. In the integers, a prime pp is a positive integer with the property that if pp divides abab then pp divides aa or p divides bb, where aa and bb are integers and the property that pp is only divisible by 1 and pp (irreducibility). By the Fundamental Theorem of Arithmetic, every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. So primes can be thought of as unique, atomic building blocks wihtin the integers, and each integer is composed of a unique collection of these building blocks. Comfort with this fact can take your number theoretic intuition a long way.