For every positive integer $ n$, let $ \phi(n)$ denotes the number of positive integers less than $ n$ that is relatively prime to $ n$ and $ \tau(n)$ denote the sum of all positive divisors of $ n$. Let $ n$ be a positive integer such that $ \phi(n)|n\minus{}1$ and that $ n$ is not a prime number. Prove that $ \tau(n)>2009$.

Let define $P_{n}(x)=x^{n-1}+x^{n-2}+x^{n-3}+ \dots +x+1$ for every positive integer $n$. Prove that for every positive integer $a$ one can find a positive integer $n$ and polynomials $R(x)$ and $Q(x)$ with integer coefficients such that \[P_{n}(x)= [1+ax+x^{2}R(x)] Q(x).\]

[i]The Game.[/i] Eric and Greg are watching their new favorite TV show, [i]The Price is Right[/i]. Bob Barker recently raised the intellectual level of his program, and he begins the latest installment with bidding on following question: How many Carmichael numbers are there less than $100,000$? Each team is to list one nonnegative integer not greater than $100,000$. Let $X$ denote the answer to Bob’s question. The teams listing $N$, a maximal bid (of those submitted) not greater than $X$, will receive $N$ points, and all other teams will neither receive nor lose points. (A Carmichael number is an odd composite integer $n$ such that $n$ divides $a^{n-1}-1$ for all integers $a$ relatively prime to $n$ with $1<a<n$.)

How many positive integers less that $200$ are relatively prime to either $15$ or $24$?

A positive number $\dfrac{m}{n}$ has the property that it is equal to the ratio of $7$ plus the number’s reciprocal and $65$ minus the number’s reciprocal. Given that $m$ and $n$ are relatively prime positive integers, find $2m + n$.

Prove that between every $27$ different positive integers , less than $100$, there exist some two which are[color=red] NOT [/color]relative prime. [u]babis[/u]

Let $h_n$ and $k_n$ be the unique relatively prime positive integers such that \[\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{h_n}{k_n}.\] Let $L_n$ denote the least common multiple of the numbers $1, 2, 3,\cdots, n$. For how many integers $n$ with $1 \le n \le 22$ is $k_n<L_n$? $\textbf{(A)} ~0 \qquad\textbf{(B)} ~3 \qquad\textbf{(C)} ~7 \qquad\textbf{(D)} ~8 \qquad\textbf{(E)} ~10 $

3. Show that there do not exist positive integers $a$, $b$, $c$ and $d$, pairwise co-prime, such that $ab+cd$, $ac+bd$ and $ad+bc$ are odd divisors of the number $(a+b-c-d)(a-b+c-d)(a-b-c+d)$.

Let $n = 2188 = 3^7+1$ and let $A_0^{(0)}, A_1^{(0)}, ..., A_{n-1}^{(0)}$ be the vertices of a regular $n$-gon (in that order) with center $O$ . For $i = 1, 2, \dots, 7$ and $j=0,1,\dots,n-1$, let $A_j^{(i)}$ denote the centroid of the triangle \[ \triangle A_j^{(i-1)} A_{j+3^{7-i}}^{(i-1)} A_{j+2 \cdot 3^{7-i}}^{(i-1)}. \] Here the subscripts are taken modulo $n$. If \[ \frac{|OA_{2014}^{(7)}|}{|OA_{2014}^{(0)}|} = \frac{p}{q} \] for relatively prime positive integers $p$ and $q$, find $p+q$. [i]Proposed by Yang Liu[/i]

Let $S$ be the sum of all numbers of the form $a/b,$ where $a$ and $b$ are relatively prime positive divisors of $1000.$ What is the greatest integer that does not exceed $S/10?$

Let $ n$ be a positive integer, let $ A$ be a subset of $ \{1, 2, \cdots, n\}$, satisfying for any two numbers $ x, y\in A$, the least common multiple of $ x$, $ y$ not more than $ n$. Show that $ |A|\leq 1.9\sqrt {n} \plus{} 5$.

Find all positive integer $ m$ if there exists prime number $ p$ such that $ n^m\minus{}m$ can not be divided by $ p$ for any integer $ n$.

Suppose Alan, Michael, Kevin, Igor, and Big Rahul are in a running race. It is given that exactly one pair of people tie (for example, two people both get second place), so that no other pair of people end in the same position. Each competitor has equal skill; this means that each outcome of the race, given that exactly two people tie, is equally likely. The probability that Big Rahul gets first place (either by himself or he ties for first) can be expressed in the form $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Compute $m+n$.

Let $P(x)=c_nx^n+c_{n-1}x^{n-1}+\cdots+c_0$ be a polynomial with integer coefficients. Suppose that $r$ is a rational number such that $P(r)=0$. Show that the $n$ numbers $c_nr, c_nr^2+c_{n-1}r, c_nr^3+c_{n-1}r^2+c_{n-1}r, \dots, c_nr^n+c_{n-1}r^{n-1}+\cdots+c_1r$ are all integers.

For a positive integer $n$, $a_1, a_2, \cdots a_k$ are all positive integers without repetition that are not greater than $n$ and relatively prime to $n$. If $k>8$, prove the following. $$\sum_{i=1}^k |a_i-\frac{n}{2}|<\frac{n(k-4)}{2}$$

For positive rational $x$, if $x$ is written in the form $p/q$ with $p, q$ positive relatively prime integers, define $f(x)=p+q$. For example, $f(1)=2$. a) Prove that if $f(x)=f(mx/n)$ for rational $x$ and positive integers $m, n$, then $f(x)$ divides $|m-n|$. b) Let $n$ be a positive integer. If all $x$ which satisfy $f(x)=f(2^nx)$ also satisfy $f(x)=2^n-1$, find all possible values of $n$. [i]Anderson Wang.[/i]

Beyond the Point of No Return is a large lake containing 2013 islands arranged at the vertices of a regular $2013$-gon. Adjacent islands are joined with exactly two bridges. Christine starts on one of the islands with the intention of burning all the bridges. Each minute, if the island she is on has at least one bridge still joined to it, she randomly selects one such bridge, crosses it, and immediately burns it. Otherwise, she stops. If the probability Christine burns all the bridges before she stops can be written as $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$, find the remainder when $m+n$ is divided by $1000$. [i]Evan Chen[/i]

Working alone, the expert can paint a car in one day, the amateur can paint a car in two days, and the beginner can paint a car in three days. If the three painters work together at these speeds to paint three cars, it will take them $\frac{m}{n}$ days where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

The diagram below shows equilateral $\triangle ABC$ with side length $2$. Point $D$ lies on ray $\overrightarrow{BC}$ so that $CD = 4$. Points $E$ and $F$ lie on $\overline{AB}$ and $\overline{AC}$, respectively, so that $E$, $F$, and $D$ are collinear, and the area of $\triangle AEF$ is half of the area of $\triangle ABC$. Then $\tfrac{AE}{AF}=\tfrac m n$, where $m$ and $n$ are relatively prime positive integers. Find $m + 2n$. [asy] import math; size(7cm); pen dps = fontsize(10); defaultpen(dps); dotfactor=4; pair A,B,C,D,E,F; B=origin; C=(2,0); D=(6,0); A=(1,sqrt(3)); E=(1/3,sqrt(3)/3); F=extension(A,C,E,D); draw(C--A--B--D,linewidth(1.1)); draw(E--D,linewidth(.7)); dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); label("$A$",A,N); label("$B$",B,S); label("$C$",C,S); label("$D$",D,S); label("$E$",E,NW); label("$F$",F,NE); [/asy]

When the number $2^{1000}$ is divided by $13$, the remainder in the division is $\textbf{(A) }1\qquad\textbf{(B) }2\qquad\textbf{(C) }3\qquad\textbf{(D) }7\qquad \textbf{(E) }11$

Let $m_1,m_2,...,m_{2013} > 1$ be 2013 pairwise relatively prime positive integers and $A_1,A_2,...,A_{2013}$ be 2013 (possibly empty) sets with $A_i\subseteq \{1,2,...,m_i-1\}$ for $i=1,2,...,2013$. Prove that there is a positive integer $N$ such that \[ N \le \left( 2\left\lvert A_1 \right\rvert + 1 \right)\left( 2\left\lvert A_2 \right\rvert + 1 \right)\cdots\left( 2\left\lvert A_{2013} \right\rvert + 1 \right) \] and for each $i = 1, 2, ..., 2013$, there does [i]not[/i] exist $a \in A_i$ such that $m_i$ divides $N-a$. [i]Proposed by Victor Wang[/i]

Let $ABC$ be an equilateral triangle with side length $1$. This triangle is rotated by some angle about its center to form triangle $DEF.$ The intersection of $ABC$ and $DEF$ is an equilateral hexagon with an area that is $\frac{4} {5}$ the area of $ABC.$ The side length of this hexagon can be expressed in the form $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. What is $m+n$? [i]Author: Ray Li[/i]

Let us consider a set $S = \{ a_1 < a_2 < \ldots < a_{2004}\}$, satisfying the following properties: $f(a_i) < 2003$ and $f(a_i) = f(a_j) \quad \forall i, j$ from $\{1, 2,\ldots , 2004\}$, where $f(a_i)$ denotes number of elements which are relatively prime with $a_i$. Find the least positive integer $k$ for which in every $k$-subset of $S$, having the above mentioned properties there are two distinct elements with greatest common divisor greater than 1.

In a certain game, Auntie Hall has four boxes $B_1$, $B_2$, $B_3$, $B_4$, exactly one of which contains a valuable gemstone; the other three contain cups of yogurt. You are told the probability the gemstone lies in box $B_n$ is $\frac{n}{10}$ for $n=1,2,3,4$. Initially you may select any of the four boxes; Auntie Hall then opens one of the other three boxes at random (which may contain the gemstone) and reveals its contents. Afterwards, you may change your selection to any of the four boxes, and you win if and only if your final selection contains the gemstone. Let the probability of winning assuming optimal play be $\tfrac mn$, where $m$ and $n$ are relatively prime integers. Compute $100m+n$. [i]Proposed by Evan Chen[/i]

Jackie and Phil have two fair coins and a third coin that comes up heads with probability $ \frac47$. Jackie flips the three coins, and then Phil flips the three coins. Let $ \frac{m}{n}$ be the probability that Jackie gets the same number of heads as Phil, where $ m$ and $ n$ are relatively prime positive integers. Find $ m \plus{} n$.