Number Theory Problems and Results

This is a page where you can learn about number theory and its applications. There are important results and practice problems.

Introduction

Results

Here includes some important results for number theory.

Wilson's Theorem

For a prime number $p$ , we have

$(p-1)! \equiv -1 \pmod p$

Example:

For any prime number $p$ , we have

$\dbinom{2p}{p} \equiv 2 \pmod p$

Proof:

$\dbinom{2p}{p} = \frac{(p+1) \cdot (p+2) \cdot \dots \cdot 2p}{p!}$

$=\frac{2 \cdot (p+1) \cdot (p+2) \cdot \dots \cdot (2p-1)}{(p-1)!}$

Note that by Wilson's Theorem,

$(p+1) \cdot (p+2) \cdot \dots \cdot (2p-1) \equiv (p-1)! \equiv -1 \pmod p$

, so

$- \dbinom{2p}{p} \equiv -2 \pmod p$

so the result follow. $\square$

Format's Little Theorem

For a prime number $p$ and integer $a$ that $p$ does not divide, we have

$a^{p-1} \equiv 1 \pmod p$

Example:

We see that $10^{200} = 100^{100} \equiv 1 \pmod {101}$

Euler's (Totient) Theorem

For relatively prime numbers $m$ and $a$ , we have

$a^{\phi (m)} \equiv 1 \pmod m$

Example:

In 2017 AIME I Problem 14, at the end, we used the Euler Totient Theorem to obtain that $2^{100} \equiv 1 \pmod {125}$

Problems

1. Suppose

$x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}$

Find the remainder when $\min{x}$ is divided by 1000.

2. (Very hard) Let $\pi (n)$ denote the number of primes that is less than or equal to $n$ .

Show that there exist numbers $c_1$ and $c_2$ such that

$c_1 \frac{x}{\log{x}}< \pi (x) < c_2 \frac{x}{\log{x}}$

Solution

Solution 1 to Problem 1(Euler's Totient Theorem)

We first simplify $2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6:$

$2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6=42^4+6 \cdot 30^6=(\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)}$

so

$x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)} \equiv 1 \pmod{5}$

$x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 0 \pmod{6}$

$x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 6 \cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)} \equiv 6 \pmod{7}$ .

where the last step of all 3 congruences hold by the Euler's Totient Theorem. Hence,

$x \equiv 1 \pmod{5}$

$x \equiv 0 \pmod{6}$

$x \equiv 6 \pmod{7}$

Now, you can bash through solving linear congruences, but there is a smarter way. Notice that $5|x-6,6|x-6$ , and $7|x-6$ . Hence, $210|x-6$ , so $x \equiv 6 \pmod{210}$ . With this in mind, we proceed with finding $x \pmod{7!}$ .

Notice that $7!=5040= \text{lcm}(144,210)$ and that $x \equiv 0 \pmod{144}$ . Therefore, we obtain the system of congruences :

$x \equiv 6 \pmod{210}$

$x \equiv 0 \pmod{144}$ .

Solving yields $x \equiv 2\boxed{736} \pmod{7!}$ , and we're done. $\square$ ~Ddk001

Solution 1 to Problem 2

Let $p$ be a prime and $n$ be an integer. Since

$\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}$

, $p$ divides $\dbinom{2n}{n}$ exactly

$\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)$

times.

Therefore, since

$\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1$

, we have

$\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)$

$\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1$

$=\lfloor \log_{p}{(2n)} \rfloor$

so if $p^r | \dbinom{2n}{n}$ , $p^r \le 2n$

Repeated applications of that gives

$\dbinom{2n}{n} \le (2n)^{\pi (2n)}$

Additionally,

$2^n=\prod_{a=1}^n {2} \le \prod_{a=1}^n {\frac{n+a}{a}} = \frac{(n+1) \cdot (n+2) \cdot \dots \cdot 2n}{n!} = \dbinom{2n}{n} \le \sum_{a=0}^{2n} {\dbinom{2n}{a}} = 2^{2n}$