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!}<cmath>

</cmath>=\frac{2 \cdot (p+1) \cdot (p+2) \cdot \dots \cdot (2p-1)}{(p-1)!}<cmath>

Note that by Wilson's Theorem,

</cmath>(p+1) \cdot (p+2) \cdot \dots \cdot (2p-1) \equiv (p-1)! \equiv -1 \pmod p<cmath>

, so

</cmath>- \dbinom{2p}{p} \equiv -2 \pmod p$ (Error compiling LaTeX. Unknown error_msg) $so the results 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$

Euler's (Totient) Theorem

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

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

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.

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!}$ .