|
|
| Line 1: |
Line 1: |
| − | This is a page where you can learn about number theory and its applications. There are important results and practice problems. | + | This is a page that was deemed obsolete. The contents were moved to a new webpage. |
| − | | |
| − | ==Introduction==
| |
| − | | |
| − | ==Results==
| |
| − | | |
| − | Here includes some important results for number theory.
| |
| − | | |
| − | ===Wilson's Theorem===
| |
| − | | |
| − | For a prime number <math>p</math>, we have
| |
| − | | |
| − | <cmath>(p-1)! \equiv -1 \pmod p</cmath>
| |
| − | | |
| − | | |
| − | '''Example:'''
| |
| − | | |
| − | For any prime number <math>p</math>, we have
| |
| − | | |
| − | <cmath>\dbinom{2p}{p} \equiv 2 \pmod p</cmath>
| |
| − | | |
| − | ''Proof:''
| |
| − | | |
| − | <cmath>\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</cmath>
| |
| − | | |
| − | so the result follow. <math>\square</math>
| |
| − | | |
| − | ===Format's Little Theorem===
| |
| − | | |
| − | For a prime number <math>p</math> and integer <math>a</math> that <math>p</math> does not divide, we have
| |
| − | | |
| − | <cmath>a^{p-1} \equiv 1 \pmod p</cmath>
| |
| − | | |
| − | '''Example:'''
| |
| − | | |
| − | We see that <math>10^{200} = 100^{100} \equiv 1 \pmod {101}</math>
| |
| − | | |
| − | ===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>
| |
| − | | |
| − | '''Example:'''
| |
| − | | |
| − | In [[2017 AIME I Problems/Problem 14|2017 AIME I Problem 14]], at the end, we used the Euler Totient Theorem to obtain that <math>2^{100} \equiv 1 \pmod {125}</math>
| |
| − | | |
| − | ==Problems==
| |
| − | | |
| − | 1. Suppose
| |
| − | | |
| − | <cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath>
| |
| − | | |
| − | Find the remainder when <math>\min{x}</math> is divided by 1000.
| |
| − | | |
| − | 2. (Very hard) Let <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.
| |
| − | | |
| − | Show that there exist numbers <math>c_1</math> and <math>c_2</math> such that
| |
| − | | |
| − | <cmath>c_1 \frac{x}{\log{x}}< \pi (x) < c_2 \frac{x}{\log{x}}</cmath>
| |
| − | | |
| − | ==Solution==
| |
| − | | |
| − | ===Solution 1 to Problem 1(Euler's Totient Theorem)===
| |
| − | | |
| − | We first simplify <math>2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6:</math>
| |
| − | | |
| − | <cmath>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)}</cmath>
| |
| − | | |
| − | so
| |
| − | | |
| − | <cmath>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}</cmath>
| |
| − | | |
| − | <cmath>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}</cmath>
| |
| − | | |
| − | <cmath>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}</cmath>.
| |
| − | | |
| − | where the last step of all 3 congruences hold by the [[Euler's Totient Theorem]]. Hence,
| |
| − | | |
| − | <cmath>x \equiv 1 \pmod{5}</cmath>
| |
| − | | |
| − | <cmath>x \equiv 0 \pmod{6}</cmath>
| |
| − | | |
| − | <cmath>x \equiv 6 \pmod{7}</cmath>
| |
| − | | |
| − | Now, you can bash through solving linear congruences, but there is a smarter way. Notice that <math>5|x-6,6|x-6</math>, and <math>7|x-6</math>. Hence, <math>210|x-6</math>, so <math>x \equiv 6 \pmod{210}</math>. With this in mind, we proceed with finding <math>x \pmod{7!}</math>.
| |
| − | | |
| − | Notice that <math>7!=5040= \text{lcm}(144,210)</math> and that <math>x \equiv 0 \pmod{144}</math>. Therefore, we obtain the system of congruences :
| |
| − | | |
| − | <cmath>x \equiv 6 \pmod{210}</cmath>
| |
| − | | |
| − | <cmath>x \equiv 0 \pmod{144}</cmath>.
| |
| − | | |
| − | Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>~[[Ddk001]]
| |
| − | | |
| − | ===Solution 1 to Problem 2===
| |
| − | | |
| − | Let <math>p</math> be a prime and <math>n</math> be an integer. Since
| |
| − | | |
| − | <cmath>\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}</cmath>
| |
| − | | |
| − | , <math>p</math> divides <math>\dbinom{2n}{n}</math> exactly
| |
| − | | |
| − | <cmath>\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)</cmath>
| |
| − | | |
| − | times.
| |
| − | | |
| − | Therefore, since
| |
| − | | |
| − | <cmath>\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1</cmath>
| |
| − | | |
| − | , we have
| |
| − | | |
| − | <cmath>\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)</cmath>
| |
| − | | |
| − | <cmath>\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1</cmath>
| |
| − | | |
| − | <cmath>=\lfloor \log_{p}{(2n)} \rfloor</cmath>
| |
| − | | |
| − | so if <math>p^r | \dbinom{2n}{n}</math>, <math>p^r \le 2n</math>
| |
| − | | |
| − | Repeated applications of that gives
| |
| − | | |
| − | <cmath>\dbinom{2n}{n} \le (2n)^{\pi (2n)}</cmath>
| |
| − | | |
| − | Additionally,
| |
| − | | |
| − | <cmath>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}</cmath>
| |
| − | | |
| − | so
| |
| − | | |
| − | <cmath>2^n \le (2n)^{\pi (2n)}</cmath>
| |
| − | | |
| − | <cmath>\implies n \cdot \log {2} \le \pi (2n) \cdot \log {2n}</cmath>
| |
| − | | |
| − | <cmath>\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}</cmath>
| |
| − | | |
| − | Now, we note also that
| |
| − | | |
| − | <cmath>\prod_{\text{p is a prime from n to 2n}} {p} | \dbinom{2n}{n}</cmath>
| |
| − | | |
| − | so
| |
| − | | |
| − | <cmath>n^{\pi (2n) - \pi (n)}=\prod_{\text{p is a prime from n to 2n}} n < \prod_{\text{p is a prime from n to 2n}} p \le \dbinom{2n}{n} \le 2^{2n}</cmath>
| |
| − | | |
| − | Thus,
| |
| − | | |
| − | <cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>
| |
| − | | |
| − | We add that repeatedly, and we have
| |
| − | | |
| − | <math></math>
| |
| − | | |
| − | ==See Also==
| |
| − | | |
| − | * [[Problem Collection]]
| |
