Difference between revisions of "Number Theory Problems Collection"

Revision as of 21:26, 1 January 2025

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

$\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. (Very hard) 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}}< \pi (x) < c_2 \frac{x}{\log{x}}$

3. Suppose there is $m$ hats and $n$ 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}$ .

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

Solution 1 to Problem 2

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

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 add that repeatedly, and we have

$$ (Error compiling LaTeX. Unknown error_msg)

@@ Line 63: / Line 63: @@
 Find the remainder when <math>\min{x}</math> is divided by 1000.
 . (Very hard) Let <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.
@@ Line 69: / Line 70: @@
 <cmath>c_1 \frac{x}{\log{x}}< \pi (x) < c_2 \frac{x}{\log{x}}</cmath>
+. 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:
+(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
+(ii) There is at least one bin that contains at least two hats
+Find <math>x \mod 1000</math>.
+. Suppose that there is <math>192</math> rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are <math>2</math> other pegs positioned sufficiently apart. A <math>move</math> is made if
+(i) <math>1</math> 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 <math>x</math> be the minimum possible number <math>moves</math> that can transfer all <math>192</math> rings onto the second peg. Find the remainder when <math>x</math> is divided by <math>1000</math>.
+. Let <math>\overline{ab}</math> be a 2-digit [[positive integer]] satisfying <math>\overline{ab}^2=a! +b!</math>. Find the sum of all possible values of  <math>\overline{ab}</math>.
+. Let <math>F_n</math> denote the <math>n</math>th Fibonacci number. Prove that if <math>n</math> is odd, then all odd prime divisors of <math>F_n</math> are <math>1 \mod{4}</math>.
 ==Solution==

Page

Toolbox

Search

Difference between revisions of "Number Theory Problems Collection"

Revision as of 21:26, 1 January 2025

Contents

Introduction

Results

Wilson's Theorem

Format's Little Theorem

Euler's (Totient) Theorem

Problems

Solution

Solution 1 to Problem 1(Euler's Totient Theorem)

Solution 1 to Problem 2

See Also