Found problems: 698
2007 Purple Comet Problems, 19
Six chairs sit in a row. Six people randomly seat themselves in the chairs. Each person randomly chooses either to set their feet on the floor, to cross their legs to the right, or to cross their legs to the left. There is only a problem if two people sitting next to each other have the person on the right crossing their legs to the left and the person on the left crossing their legs to the right. The probability that this will [b]not[/b] happen is given by $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.
2008 China Team Selection Test, 2
Let $ n > 1$ be an integer, and $ n$ can divide $ 2^{\phi(n)} \plus{} 3^{\phi(n)} \plus{} \cdots \plus{} n^{\phi(n)},$ let $ p_{1},p_{2},\cdots,p_{k}$ be all distinct prime divisors of $ n$. Show that $ \frac {1}{p_{1}} \plus{} \frac {1}{p_{2}} \plus{} \cdots \plus{} \frac {1}{p_{k}} \plus{} \frac {1}{p_{1}p_{2}\cdots p_{k}}$ is an integer. ( where $ \phi(n)$ is defined as the number of positive integers $ \leq n$ that are relatively prime to $ n$.)
2019 PUMaC Algebra B, 1
Let $a,b$ be positive integers such that $a+b=10$. Let $\tfrac{p}{q}$ be the difference between the maximum and minimum possible values of $\tfrac{1}{a}+\tfrac{1}{b}$, where $p$ and $q$ are relatively prime positive integers. Compute $p+q$.
2013 Turkey Team Selection Test, 1
Let $\phi(n)$ be the number of positive integers less than $n$ that are relatively prime to $n$, where $n$ is a positive integer. Find all pairs of positive integers $(m,n)$ such that \[2^n + (n-\phi(n)-1)! = n^m+1.\]
2010 AIME Problems, 2
A point $ P$ is chosen at random in the interior of a unit square $ S$. Let $ d(P)$ denote the distance from $ P$ to the closest side of $ S$. The probability that $ \frac15\le d(P)\le\frac13$ is equal to $ \frac{m}{n}$, where $ m$ and $ n$ are relatively prime positive integers. Find $ m\plus{}n$.
2019 PUMaC Algebra B, 4
Let $f(x)=x^2+4x+2$. Let $r$ be the difference between the largest and smallest real solutions of the equation $f(f(f(f(x))))=0$. Then $r=a^{\frac{p}{q}}$ for some positive integers $a$, $p$, $q$ so $a$ is square-free and $p,q$ are relatively prime positive integers. Compute $a+p+q$.
2019 Silk Road, 3
Find all pairs of $ (a, n) $ natural numbers such that $ \varphi (a ^ n + n) = 2 ^ n. $
($ \varphi (n) $ is the Euler function, that is, the number of integers from $1$ up to $ n $, relative prime to $ n $)
2020 China Northern MO, BP5
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)$
2020 Switzerland Team Selection Test, 4
Find all odd positive integers $ n > 1$ such that if $ a$ and $ b$ are relatively prime divisors of $ n$, then $ a\plus{}b\minus{}1$ divides $ n$.
2006 IMO Shortlist, 6
Let $ a > b > 1$ be relatively prime positive integers. Define the weight of an integer $ c$, denoted by $ w(c)$ to be the minimal possible value of $ |x| \plus{} |y|$ taken over all pairs of integers $ x$ and $ y$ such that \[ax \plus{} by \equal{} c.\] An integer $ c$ is called a [i]local champion [/i]if $ w(c) \geq w(c \pm a)$ and $ w(c) \geq w(c \pm b)$.
Find all local champions and determine their number.
[i]Proposed by Zoran Sunic, USA[/i]
2004 AIME Problems, 1
A chord of a circle is perpendicular to a radius at the midpoint of the radius. The ratio of the area of the larger of the two regions into which the chord divides the circle to the smaller can be expressed in the form $\frac{a\pi+b\sqrt{c}}{d\pi-e\sqrt{f}}$, where $a$, $b$, $c$, $d$, $e$, and $f$ are positive integers, $a$ and $e$ are relatively prime, and neither $c$ nor $f$ is divisible by the square of any prime. Find the remainder when the product $abcdef$ is divided by 1000.
2000 AIME Problems, 1
The number \[ \frac 2{\log_4{2000^6}}+\frac 3{\log_5{2000^6}} \] can be written as $\frac mn$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$
2004 Purple Comet Problems, 7
How many positive integers less that $200$ are relatively prime to either $15$ or $24$?
2000 AIME Problems, 4
The diagram shows a rectangle that has been dissected into nine non-overlapping squares. Given that the width and the height of the rectangle are relatively prime positive integers, find the perimeter of the rectangle.
[asy]
defaultpen(linewidth(0.7));
draw((0,0)--(69,0)--(69,61)--(0,61)--(0,0));draw((36,0)--(36,36)--(0,36));
draw((36,33)--(69,33));draw((41,33)--(41,61));draw((25,36)--(25,61));
draw((34,36)--(34,45)--(25,45));
draw((36,36)--(36,38)--(34,38));
draw((36,38)--(41,38));
draw((34,45)--(41,45));[/asy]
2012 AIME Problems, 9
Let $x$, $y$, and $z$ be positive real numbers that satisfy \[ 2\log_x(2y) = 2\log_{2x}(4z) = \log_{2x^4}(8yz) \neq 0. \] The value of $xy^5z$ can be expressed in the form $\frac{1}{2^{p/q}}$, where $p$ and $q$ are relatively prime integers. Find $p+q$.
PEN M Problems, 14
Let $x_{1}$ and $x_{2}$ be relatively prime positive integers. For $n \ge 2$, define $x_{n+1}=x_{n}x_{n-1}+1$.[list=a][*] Prove that for every $i>1$, there exists $j>i$ such that ${x_{i}}^{i}$ divides ${x_{j}}^{j}$. [*] Is it true that $x_{1}$ must divide ${x_{j}}^{j}$ for some $j>1$? [/list]
2019 AIME Problems, 2
Jenn randomly chooses a number $J$ from $1, 2, 3,\ldots, 19, 20$. Bela then randomly chooses a number $B$ from $1, 2, 3,\ldots, 19, 20$ distinct from $J$. The value of $B - J$ is at least $2$ with a probability that can be expressed in the form $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.
2023 AIME, 2
If $\sqrt{\log_bn}=\log_b\sqrt n$ and $b\log_bn=\log_bbn,$ then the value of $n$ is equal to $\frac jk,$ where $j$ and $k$ are relatively prime. What is $j+k$?
PEN P Problems, 19
Let $n$ be an integer of the form $a^2 + b^2$, where $a$ and $b$ are relatively prime integers and such that if $p$ is a prime, $p \leq \sqrt{n}$, then $p$ divides $ab$. Determine all such $n$.
1992 IMO Longlists, 11
Let $\phi(n,m), m \neq 1$, be the number of positive integers less than or equal to $n$ that are coprime with $m.$ Clearly, $\phi(m,m) = \phi(m)$, where $\phi(m)$ is Euler’s phi function. Find all integers $m$ that satisfy the following inequality:
\[\frac{\phi(n,m)}{n} \geq \frac{\phi(m)}{m}\]
for every positive integer $n.$
1998 Harvard-MIT Mathematics Tournament, 5
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.)
2014 NIMO Problems, 3
Let $ABCD$ be a square with side length $2$. Let $M$ and $N$ be the midpoints of $\overline{BC}$ and $\overline{CD}$ respectively, and let $X$ and $Y$ be the feet of the perpendiculars from $A$ to $\overline{MD}$ and $\overline{NB}$, also respectively. The square of the length of segment $\overline{XY}$ can be written in the form $\tfrac pq$ where $p$ and $q$ are positive relatively prime integers. What is $100p+q$?
[i]Proposed by David Altizio[/i]
2001 Korea Junior Math Olympiad, 2
$n$ is a product of some two consecutive primes. $s(n)$ denotes the sum of the divisors of $n$ and $p(n)$ denotes the number of relatively prime positive integers not exceeding $n$. Express $s(n)p(n)$ as a polynomial of $n$.
1997 IMO Shortlist, 6
(a) Let $ n$ be a positive integer. Prove that there exist distinct positive integers $ x, y, z$ such that
\[ x^{n\minus{}1} \plus{} y^n \equal{} z^{n\plus{}1}.\]
(b) Let $ a, b, c$ be positive integers such that $ a$ and $ b$ are relatively prime and $ c$ is relatively prime either to $ a$ or to $ b.$ Prove that there exist infinitely many triples $ (x, y, z)$ of distinct positive integers $ x, y, z$ such that
\[ x^a \plus{} y^b \equal{} z^c.\]
2010 Contests, 1
A function $f : \mathbb{Z}_+ \to \mathbb{Z}_+$, where $\mathbb{Z}_+$ is the set of positive integers, is non-decreasing and satisfies $f(mn) = f(m)f(n)$ for all relatively prime positive integers $m$ and $n$. Prove that $f(8)f(13) \ge (f(10))^2$.