Difference between revisions of "Number Theory Problems Collection"

 
(6 intermediate revisions by the same user not shown)
Line 64: Line 64:
  
  
2. (Very hard) Let <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.
+
2. 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  
 
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>
+
<cmath>c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}</cmath>
  
  
3. Suppose there is <math>m</math> hats and <math>n</math> bins to put them in, and all objects are assigned a corresponding integer. Suppose there is <math>x</math> ways of putting the hats in the bins such that the following criteria are followed:
+
3. Suppose there is <math>6</math> hats and <math>34</math> bins to put them in, and all objects are assigned a corresponding integer. Suppose there is <math>x</math> ways of putting the hats in the bins such that the following criteria are followed:
 +
 
 
(i) If <math>i<j</math> (where <math>i</math> and <math>j</math> are integers), then hat <math>i</math> is placed in a bin whose number is less than or equal to the number of the bin that hat <math>j</math> is placed in
 
(i) If <math>i<j</math> (where <math>i</math> and <math>j</math> are integers), then hat <math>i</math> is placed in a bin whose number is less than or equal to the number of the bin that hat <math>j</math> is placed in
  
Line 133: Line 134:
 
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>~[[Ddk001]]
 
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>~[[Ddk001]]
  
===Solution 1 to Problem 2===
+
===Solution 1 to Problem 2 (The Proof by Chebyshev)===
  
 
Let <math>p</math> be a prime and <math>n</math> be an integer. Since
 
Let <math>p</math> be a prime and <math>n</math> be an integer. Since
Line 174: Line 175:
  
 
<cmath>\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}</cmath>
 
<cmath>\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}</cmath>
 +
 +
<cmath>\implies \pi (n) \ge \frac{\log{2}}{2} \cdot \frac{n}{\log {n}}</cmath>
  
 
Now, we note also that  
 
Now, we note also that  
Line 187: Line 190:
 
<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>
 
<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>
  
We add that repeatedly, and we have
+
We have
 +
 
 +
<cmath>\log {2n} \cdot \pi (2n)+\log {n} \cdot \pi (n)= \log {2} \cdot \pi (2n) + \log {n} \cdot (\pi (2n) - \pi (n)) \le \log {2} \cdot \pi (2n) + n \cdot \log {4} \le 3n \cdot \log {2}</cmath>
 +
 
 +
since <math>\pi (2n) \le n</math> for <math>n>3</math> (because there is at least a half of even numbers).
 +
 
 +
Repeated addition of that gives
 +
 
 +
<cmath>\pi (2n) = \frac{1}{\log{2n}} \cdot (\log {2n} \cdot \pi (2n)- \log {n} \cdot \pi (n))+(\log {n} \cdot \pi (n)- \log {\frac{n}{2}} \cdot \pi (\frac{n}{2}))+ (\log {\frac{n}{2}} \cdot \pi (\frac{n}{2})- \log {\frac{n}{4}} \cdot \pi (\frac{n}{4}))+ \dots</cmath>
 +
 
 +
<cmath>\le \frac{1}{\log {2n}} \cdot (3n \cdot \log {2}+\frac{3n}{2} \cdot \log {2}+\frac{3n}{4} \cdot \log {2}+ \dots)</cmath>
 +
 
 +
<cmath>= \frac{3n \cdot \log {2}}{\log {2n}} \cdot (1+ \frac{1}{2}+\frac{1}{4} + \dots)</cmath>
 +
 
 +
<cmath>= \frac{6n \cdot \log {2}}{\log {2n}}</cmath>
 +
 
 +
<cmath>\le \frac{\log{64} \cdot n}{\log{n}}</cmath>
 +
 
 +
As we have previously derived,
 +
 
 +
<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>
 +
 
 +
so
 +
 
 +
<cmath>\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) = \frac{\log {x}}{2^{m}} (\pi (\frac{x}{2^m})-\pi (\frac{x}{2^{m+1}})) + \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) </cmath>
 +
 
 +
<cmath>\le \frac{\log {x}}{2^{m}} \cdot \log {4} \cdot \frac{\frac{x}{2^{m+1}}}{\log {\frac{x}{2^{m+1}}}} + \frac{\log {x}}{2^{m+1}} \cdot \frac{\log{64} \cdot \frac{x}{2^{m+2}}}{\log{\frac{x}{2^{m+2}}}}</cmath>
  
IN PROGRESS
+
<cmath>\le \frac{\log {x} \cdot \log {4}}{2^{2m+1}} \cdot (\frac{x}{\log {\frac{x}{2^{m+1}}}}+\frac{x}{\log {\frac{x}{2^{m+2}}}})</cmath>
 +
 
 +
<cmath>\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}</cmath>
 +
 
 +
<cmath>\le \log {4} \cdot \frac{x}{2^{m}}</cmath>
 +
 
 +
. (The last step I do not know why. If you can figure out the reason, please add the intermediate steps for it)
 +
 
 +
If we add that, we get a telescoping sum, so we have
 +
 
 +
<cmath>\log{x} \cdot \pi (x)  = \sum_{m=0}^{v} (\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}))</cmath>
 +
 
 +
<cmath>\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}</cmath>
 +
 
 +
<cmath>\le \log{4} \cdot x</cmath>
 +
 
 +
<cmath>\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath>
 +
 
 +
where <math>v</math> is the greatest integer such a that <math>2^v | x</math>.
 +
 
 +
Collecting our results, we see that
 +
 
 +
<cmath>\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath>
 +
 
 +
We have thus found the desired <math>c_1</math> and <math>c_2</math>. ~[[Ddk001]] <math>\blacksquare</math>
 +
 
 +
Note: This was actually the same method of proof given by Chebyshev.
  
 
===Solution 1 to Problem 3===
 
===Solution 1 to Problem 3===
 +
 +
We see that this is equivalent to asking "What is the number of ordered 6-tuples <math>(x_1,x_2, \dots , x_6)</math> such that <math>x_1 \le x_2 \le x_3 \le \dots \le  x_6 \le 34</math> and that <math>x_1 < x_2 < x_3 < \dots <x_6</math> do NOT hold?". <math>x_i</math> correspond to the number of the bin that hat <math>i</math> is placed in. By the [[Nested Sum Theorem]], there is <math>\dbinom{39}{6}</math> ways of putting the hats in the bins without following the second criteria. We subtract the ways that do not follow the second criteria, i.e. the ordered 6-tuples such that
 +
 +
<cmath>1 \le x_1 < x_2 < x_3 < \dots <x_6 \le 34</cmath>
 +
 +
DO hold. There is obviously <math>\dbinom{34}{6}</math> such ways. Thus, <math>x=\dbinom{39}{6} - \dbinom{34}{6}</math>.
 +
 +
We have
 +
 +
<cmath>x=\dbinom{39}{6} - \dbinom{34}{6}</cmath>
 +
 +
<cmath>= \frac{39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 \cdot 34 - 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{720}</cmath>
 +
 +
<cmath>= 13 \cdot 19 \cdot 37 \cdot 3 \cdot 7 \cdot 17 - 34 \cdot 11 \cdot 2 \cdot 31 \cdot 2 \cdot 29</cmath>
 +
 +
<cmath>\equiv 623 -904</cmath>
 +
 +
<cmath>= \boxed{719} \pmod {1000}</cmath>
 +
 +
<math>\square</math> ~ [[Ddk001]]
  
 
===Solution 1 to Problem 4===
 
===Solution 1 to Problem 4===
Line 505: Line 580:
 
<cmath>\equiv \boxed{689} \pmod {1000}</cmath>
 
<cmath>\equiv \boxed{689} \pmod {1000}</cmath>
  
This is our answer. <math>\square</math>. ~
+
This is our answer. <math>\square</math>. ~ [[Ddk001]]
  
 
==See Also==
 
==See Also==
  
 
* [[Problem Collection]]
 
* [[Problem Collection]]

Latest revision as of 20:22, 7 January 2025

This is a page where you can learn about number theory and its applications. There are important results and practice problems.


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

\[\dbinom{2p}{p} \equiv 2 \pmod p\]

Proof:

\[\dbinom{2p}{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

\[- \dbinom{2p}{p} \equiv -2 \pmod p\]

so the result 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\]

Example:

We see that $10^{200} = 100^{100} \equiv 1 \pmod {101}$

Euler's (Totient) Theorem

For relatively prime numbers $m$ and $a$, we have

\[a^{\phi (m)} \equiv 1 \pmod m\]

Example:

In 2017 AIME I Problem 14, at the end, we used the Euler Totient Theorem to obtain that $2^{100} \equiv 1 \pmod {125}$

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.


2. Let $\pi (n)$ denote the number of primes that is less than or equal to $n$.

Show that there exist numbers $c_1$ and $c_2$ such that

\[c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}\]


3. Suppose there is $6$ hats and $34$ bins to put them in, and all objects are assigned a corresponding integer. Suppose there is $x$ ways of putting the hats in the bins such that the following criteria are followed:

(i) If $i<j$ (where $i$ and $j$ are integers), then hat $i$ is placed in a bin whose number is less than or equal to the number of the bin that hat $j$ is placed in

(ii) There is at least one bin that contains at least two hats

Find $x \mod 1000$.


4. Suppose that there is $192$ rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are $2$ other pegs positioned sufficiently apart. A $move$ is made if

(i) $1$ ring changed position (i.e., that ring is transferred from one peg to another)

(ii) No bigger rings are on top of smaller rings.

Then, let $x$ be the minimum possible number $moves$ that can transfer all $192$ rings onto the second peg. Find the remainder when $x$ is divided by $1000$.


5. Let $\overline{ab}$ be a 2-digit positive integer satisfying $\overline{ab}^2=a! +b!$. Find the sum of all possible values of $\overline{ab}$.


6. Let $F_n$ denote the $n$th Fibonacci number. Prove that if $n$ is odd, then all odd prime divisors of $F_n$ are $1 \mod{4}$.

7. Let $x$ be the remainder when

\[106! + (53!)^2\]

is divided by $107 \cdot 53^3$. Find the remainder when $x$ is divided by $1000$.

Solutions

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

Solution 1 to Problem 2 (The Proof by Chebyshev)

Let $p$ be a prime and $n$ be an integer. Since

\[\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}\]

, $p$ divides $\dbinom{2n}{n}$ exactly

\[\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)\]

times.

Therefore, since

\[\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1\]

, we have

\[\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)\]

\[\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1\]

\[=\lfloor \log_{p}{(2n)} \rfloor\]

so if $p^r | \dbinom{2n}{n}$, $p^r \le 2n$

Repeated applications of that gives

\[\dbinom{2n}{n} \le (2n)^{\pi (2n)}\]

Additionally,

\[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}\]

so

\[2^n \le (2n)^{\pi (2n)}\]

\[\implies n \cdot \log {2} \le \pi (2n) \cdot \log {2n}\]

\[\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}\]

\[\implies \pi (n) \ge \frac{\log{2}}{2} \cdot \frac{n}{\log {n}}\]

Now, we note also that

\[\prod_{\text{p is a prime from n to 2n}} {p} | \dbinom{2n}{n}\]

so

\[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}\]

Thus,

\[\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}\]

We have

\[\log {2n} \cdot \pi (2n)+\log {n} \cdot \pi (n)= \log {2} \cdot \pi (2n) + \log {n} \cdot (\pi (2n) - \pi (n)) \le \log {2} \cdot \pi (2n) + n \cdot \log {4} \le 3n \cdot \log {2}\]

since $\pi (2n) \le n$ for $n>3$ (because there is at least a half of even numbers).

Repeated addition of that gives

\[\pi (2n) = \frac{1}{\log{2n}} \cdot (\log {2n} \cdot \pi (2n)- \log {n} \cdot \pi (n))+(\log {n} \cdot \pi (n)- \log {\frac{n}{2}} \cdot \pi (\frac{n}{2}))+ (\log {\frac{n}{2}} \cdot \pi (\frac{n}{2})- \log {\frac{n}{4}} \cdot \pi (\frac{n}{4}))+ \dots\]

\[\le \frac{1}{\log {2n}} \cdot (3n \cdot \log {2}+\frac{3n}{2} \cdot \log {2}+\frac{3n}{4} \cdot \log {2}+ \dots)\]

\[= \frac{3n \cdot \log {2}}{\log {2n}} \cdot (1+ \frac{1}{2}+\frac{1}{4} + \dots)\]

\[= \frac{6n \cdot \log {2}}{\log {2n}}\]

\[\le \frac{\log{64} \cdot n}{\log{n}}\]

As we have previously derived,

\[\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}\]

so

\[\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) = \frac{\log {x}}{2^{m}} (\pi (\frac{x}{2^m})-\pi (\frac{x}{2^{m+1}})) + \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}})\]

\[\le \frac{\log {x}}{2^{m}} \cdot \log {4} \cdot \frac{\frac{x}{2^{m+1}}}{\log {\frac{x}{2^{m+1}}}} + \frac{\log {x}}{2^{m+1}} \cdot \frac{\log{64} \cdot \frac{x}{2^{m+2}}}{\log{\frac{x}{2^{m+2}}}}\]

\[\le \frac{\log {x} \cdot \log {4}}{2^{2m+1}} \cdot (\frac{x}{\log {\frac{x}{2^{m+1}}}}+\frac{x}{\log {\frac{x}{2^{m+2}}}})\]

\[\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}\]

\[\le \log {4} \cdot \frac{x}{2^{m}}\]

. (The last step I do not know why. If you can figure out the reason, please add the intermediate steps for it)

If we add that, we get a telescoping sum, so we have

\[\log{x} \cdot \pi (x)  = \sum_{m=0}^{v} (\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}))\]

\[\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}\]

\[\le \log{4} \cdot x\]

\[\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}\]

where $v$ is the greatest integer such a that $2^v | x$.

Collecting our results, we see that

\[\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}\]

We have thus found the desired $c_1$ and $c_2$. ~Ddk001 $\blacksquare$

Note: This was actually the same method of proof given by Chebyshev.

Solution 1 to Problem 3

We see that this is equivalent to asking "What is the number of ordered 6-tuples $(x_1,x_2, \dots , x_6)$ such that $x_1 \le x_2 \le x_3 \le \dots \le  x_6 \le 34$ and that $x_1 < x_2 < x_3 < \dots <x_6$ do NOT hold?". $x_i$ correspond to the number of the bin that hat $i$ is placed in. By the Nested Sum Theorem, there is $\dbinom{39}{6}$ ways of putting the hats in the bins without following the second criteria. We subtract the ways that do not follow the second criteria, i.e. the ordered 6-tuples such that

\[1 \le x_1 < x_2 < x_3 < \dots <x_6 \le 34\]

DO hold. There is obviously $\dbinom{34}{6}$ such ways. Thus, $x=\dbinom{39}{6} - \dbinom{34}{6}$.

We have

\[x=\dbinom{39}{6} - \dbinom{34}{6}\]

\[= \frac{39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 \cdot 34 - 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{720}\]

\[= 13 \cdot 19 \cdot 37 \cdot 3 \cdot 7 \cdot 17 - 34 \cdot 11 \cdot 2 \cdot 31 \cdot 2 \cdot 29\]

\[\equiv 623 -904\]

\[= \boxed{719} \pmod {1000}\]

$\square$ ~ Ddk001

Solution 1 to Problem 4

Let $M_n$ be the minimum possible number $moves$ that can transfer $n$ rings onto the second peg. To build the recursion, we consider what is the minimum possible number $moves$ that can transfer $n+1$ rings onto the second peg. If we use only legal $moves$, then $n+1$ will be smaller on the top, bigger on the bottom. Hence, the largest ring have to be at the bottom of the second peg, or the largest peg will have nowhere to go. In order for the largest ring to be at the bottom, we must first move the top $n$ rings to the third peg using $M_n$ $moves$, then place the largest ring onto the bottom of the second peg using $1$ $move$, and then get all the rings from the third peg on top of the largest ring using another $M_n$ $moves$. This gives a total of $2M_n+1$, hence we have $M_{n+1}=2M_{n}+1$. Obviously, $M_1=1$. We claim that $M_n=2^n-1$. This is definitely the case for $n=1$. If this is true for $n$, then

\[M_{n+1}=2M_{n}+1=2(2^n-1)+1=2^{n+1}-1\]

so this is true for $n+1$. Therefore, by induction, $M_n=2^n-1$ is true for all $n$. Now, $x=M_{192}=2^{192}-1$. Therefore, we see that

\[x+1 \equiv 0 \pmod{8}\].

But the $\text{mod 125}$ part is trickier. Notice that by the Euler's Totient Theorem,

\[2^{\phi (125)}=2^{100} \equiv 1 \pmod{125} \implies 2^{200} \equiv 1 \pmod{125}\]

so $x+1=\frac{2^{200}}{256}$ is equivalent to the inverse of $256$ in $\text{mod 125}$, which is equivalent to the inverse of $6$ in $\text{mod 125}$, which, by inspection, is simply $21$. Hence,

\[x+1 \equiv 0 \pmod{8}\]

\[x+1 \equiv 21 \pmod{125}\]

, so by the Chinese Remainder Theorem, $x+1 \equiv 896 \pmod{1000} \implies x \equiv \boxed{895} \pmod{1000}$. $\square$

~Ddk001

Solutions to Problem 5

Solution 1 to Problem 5 (Tedious Casework)

Case 1: $a>b$

In this case, we have

\[\overline{ab}^2=a! +b!=(1+a \cdot (a-1) \cdot \dots \cdot (b+1)) \cdot b! \implies b!|\overline{ab}^2=(10a+b)^2\].

If $b \ge 5$, we must have

\[10|b!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0\]

, but this contradicts the original assumption of $b \ge 5$, so hence we must have $b \le 4$.

With this in mind, we consider the unit digit of $\overline{ab}^2$.

Subcase 1.1: $a>b=1$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+1)^2-1 \equiv 0 \pmod{10} \implies 10|a! \implies a \ge 5\].

There is no apparent contradiction here, so we leave this as it is.

Subcase 1.2: $a>b=2$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+2)^2-2 \equiv 2 \pmod{10} \implies a! \equiv 2 \pmod{10} \implies a=2\].

This contradicts with the fact that $a>b$, so this is impossible.

Subcase 1.3: $a>b=3$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+3)^2-6 \equiv 3 \pmod{10}\].

However, this is impossible for all $a$.

Subcase 1.4: $a>b=4$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+4)^2-24 \equiv 2 \pmod{10}\].

Again, this yields $a=2$, which, again, contradicts $a>b$. $\square$

Hence, we must have $b=1$.

Now, with $b$ determined by modular arithmetic, we actually plug in the values.

To simplify future calculations, note that

\[a!=\overline{ab}^2-b!=(10a+1)^2-1=100a^2+20a=10a(10a+2)\].

For $a=5$, this does not hold.

For $a=6$, this does not hold.

For $a=7$, this does hold. Hence, $(a,b)=(7,1)$ is a solution.

For $a=8$, this does not hold.

For $a=9$, this does not hold.

Hence, there is no positive integers $a$ and $b$ between $1$ and $9$ inclusive such that $a!+b!=\overline{ab}^2$.

Case 2: $a=b$

For this case, we must have

\[(11a)^2=\overline{ab}^2=a!+b!=2a! \implies 11|a!\]

which is impossible if a is a integer and $1 \le a \le 9$.

Case 3: $a<b$

In this case, we have

\[\overline{ab}^2=a! +b!=(1+b \cdot (b-1) \cdot \dots \cdot (a+1)) \cdot a! \implies a!|\overline{ab}^2=(10a+b)^2\].

If $a \ge 5$, we must have

\[10|a!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0 \implies 10|a!+b!\]

which is impossible since $10|a!$ and $b!=1$.

Hence, $a \le 4$.

Subcase 3.1: $b>a=1$

\[(10+b)^2=1+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.2: $b>a=2$

\[(20+b)^2=2+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.3: $b>a=3$

\[(30+b)^2=3+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.4: $b>a=4$

\[(40+b)^2=4+b!\]

Testing cases, we can see that there is no such $b$.

We see that $(a,b)=(7,1) \implies a+b=\boxed{008}$. $\blacksquare$ ~Ddk001

Solution 2 to Problem 5 (Official)

$\overline{ab}^2=a! +b!$ cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between $100(10^{2})$ and $9801(99^{2})$.

This means both $a$ and $b$ are less than or equal to 7 as any $factorial$ greater than 7! exceeds 9999.

Now at least one of $a$ or $b$ must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100 also, both $a$ and $b$ can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.

Hence, one of $a$ and $b$ is greater than or equal to 5 and the other is less than 5. this means the unit digit of RHS is the unit digit of a factorial which is less than 5.

Hence unit digit of RHS is 0,1,2, 6 or 4. 0,2,4 and 6 are rejected as follows:-

1. 2 can't be the unit digit of a perfect square.

2. If 6 is the unit digit of OF LHS this means one of the numbers is 3( as only 3! has the unit digit 6) and also this would mean that $b$ is either 4 or 6. This directly means that 36 and 34 are the only cases to be tested. 34 can't be as both the digits are less than 5 and 36 clearly doesn't satisfy

3. If 0 is the unit digit of LHS then 50 60 70 are the only cases (as one of the digits is greater than or equal to 5) that don't satisfy

4. If 4 is the unit digit of LHS this means one of the numbers is 4( as only 4! has the unit digit 4) and also this would mean that $b$ is either 2 or 8. This directly means that 42 and 48 are the only cases to be tested. 42 can't be as both the digits are less than 5 and 48 can't also as one of the digits is 8

Hence, the unit digit of LHS must be 1 for which $b$=1 or 9(rejected). This means 51 61 and 71 are the only cases to be tried now which is really very easy to calculate and get 71 as the only possible solution to the problem and

thus, our answer is 7+1=$\boxed{008}$.~ SANSGANKRSNGUPTA

Solution 3 to Problem 5 (Official and Fastest)

$\overline{ab}^2=a! +b!$ cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between $100(10^{2})$ and $9801(99^{2})$.

This means both $a$ and $b$ are less than or equal to 7 as any $factorial$ greater than 7! exceeds 9999.

Now at least one of $a$ or $b$ must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100 also, both $a$ and $b$ can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.

Hence, one of $a$ and $b$ is greater than or equal to 5 and the other is less than 5. Also, RHS is a perfect square, so it must be 0 or 1 $(mod 4)$

Hence the number less than 5 can be either 1 or 4 because 2! and 3! are 2 $(mod 4)$

If it is 4, then the unit digit of RHS is 4 meaning $b$ is either 2 or 8 both of which aren't possible as 8>7 and the number less than 5 is 4 not 2.

If it is 1 then the unit digit of RHS is 1 implying $b$ is either 9(rejected 9>7) or 1. This means $b$ is 1, this means 51 61 and 71 are the only cases to be tried

which is very easy to calculate and get 71 as the only possible solution to the problem and

thus, our answer is 7+1=$\boxed{008}$.~ SANSGANKRSNGUPTA

Solution 1 to Problem 6 (Short and elegant)

Let $n=2k+1$ for some nonnegative integer $k$. Then $F_n=F_{2k+1}=(F_k)^2+(F_{k+1})^2$. Since $F_k$ and $F_{k+1}$ are relatively prime, we are done.

Solution by Yiyj1 (talk) 23:48, 3 December 2024 (EST)


Solutions to Problem 7

Solution 1 to Problem 7

We note that

\[(53!)^2\]

\[=1 \cdot 2 \cdot \dots \cdot 53 \cdot (53 \cdot 52 \cdot \dots \cdot 1)\]

\[=1 \cdot 2 \cdot \dots \cdot 53 \cdot [53 \cdot 52 \cdot \dots \cdot 1 \cdot (-1)^{53}] \cdot (-1)\]

\[=1 \cdot 2 \cdot \dots \cdot 53 \cdot [(-53) \cdot (-52) \cdot \dots \cdot (-1)] \cdot (-1)\]

\[\equiv 1 \cdot 2 \cdot \dots \cdot 53 \cdot [(107-53) \cdot (107-52) \cdot \dots \cdot (107-1)] \cdot (-1)\]

\[= 1 \cdot 2 \cdot \dots \cdot 53 \cdot 54 \cdot 55 \cdot \dots \cdot 106 \cdot (-1)\]

\[= -106!\]

\[\equiv 1 \pmod {107}\]

where the last step follows from Wilson's Theorem.

Now, applying Wilson's Theorem again implies $106! \equiv 1 \pmod {107}$, so

\[106! + (53!)^2 \equiv 0 \pmod {107}\]

We see that

\[(52!)^2 \equiv (-1)^2\]

\[= 1 \pmod {53}\]

by Wilson's Theorem, so

\[(53!)^2 = 53^2 (52!)^2\]

\[\equiv 53^2 \pmod {53^3}\]

Somewhat similarly,

\[\frac{106!}{53^2} = \dbinom{106}{53} \cdot (52!)^2\]

\[\equiv 2 \pmod {53}\]

since $\binom{2p}{p} \equiv 2 \pmod p$ when $p$ is a prime. (Proof here) Thus,

\[106!= \frac{106!}{53^2} \cdot 53^2\]

\[\equiv 2 \cdot 53^2 \pmod {53^3}\]

so

\[106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}\]

We obtain the following linear system of congruences:

\[106! + (53!)^2 \equiv 0 \pmod {107}\]

\[106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}\]

By the Chinese Remainder Theorem,

\[106!+(53!)^2 \equiv 3 \cdot 53^2 \cdot 107 \cdot y \pmod {107 \cdot 53^3}\]

where $y$ is an integer such that

\[107y \equiv 1 \pmod {53^3}\]

(i.e. $y$ is an inverse of $107$ modulo $53^3$).

Seeing a power of a prime as modulus reminds us of Hensel's Lemma for solving polynomial congruences. Let \[f(y)=107y-1\]. We wish to solve $f(y) \equiv 0 \pmod {53^3}$. Obviously, $107 \equiv 1 \pmod {53}$, so $f(1) \equiv 0 \pmod {53}$. By Hensel's Lemma, there exists a unique integer $t \in [0,53)$ such that $f(53t+1) \equiv 0 \pmod {53^2}$, and $t$ is given by

\[t=- \bar{f'(1)} \cdot (\frac{f(1)}{53})\]

where $\bar{f'(1)}$ denotes the inverse of $f'(1)$ modulo $53$ (just $53$, not $53$ to any power). Again, $107 \equiv 1 \pmod {53}$, so since $f'(1) =107$, $\bar{f'(1)}=1$, so

\[t= -1 \cdot \frac{106}{53}\]

\[=-2\]

Therefore, we see that $f(-105) \equiv 0 \pmod {53^2}$. We preform another lift. Again, there exists unique integer $t \in [0,53)$ such that $f(-105+53^2 \cdot t) \equiv 0 \pmod {53^3}$, given by

\[t = - \bar{f'(-105)} \cdot (\frac{f(-105)}{53^2})\]

$f'(-105)$ is also $107$, so $\bar{f'(-105)} = 1$. We have $f(-105)= -105 \cdot 107 -1=-106^2= (-4) \cdot 53^2$, so

\[t = -1 \cdot (\frac{(-4) \cdot 53^2}{53^2}\]

\[=4\]

Therefore, $f(4 \cdot 53^2-105) \equiv 0 \pmod {53^3}$. We can thus set $y=4 \cdot 53^2-105$, so that

\[x \equiv 106!+(53!)^2\]

\[\equiv 3 \cdot 53^2 \cdot 107 \cdot y\]

\[= 3 \cdot 53^2 \cdot 107 \cdot (4 \cdot 53^2-105)\]

\[=12 \cdot 53^4 \cdot 107 - 315 \cdot 53^2 \cdot 107\]

\[\equiv - 315 \cdot 53^2 \cdot 107 \pmod {107 \cdot 53^3}\]

Thus,

\[x=53^3 \cdot 107 \cdot k - 315 \cdot 53^2 \cdot 107\]

\[= (53k-315) \cdot 53^2 \cdot 107\]

for some integer $k$. Since $0 \le x < 53^3 \cdot 107$ (since it is a remainder), $0 \le 53k-315 < 53 \implies k=6$. Therefore,

\[x=3 \cdot 53^2 \cdot 107\]

A simple calculation shows $53^2=2809$, so

\[x \equiv 3 \cdot 809 \cdot 107\]

\[\equiv \boxed{689} \pmod {1000}\]

This is our answer. $\square$. ~ Ddk001

See Also