Find all positive integers $n>1$ such that \[\tau(n)+\phi(n)=n+1\] Which in this case, $\tau(n)$ represents the amount of positive divisors of $n$, and $\phi(n)$ represents the amount of positive integers which are less than $n$ and relatively prime with $n$. [i]Raja Oktovin, Pekanbaru[/i]

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]

Prove that for any positive integer $ k$, there exists an arithmetic sequence $ \frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}, ... ,\frac{a_k}{b_k}$ of rational numbers, where $ a_i, b_i$ are relatively prime positive integers for each $ i \equal{} 1,2,...,k$ such that the positive integers $ a_1, b_1, a_2, b_2, ..., a_k, b_k$ are all distinct.

Let $a$, $b$, $c$ be positive reals for which \begin{align*} (a+b)(a+c) &= bc + 2 \\ (b+c)(b+a) &= ca + 5 \\ (c+a)(c+b) &= ab + 9 \end{align*} If $abc = \frac{m}{n}$ for relatively prime positive integers $m$ and $n$, compute $100m+n$. [i]Proposed by Evan Chen[/i]

Look at these fractions. At firs step we have $ \frac{0}{1}$ and $ \frac{1}{0}$, and at each step we write $ \frac{a\plus{}b}{c\plus{}d}$ between $ \frac{a}{b}$ and $ \frac{c}{d}$, and we do this forever \[ \begin{array}{ccccccccccccccccccccccccc}\frac{0}{1}&&&&&&&&\frac{1}{0}\\ \frac{0}{1}&&&&\frac{1}{1}&&&&\frac{1}{0}\\ \frac{0}{1}&&\frac{1}{2}&&\frac{1}{1}&&\frac{2}{1}&&\frac{1}{0}\\ \frac{0}{1}&\frac{1}{3}&\frac{1}{2}&\frac{2}{3}&\frac{1}{1}&\frac{3}{2}&\frac{2}{1}&\frac{3}{1}&\frac{1}{0}\\ &&&&\dots\end{array}\] a) Prove that each of these fractions is irreducible. b) In the plane we have put infinitely many circles of diameter 1, over each integer on the real line, one circle. The inductively we put circles that each circle is tangent to two adjacent circles and real line, and we do this forever. Prove that points of tangency of these circles are exactly all the numbers in part a(except $ \frac{1}{0}$). [img]http://i2.tinypic.com/4m8tmbq.png[/img] c) Prove that in these two parts all of positive rational numbers appear. If you don't understand the numbers, look at [url=http://upload.wikimedia.org/wikipedia/commons/2/21/Arabic_numerals-en.svg]here[/url].

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

Let $n$ be a positive integer. Let $A_n$ denote the set of primes $p$ such that there exists positive integers $a,b$ satisfying $$\frac{a+b}{p} \text{ and } \frac{a^n + b^n}{p^2}$$ are both integers that are relatively prime to $p$. If $A_n$ is finite, let $f(n)$ denote $|A_n|$. a) Prove that $A_n$ is finite if and only if $n \not = 2$. b) Let $m,k$ be odd positive integers and let $d$ be their gcd. Show that $$f(d) \leq f(k) + f(m) - f(km) \leq 2 f(d).$$

Find the smallest integer $k$ for which the conditions $(1)$ $a_1, a_2, a_3, \ldots$ is a nondecreasing sequence of positive integers $(2)$ $a_n=a_{n-1}+a_{n-2}$ for all $n>2$ $(3)$ $a_9=k$ are satisfied by more than one sequence.

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]

For positive integer $k$, define $x_k=3k+\sqrt{k^2-1}-2(\sqrt{k^2-k}+\sqrt{k^2+k})$. Then $\sqrt{x_1}+\sqrt{x_2}+\cdots+\sqrt{x_{1681}}=\sqrt{m}-n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Prove that we can find an infinite set of positive integers of the from $2^n-3$ (where $n$ is a positive integer) every pair of which are relatively prime.

Ralph is standing along a road which heads straight east. If you go nine miles east, make a left turn, and travel seven miles north, you will find Pamela with her mountain bike. At exactly the same time that Ralph begins running eastward along the road at 6 miles per hour, Pamela begins biking in a straight line at 10 miles per hour. Pamela’s direction is chosen so that she will reach a point on the road where Ralph is running at exactly the same time Ralph reaches that same point. Let $M$ and $N$ be relatively prime positive integers such that $\frac{M}{N}$ is the number of hours that it takes Pamela and Ralph to meet. Find $M+N$.

You know that the Jones family has five children, and the Smith family has three children. Of the eight children you know that there are five girls and three boys. Let $\dfrac{m}{n}$ be the probability that at least one of the families has only girls for children. Given that $m$ and $n$ are relatively prime positive integers, find $m+ n$.

Square $S_{1}$ is $1\times 1.$ For $i\ge 1,$ the lengths of the sides of square $S_{i+1}$ are half the lengths of the sides of square $S_{i},$ two adjacent sides of square $S_{i}$ are perpendicular bisectors of two adjacent sides of square $S_{i+1},$ and the other two sides of square $S_{i+1},$ are the perpendicular bisectors of two adjacent sides of square $S_{i+2}.$ The total area enclosed by at least one of $S_{1}, S_{2}, S_{3}, S_{4}, S_{5}$ can be written in the form $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m-n.$ [asy] size(250); path p=rotate(45)*polygon(4); int i; for(i=0; i<5; i=i+1) { draw(shift(2-(1/2)^(i-1),0)*scale((1/2)^i)*p); } label("$S_1$", (0,-0.75)); label("$S_2$", (1,-0.75)); label("$S_3$", (3/2,-0.75)); label("$\cdots$", (7/4, -3/4)); label("$\cdots$", (2.25, 0));[/asy]

Find the number of ordered triples of positive integers $(a,b,c),$ where $1 \leq a,b,c \leq 10,$ with the property that $\gcd(a,b), \gcd(a,c),$ and $\gcd(b,c)$ are all pairwise relatively prime. [i]Proposed by Kyle Lee[/i]

Prove that for positive integers $ x,y,z$ the number $ x^2 \plus{} y^2 \plus{} z^2$ is not divisible by $ 3(xy \plus{} yz \plus{} zx)$.

Let $S$ denote the set of words $W = w_1w_2\ldots w_n$ of any length $n\ge0$ (including the empty string $\lambda$), with each letter $w_i$ from the set $\{x,y,z\}$. Call two words $U,V$ [i]similar[/i] if we can insert a string $s\in\{xyz,yzx,zxy\}$ of three consecutive letters somewhere in $U$ (possibly at one of the ends) to obtain $V$ or somewhere in $V$ (again, possibly at one of the ends) to obtain $U$, and say a word $W$ is [i]trivial[/i] if for some nonnegative integer $m$, there exists a sequence $W_0,W_1,\ldots,W_m$ such that $W_0=\lambda$ is the empty string, $W_m=W$, and $W_i,W_{i+1}$ are similar for $i=0,1,\ldots,m-1$. Given that for two relatively prime positive integers $p,q$ we have \[\frac{p}{q} = \sum_{n\ge0} f(n)\left(\frac{225}{8192}\right)^n,\]where $f(n)$ denotes the number of trivial words in $S$ of length $3n$ (in particular, $f(0)=1$), find $p+q$. [i]Victor Wang[/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$.

Natural $p$ and $q$ are relatively prime. The $[0,1]$ is divided onto $(p+q)$ equal segments. Prove that every segment except two marginal contain exactly one from the $(p+q-2)$ numbers $$\{1/p, 2/p, ... , (p-1)/p, 1/q, 2/q, ... , (q-1)/q\}$$

Prove that the set of all the points with both coordinates begin rational numbers can be written as a reunion of two disjoint sets $ A$ and $ B$ such that any line that that is parallel with $ Ox$, and respectively $ Oy$ intersects $ A$, and respectively $ B$ in a finite number of points.

When $12{}^1{}^8$ is divided by $18{}^1{}^2$, the result is $(\tfrac{m}{n})^3$, where $m$ and $n$ are relatively prime integers. Find $m-n$.

How many positive integers less than $1998$ are relatively prime to $1547$? (Two integers are relatively prime if they have no common factors besides 1.)

A bag contains $8$ green candies and $4$ red candies. You randomly select one candy at a time to eat. If you eat five candies, there are relatively prime positive integers $m$ and $n$ so that $\frac{m}{n}$ is the probability that you do not eat a green candy after you eat a red candy. Find $m+n$.

A jar has 10 red candies and 10 blue candies. Terry picks two candies at random, then Mary picks two of the remaining candies at random. Given that the probability that they get the same color combination, irrespective of order, is $m/n$, where $m$ and $n$ are relatively prime positive integers, find $m+n$.

Alpha and Beta both took part in a two-day problem-solving competition. At the end of the second day, each had attempted questions worth a total of 500 points. Alpha scored 160 points out of 300 points attempted on the first day, and scored 140 points out of 200 points attempted on the second day. Beta who did not attempt 300 points on the first day, had a positive integer score on each of the two days, and Beta's daily success rate (points scored divided by points attempted) on each day was less than Alpha's on that day. Alpha's two-day success ratio was 300/500 = 3/5. The largest possible two-day success ratio that Beta could achieve is $m/n$, where $m$ and $n$ are relatively prime positive integers. What is $m+n$?