Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Number Theory Problems and Results"

(Created Page)
 
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 where you can learn about number theory and its applications. There are important results and practice problems.
 +
 +
==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 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

Revision as of 20:26, 28 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

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 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Number_Theory_Problems_and_Results&oldid=238220"