|
|
| (23 intermediate revisions by the same user not shown) |
| 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==
| |
| − | | |
| − | ==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.
| |
| − | | |
| − | ==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
| |
| − | | |
| − | ==See Also==
| |
| − | | |
| − | * [[Problem Collection]]
| |
