Difference between revisions of "Number Theory Problems and Results"

Revision as of 21:07, 30 December 2024

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

$2p \choose p \equiv 2 \pmod p$

Proof:

$(2p \choose 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

$- 2p \choose p \equiv -2 \pmod p$

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

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

@@ Line 7: / Line 7: @@
 Here includes some important results for number theory.
-===Wilson's Theorem====
+===Wilson's Theorem===
 For a prime number <math>p</math>, we have
@@ Line 22: / Line 22: @@
 ''Proof:''
-<cmath>2p \choose p = \frac{(p+1) \cdot (p+2) \cdot \dots \cdot 2p}{p!}</cmath>
+<cmath>(2p \choose 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>
@@ Line 35: / Line 35: @@
 so the results follow. <math>\square</math>
 ===Format's Little Theorem===

Page

Toolbox

Search