[書籍] 104 Number Theory Problems: From the Training of the USA IMO Team

Titu Andreescu, Dorin Andrica, Zuming Feng(2007), 104 Number Theory Problems: From the Training of the USA IMO Team
http://www.amazon.com/104-Number-Theory-Problems-Training/dp/0817645276


Example 1.10. [HMMT 2002]
Find $n$ such that $2\parallel 3^{1024}-1$.

Theorem 1.3b.
For any given integer $m$, there is no polynomial $p(x)$ with integer coefficients such that $p(n)$ is prime for all integers $n$ with $n>m$.

Example 1.12.
Compute gcd$(2002+2,2002^{2}+2,2002^{3}+2,\cdots )$.

Corollary 1.10.
Let $p$ be a prime, and let $k$ be an integer with $1\leq k<p$. Then $p\mid \binom{p}{k}$.

Example 1.15. [Russia 2001]
Let $a$ and $b$ be distinct positive integers such that $ab(a+b)$ is divisible by $a^{2}+ab+b^2$. Prove that $\left | a-b \right |>\sqrt[3]{ab}$.

Example 1.16. [AIME 1988]
Compute the probability that a randomly chosen positive divisor of $10^{99}$ is an integer multiple of $10^{88}$.

Example 1.17.
Determine the number of ordered pairs of positive integers $(a, b)$ such that the least common multiple of $a$ and $b$ is $2^{3}5^{7}11^{13}$.

Example 1.18.
Determine the product of distinct positive integer divisors of $n = 420^4$.

Corollary 1.15.
For any positive integer $n$, $\prod_{d\mid n}^{\; }d=n^{\frac{\tau (n)}{2}}$.

The Number of Divisors $\tau (n)=\sum_{d\mid n}^{\; }1$, The Sum of Divisors $\sigma (n)=\sum_{d\mid n}^{\; }d$.

Corollary 1.16.
For any positive integer $n$, $\tau (n)\leq 2\sqrt{n}$.

Example 1.19.
Find the sum of even positive divisors of $10000$.

Example 1.21. [Russia 2001]
Find all primes $p$ and $q$ such that $p + q =(p − q)^{3}$.

Example 1.22. [Baltic 2001]
Let $a$ be an odd integer. Prove that $a^{2^n} + 2^{2^n}$ and $a^{2^m} + 2^{2^m}$ are relatively prime for all positive integers $n$ and $m$ with $n\neq m$.

Example 1.23.
Determine whether there exist infinitely many even positive integers $k$ such that for every prime $p$ the number $p^2 + k$ is composite.

Residue Classes

Example 1.25. [Romania 2003]
Consider the prime numbers $n_1 < n_2 < \cdots <n_{31}$. Prove that if $30$ divides $n_{1}^{4}+n_{2}^{4}+\cdots +n_{31}^{4}$, then among these numbers one can find three consecutive primes.

Example 1.26.
Let $m$ be an even positive integer. Assume that $\left \{ a_{1},a_{2},\cdots ,a_{m} \right \}$ and $\left \{ b_{1},b_{2},\cdots ,b_{m} \right \}$ are two complete sets of residue classes modulo $m$. Prove that $\left \{ a_{1}+b_{1},a_{2}+b_{2},\cdots ,a_{m}+b_{m} \right \}$ is not a complete set of residue classes.

Theorem 1.26. [Wilson’s Theorem]
For any prime $p$, $(p-1)!\equiv -1\; (\mathbf{mod}\; p)$.

Fermat’s Little Theorem and Euler’s Theorem

Example 1.30.
Let $p\geq 7$ be a prime. Prove that the number  $\underset{p-1\; \mathbf{1's}}{\underbrace{11\cdots 1}}$ is divisible by $p$.

Example 1.31.
Let $p$ be a prime with $p > 5$. Prove that $p^{8}\equiv 1\; (\mathbf{mod}\; 240)$.

Example 1.32.
Prove that for any even positive integer $n$, $n^2−1$ divides $2^{n!}−1$.

Example 1.33. [IMO 2005]
Consider the sequence $a_1, a_2,\cdots$ defined by $a_{n}=2^{n}+3^{n}+6^{n}-1$ for all positive integers $n$. Determine all positive integers that are relatively prime to every term of the sequence.

Example 1.35. [IMO 2003 shortlist]
Determine the smallest positive integer $k$ such that there exist integers $x_1, x_2,\cdots , x_k$ with $x_{1}^{3}+x_{2}^{3}+\cdots +x_{k}^{3}=2002^{2002}$.

Example 1.36. [AIME 2001]
How many positive integer multiples of $1001$ can be expressed in the form $10^j −10^i$ , where $i$ and $j$ are integers and $0\leq i\leq j\leq 99$?

Euler’s Totient Function

Theorem 1.34. [Gauss]
For any positive integer $n$, $\sum_{d\mid n}^{\; }\phi (d)=n$.

Example 1.37.
Let $n$ be a positive integer.
(1) Find the sum of all positive integers less than $n$ and relatively prime to $n$.
(2) Find the sum of all positive integers less than $2n$ and relatively prime to $n$.

Linear Diophantine Equations

Example 1.39.
Let $n$ be a positive integer. Suppose that there are $666$ ordered triples $(x, y, z)$ of positive integers satisfying the equation $x+8y+8z=n$. Find the maximum value of $n$.

Numerical Systems

Example 1.41. [AHSME 1973]
In the following equation, each of the letters represents uniquely a different digit in base ten: $(YM)\cdot (ME)=TTT$. Determine the sum $E + M + T + Y$.

Example 1.42. [AIME 2001]
Find the sum of all positive two-digit integers that are divisible by each of their digits.

Example 1.43. [AMC12A 2002]
Some sets of prime numbers, such as ${7, 83, 421, 659}$, use each of the nine nonzero digits exactly once. What is the smallest possible sum such a set of primes can have?

Example 1.48.
Determine all positive integers $n$ such that $11111_{(n)}$ is a perfect square.

Divisibility Criteria in the Decimal System

Example 1.50. Perfect squares or not?
(1) Determine all positive integers $k$ such that the $k$-digit number $11\cdots 1$ is not a perfect square.
(2) Can a $5$-digit number consisting only of distinct even digits be a perfect square?
(3) Determine whether $\underset{2004}{\underbrace{20\cdots 04}}$ is a perfect square.

Example 1.52.
Determine the number of five-digit positive integers $\overline{abcde}$$(a, b, c, d,$ and $e$ not necessarily distinct) such that the sum of the three-digit
number $\overline{abc}$ and the two-digit number $\overline{de}$ is divisible by 11.

Example 1.53. [USAMO 2003]
$S(n)$ denote the sum of its digits. Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.

Example 1.54. [Russia 1999]
In the decimal expansion of $n$, each digit (except the first digit) is greater than the digit to its left. What is $S(9n)$?

Example 1.55. [Ireland 1996]
Find a positive integer $n$ such that $S(n) =1996S(3n)$.

Example 1.56. 
Determine whether there is any perfect square that ends in $10$ distinct digits.

Example 1.57. [IMO 1976]
When $4444^{4444}$ is written in decimal notation, the sum of its digits is $A$. Let $B$ be the sum of the digits of $A$. Find the sum of the digits of $B$.

Floor Function

Example 1.60. [ARML 2003]
Find the positive integer $n$ such that $\frac{1}{n}$ is closest to $\left \{ \sqrt{123456789} \right \}$.

Example 1.61 [AIME 1997]
Suppose that $a$ is positive, ${a^{−1}} = {a^2}$, and $2 < a^2 < 3$. Find the value of $a^{12} − 144a^{−1}$.

Example 1.62. 
Find all real solutions to the equation $4x^2-40\left \lfloor x \right \rfloor+51=0$.

以上節錄了一些題目，有興趣的可以自行練習。