Found problems: 698
Denote by $\phi(n)$ for all $n\in\mathbb{N}$ the number of positive integer smaller than $n$ and relatively prime to $n$. Also, denote by $\omega(n)$ for all $n\in\mathbb{N}$ the number of prime divisors of $n$. Given that $\phi(n)|n-1$ and $\omega(n)\leq 3$. Prove that $n$ is a prime number.
Find all natural numbers $k$ which can be represented as the sum of two relatively prime numbers not equal to $1$.
Ten positive integers are arranged around a circle. Each number is one more than the greatest common divisor of its two neighbors. What is the sum of the ten numbers?
The polynomial \[P(x)=(1+x+x^2+\cdots+x^{17})^2-x^{17}\] has 34 complex roots of the form $z_k=r_k[\cos(2\pi a_k)+i\sin(2\pi a_k)], k=1, 2, 3,\ldots, 34$, with $0<a_1\le a_2\le a_3\le\cdots\le a_{34}<1$ and $r_k>0$. Given that $a_1+a_2+a_3+a_4+a_5=m/n$, where $m$ and $n$ are relatively prime positive integers, find $m+n$.
In the diagram $ABCDEFG$ is a regular heptagon (a $7$ sided polygon). Shown is the star $AEBFCGD$. The degree measure of the obtuse angle formed by $AE$ and $CG$ is $\dfrac{m}{n}$ where m and n are relatively prime positive integers. Find $m + n$.
[asy]
size(150);
defaultpen(linewidth(1));
string lab[]={"A","B","C","D","E","F","G"};
real r = 360/7;
pair A=dir(90-r),B=dir(90),C=dir(90+r),D=dir(90+2*r),E=dir(90+3*r),F=dir(90+4*r),G=dir(90+5*r);
draw(A--E--B--F--C--G--D--cycle);
for(int k = -1;k <= 5;++k) {
label("$"+lab[k+1]+"$",dir(90+k*r),dir(90+k*r));
}
[/asy]
Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The probability that for every positive integer $k<5,$ no collection of $k$ pairs made by the child contains the shoes from exactly $k$ of the adults is $\tfrac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.
The number $1$ is special. The number $2$ is special because it is relatively prime to $1$. The number $3$ is not special because it is not relatively prime to the sum of the special numbers less than it, $1 + 2$. The number $4$ is special because it is relatively prime to the sum of the special numbers less than it. So, a number bigger than $1$ is special only if it is relatively prime to the sum of the special numbers less than it. Find the twentieth special number.
A drawer has $5$ pairs of socks. Three socks are chosen at random. If the probability that there is a pair among the three is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, what is $m+n$?
[i]Author: Ray Li[/i]
Let $r,s,t$ positive integers which are relatively prime and $a,b \in G$, $G$ a commutative multiplicative group with unit element $e$, and $a^r=b^s=(ab)^t=e$.
(a) Prove that $a=b=e$.
(b) Does the same hold for a non-commutative group $G$?
Show that, for any fixed integer $\,n \geq 1,\,$ the sequence \[ 2, \; 2^2, \; 2^{2^2}, \; 2^{2^{2^2}}, \ldots (\mbox{mod} \; n) \] is eventually constant.
[The tower of exponents is defined by $a_1 = 2, \; a_{i+1} = 2^{a_i}$. Also $a_i \; (\mbox{mod} \; n)$ means the remainder which results from dividing $a_i$ by $n$.]
Define $a_k = (k^2 + 1)k!$ and $b_k = a_1 + a_2 + a_3 + \cdots + a_k$. Let \[\frac{a_{100}}{b_{100}} = \frac{m}{n}\] where $m$ and $n$ are relatively prime natural numbers. Find $n - m$.
In the middle of a vast prairie, a firetruck is stationed at the intersection of two perpendicular straight highways. The truck travels at $50$ miles per hour along the highways and at $14$ miles per hour across the prairie. Consider the set of points that can be reached by the firetruck within six minutes. The area of this region is $m/n$ square miles, where $m$ and $n$ are relatively prime positive integers. Find $m+n.$
Set $S = \{1, 2, 3, ..., 2005\}$. If among any $n$ pairwise coprime numbers in $S$ there exists at least a prime number, find the minimum of $n$.
Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$?
PUMaCDonalds, a newly-opened fast food restaurant, has 5 menu items. If the first 4 customers each choose one menu item at random, the probability that the 4th customer orders a previously unordered item is $m/n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.
By a [i]pure repeating decimal[/i] (in base $10$), we mean a decimal $0.\overline{a_1\cdots a_k}$ which repeats in blocks of $k$ digits beginning at the decimal point. An example is $.243243243\cdots = \tfrac{9}{37}$. By a [i]mixed repeating decimal[/i] we mean a decimal $0.b_1\cdots b_m\overline{a_1\cdots a_k}$ which eventually repeats, but which cannot be reduced to a pure repeating decimal. An example is $.011363636\cdots = \tfrac{1}{88}$.
Prove that if a mixed repeating decimal is written as a fraction $\tfrac pq$ in lowest terms, then the denominator $q$ is divisible by $2$ or $5$ or both.
Let $a$ be a rational number and let $n$ be a positive integer. Prove that the polynomial $X^{2^n}(X+a)^{2^n}+1$ is irreducible in the ring $\mathbb{Q}[X]$ of polynomials with rational coefficients.
[i]Proposed by Vincent Jugé, École Polytechnique, Paris.[/i]
Suppose that $m>2$, and let $P$ be the product of the positive integers less than $m$ that are relatively prime to $m$. Show that $P \equiv -1 \pmod{m}$ if $m=4$, $p^n$, or $2p^{n}$, where $p$ is an odd prime, and $P \equiv 1 \pmod{m}$ otherwise.
Dave rolls a fair six-sided die until a six appears for the first time. Independently, Linda rolls a fair six-sided die until a six appears for the first time. Let $ m$ and $ n$ be relatively prime positive integers such that $ \frac{m}{n}$ is the probability that the number of times Dave rolls his die is equal to or within one of the number of times Linda rolls her die. Find $ m\plus{}n$.
We have a positive integer $ n$ such that $ n \neq 3k$. Prove that there exists a positive integer $ m$ such that $ \forall_{k\in N \ k\geq m} \ k$ can be represented as a sum of digits of some multiplication of $ n$.
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}$.
Let $k$ be a positive integer. Prove that there exists a positive integer $\ell$ with the following property: if $m$ and $n$ are positive integers relatively prime to $\ell$ such that $m^m\equiv n^n \pmod{\ell}$, then $m\equiv n \pmod k$.
A number is called [i]purple[/i] if it can be expressed in the form $\frac{1}{2^a 5^b}$ for positive integers $a > b$. The sum of all purple numbers can be expressed as $\frac{a}{b}$ for relatively prime positive integers $a, b$. Compute $100a + b$.
[i]Proposed by Eugene Chen[/i]
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]
The sum $$\sum_{k=3}^{\infty} \frac{1}{k(k^4-5k^2+4)^2}$$ is equal to $\frac{m^2}{2n^2}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.