Difference between revisions of "Number Theory Problems and Results"

Revision as of 21:02, 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)!}$

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 12: / Line 12: @@
 <cmath>(p-1)! \equiv -1 \pmod p</cmath>
+'''Example:'''
+For any prime number <math>p</math>, we have
+<cmath>2p \choose p \equiv 2 \pmod p</cmath>
+''Proof:''
+<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>
 Format's Little Theorem:
@@ Line 17: / Line 30: @@
 <cmath>a^{p-1} \equiv 1 \pmod p</cmath>
+Euler's (Totient) Theorem
+For relatively prime numbers <math>m</math> and <math>a</math>, we have
+<cmath>a^{\phi (m)} \equiv 1 \pmod m</cmath>
 ==Problems==

Page

Toolbox

Search