Fun Problems in Number Theory

• Easy Problems
  • 1.1
  • 1.2
• Medium Problems
  • 2.1
    • Three
    • Five
    • Nine
    • Eleven
      • Additional Note
  • 2.2
  • 2.3
  • 2.4
  • 2.5
• Hard Problems
  • Fermat’s Last Theorem
  • Collatz Conjecture
  • Goldbach’s Conjecture

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

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

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

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

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

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

Additional Note

Definition (Palindrome): let the digits of $n \in \pmod{11}$ be of the form $abc...cba$. Then $n$ 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.

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

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

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

$111 \dots 111 = 111 \dots 108 + 3 = 4k+ 3$.

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

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

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.

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

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