Let us consider the sequence $1,2, 3, \ldots , 2002$. Somebody choses $1002$ numbers from the sequence. Prove that there are two of the chosen numbers which are relatively prime (i.e. do not have any common divisors except $1$).

In $\triangle RED, RD =1, \angle DRE = 75^\circ$ and $\angle RED = 45^\circ$. Let $M$ be the midpoint of segment $\overline{RD}$. Point $C$ lies on side $\overline{ED}$ such that $\overline{RC} \perp \overline{EM}$. Extend segment $\overline{DE}$ through $E$ to point $A$ such that $CA = AR$. Then $AE = \tfrac{a-\sqrt{b}}{c},$ where $a$ and $c$ are relatively prime positive integers, and $b$ is a positive integer. Find $a+b+c$.

1) Cells of $8 \times 8$ table contain pairwise distinct positive integers. Each integer is prime or a product of two primes. It is known that for any integer $a$ from the table there exists integer written in the same row or in the same column such that it is not relatively prime with $a$. Find maximum possible number of prime integers in the table. 2) Cells of $2n \times 2n$ table, $n \ge 2,$ contain pairwise distinct positive integers. Each integer is prime or a product of two primes. It is known that for any integer $a$ from the table there exist integers written in the same row and in the same column such that they are not relatively prime with $a$. Find maximum possible number of prime integers in the table.

There are 2010 boxes labeled $B_1,B_2,\dots,B_{2010},$ and $2010n$ balls have been distributed among them, for some positive integer $n.$ You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving [i]exactly[/i] $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?

The function $ f : \mathbb{N} \to \mathbb{Z}$ is defined by $ f(0) \equal{} 2$, $ f(1) \equal{} 503$ and $ f(n \plus{} 2) \equal{} 503f(n \plus{} 1) \minus{} 1996f(n)$ for all $ n \in\mathbb{N}$. Let $ s_1$, $ s_2$, $ \ldots$, $ s_k$ be arbitrary integers not smaller than $ k$, and let $ p(s_i)$ be an arbitrary prime divisor of $ f\left(2^{s_i}\right)$, ($ i \equal{} 1, 2, \ldots, k$). Prove that, for any positive integer $ t$ ($ t\le k$), we have $ 2^t \Big | \sum_{i \equal{} 1}^kp(s_i)$ if and only if $ 2^t | k$.

Let $k$ be a nonzero natural number and $m$ an odd natural number . Prove that there exist a natural number $n$ such that the number $m^n+n^m$ has at least $k$ distinct prime factors.

Let $f: \mathbb{R}\to\mathbb{R}$ be a function such that $(f(x))^{n}$ is a polynomial for every integer $n\geq 2$. Is $f$ also a polynomial?

Let $ (a_{n})_{n\ge 1}$ be a sequence of positive integers satisfying $ (a_{m},a_{n}) = a_{(m,n)}$ (for all $ m,n\in N^ +$). Prove that for any $ n\in N^ + ,\prod_{d|n}{a_{d}^{\mu (\frac {n}{d})}}$ is an integer. where $ d|n$ denotes $ d$ take all positive divisors of $ n.$ Function $ \mu (n)$ is defined as follows: if $ n$ can be divided by square of certain prime number, then $ \mu (1) = 1;\mu (n) = 0$; if $ n$ can be expressed as product of $ k$ different prime numbers, then $ \mu (n) = ( - 1)^k.$

Find the smallest positive integer $ K$ such that every $ K$-element subset of $ \{1,2,...,50 \}$ contains two distinct elements $ a,b$ such that $ a\plus{}b$ divides $ ab$.

Find the number of rational numbers $r$, $0<r<1$, such that when $r$ is written as a fraction in lowest terms, the numerator and denominator have a sum of $1000$.

How many positive integers $n$ are there such that $n!(2n+1)$ and $221$ are relatively prime? $ \textbf{(A)}\ 10 \qquad\textbf{(B)}\ 11 \qquad\textbf{(C)}\ 12 \qquad\textbf{(D)}\ 13 \qquad\textbf{(E)}\ \text{None of the above} $

It is known that subsets $A_1,A_2, \cdots , A_n$ of set $I=\{1,2,\cdots ,101\}$ satisfy the following condition $$\text{For any } i,j \text{ } (1 \leq i < j \leq n) \text{, there exists } a,b \in A_i \cap A_j \text{ so that } (a,b)=1$$ Determine the maximum positive integer $n$. *$(a,b)$ means $\gcd (a,b)$

Let $\phi(n)$ denote $\textit{Euler's phi function}$, the number of integers $1\leq i\leq n$ that are relatively prime to $n$. (For example, $\phi(6)=2$ and $\phi(10)=4$.) Let \[S=\sum_{d|2008}\phi(d),\] in which $d$ ranges through all positive divisors of $2008$, including $1$ and $2008$. Find the remainder when $S$ is divided by $1000$.

A capricious mathematician writes a book with pages numbered from $2$ to $400$. The pages are to be read in the following order. Take the last unread page ($400$), then read (in the usual order) all pages which are not relatively prime to it and which have not been read before. Repeat until all pages are read. So, the order would be $2, 4, 5, ... , 400, 3, 7, 9, ... , 399, ...$. What is the last page to be read?

Let $n \ge 2$ be a positive integer, and let $\sigma(n)$ denote the sum of the positive divisors of $n$. Prove that the $n^{\text{th}}$ smallest positive integer relatively prime to $n$ is at least $\sigma(n)$, and determine for which $n$ equality holds. [i]Proposed by Ashwin Sah[/i]

To each positive integer $ n$ it is assigned a non-negative integer $f(n)$ such that the following conditions are satisfied: (1) $ f(rs) \equal{} f(r)\plus{}f(s)$ (2) $ f(n) \equal{} 0$, if the first digit (from right to left) of $ n$ is 3. (3) $ f(10) \equal{} 0$. Find $f(1985)$. Justify your answer.

Consider positive integers $m <n,p < q$ such that $(m, n) = 1, (p, q) = 1$ and satisfy the condition that if $\frac{m}{n}= tan\alpha$ and $\frac{p}{q} = tan\beta$, then $\alpha + \beta = 45^o$. i) Given $m, n$, find $p, q$. ii) Given $n, q$, find $m, p$. ii) Given $m, q$, find $n, p$.

Let $S$ be the set of points whose coordinates $x,$ $y,$ and $z$ are integers that satisfy $0\le x\le2,$ $0\le y\le3,$ and $0\le z\le4.$ Two distinct points are randomly chosen from $S.$ The probability that the midpoint of the segment they determine also belongs to $S$ is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$. [i]Proposed by Jaroslaw Wroblewski, Poland[/i]

For two positive integers a and b, which are relatively prime, find all integer that can be the great common divisor of $a+b$ and $\frac{a^{2005}+b^{2005}}{a+b}$.

Bob is making partitions of $10$, but he hates even numbers, so he splits $10$ up in a special way. He starts with $10$, and at each step he takes every even number in the partition and replaces it with a random pair of two smaller positive integers that sum to that even integer. For example, $6$ could be replaced with $1+5$, $2+4$, or $3+3$ all with equal probability. He terminates this process when all the numbers in his list are odd. The expected number of integers in his list at the end can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Compute $100m+n$. [i]Proposed by Michael Ren[/i]

Let $S(n)=1\varphi(1)+2\varphi(2) \ldots +n\varphi(n)$, where $\varphi(n)$ is the number of positive integers less than or equal to $n$ that are relatively prime to $n$. (For instance $\varphi(12)=4$ and $\varphi(20)=8$.) Prove that for all $n \geq 2018$, the following inequality holds: $$0.17n^3 \leq S(n) \leq 0.23n^3$$

A pair of integers $ (m,n)$ is called [i]good[/i] if \[ m\mid n^2 \plus{} n \ \text{and} \ n\mid m^2 \plus{} m\] Given 2 positive integers $ a,b > 1$ which are relatively prime, prove that there exists a [i]good[/i] pair $ (m,n)$ with $ a\mid m$ and $ b\mid n$, but $ a\nmid n$ and $ b\nmid m$.

Let $p$ and $q$ be relatively prime positive integers. A subset $S\subseteq \mathbb{N}_0$ is called ideal if $0 \in S$ and, for each element $n \in S$, the integers $n+p$ and $n+q$ belong to $S$. Determine the number of ideal subsets of $\mathbb{N}_0$.

Trapezoid $ABCD$ has sides $AB=92$, $BC=50$, $CD=19$, and $AD=70$, with $AB$ parallel to $CD$. A circle with center $P$ on $AB$ is drawn tangent to $BC$ and $AD$. Given that $AP=\frac mn$, where $m$ and $n$ are relatively prime positive integers, find $m+n$.