Found problems: 583
Let $x, y$ be positive integers such that $\gcd(x,y)=1$ and $x+3y^2$ is a perfect square. Prove that $x^2+9y^4$ can't be a perfect square.
What is the greatest common divisor of the set of numbers \[\{{16}^{n}+10n-1 \; \vert \; n=1,2,\cdots \}?\]
Determine all functions $f: \mathbb{Z}\to\mathbb{Z}$ satisfying the following property: For each pair of integers $m$ and $n$ (not necessarily distinct), $\mathrm{gcd}(m, n)$ divides $f(m) + f(n)$.
Note: If $n\in\mathbb{Z}$, $\mathrm{gcd}(m, n)=\mathrm{gcd}(|m|, |n|)$ and $\mathrm{gcd}(n, 0)=n$.
Let $a,b$ be two integers such that their gcd has at least two prime factors. Let $S = \{ x \mid x \in \mathbb{N}, x \equiv a \pmod b \} $ and call $ y \in S$ irreducible if it cannot be expressed as product of two or more elements of $S$ (not necessarily distinct). Show there exists $t$ such that any element of $S$ can be expressed as product of at most $t$ irreducible elements.
Two thieves stole a container of $8$ liters of wine. How can they divide it into two parts of $4$ liters each if all they have is a $3 $ liter container and a $5$ liter container? Consider the general case of dividing $m+n$ liters into two equal amounts, given a container of $m$ liters and a container of $n$ liters (where $m$ and $n$ are positive integers). Show that it is possible iff $m+n$ is even and $(m+n)/2$ is divisible by $gcd(m,n)$.
Let $f_n$ be the Fibonacci numbers, defined by $f_0 = 1$, $f_1 = 1$, and $f_n = f_{n-1}+f_{n-2}$. For each $i$, $1 \le i \le 200$, we calculate the greatest common divisor $g_i$ of $f_i$ and $f_{2007}$. What is the sum of the distinct values of $g_i$?
On each day of their tour of the West Indies, Sourav and Srinath have either an apple or an orange for breakfast. Sourav has oranges for the first $m$ days, apples for the next $m$ days, followed by oranges for the next $m$ days, and so on. Srinath has oranges for the first $n$ days, apples for the next $n$ days, followed by oranges for the next $n$ days, and so on.
If $\gcd(m,n)=1$, and if the tour lasted for $mn$ days, on how many days did they eat the same kind of fruit?
A sequence of positive integers $a_1, a_2,\ldots, a_n$ is called [i]ladder[/i] of length $n$ if it consists of $n$ consecutive integers in ascending order.
(a) Prove that for every positive integer $n$ there exist two ladders of length $n$, with no elements in common,
$a_1, a_2,\ldots, a_n$ and $b_1, b_2,\ldots, b_n$, such that for all $i$ between $1$ and $n$, the greatest common divisor of $a_i$ and $b_i$ is equal to $1$.
(b) Prove that for every positive integer $n$ there exist two ladders of length $n$, with no elements in common,
$a_1, a_2,\ldots, a_n$ and $b_1, b_2,\ldots, b_n$, such that for all $i$ between $1$ and $n$, the greatest common divisor of $a_i$ and $b_i$ is greater than $1$.
Given $T_1 =2, T_{n+1}= T_{n}^{2} -T_n +1$ for $n>0.$ Prove:
(i) If $m \ne n,$ $T_m$ and $T_n$ have no common factor greater than $1.$
(ii) $\sum_{i=1}^{\infty} \frac{1}{T_i }=1.$
Let $c$ be the least common multiple of positive integers $a$ and $b$, and $d$ be the greatest common divisor of $a$ and $b$. How many pairs of positive integers $(a,b)$ are there such that
\[
\dfrac {1}{a} + \dfrac {1}{b} + \dfrac {1}{c} + \dfrac {1}{d} = 1?
\]
$
\textbf{(A)}\ 6
\qquad\textbf{(B)}\ 5
\qquad\textbf{(C)}\ 4
\qquad\textbf{(D)}\ 3
\qquad\textbf{(E)}\ 2
$
How many distinct four-tuples $ (a,b,c,d)$ of rational numbers are there with
$ a \log_{10} 2 \plus{} b \log_{10} 3 \plus{} c \log_{10} 5 \plus{} d \log_{10} 7 \equal{} 2005$?
$ \textbf{(A)}\ 0\qquad
\textbf{(B)}\ 1\qquad
\textbf{(C)}\ 17\qquad
\textbf{(D)}\ 2004\qquad
\textbf{(E)}\ \text{infinitely many}$
All the species of plants existing in Russia are catalogued (numbered by integers from $2$ to $2000$ ; one after another, without omissions or repetitions). For any pair of species the gcd of their catalogue numbers was calculated and recorded but the catalogue numbers themselves were lost. Is it possible to restore the catalogue numbers from the data in hand?
Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.
Written on a blackboard are $n$ nonnegative integers whose greatest common divisor is $1$. A [i]move[/i] consists of erasing two numbers $x$ and $y$, where $x\ge y$, on the blackboard and replacing them with the numbers $x-y$ and $2y$. Determine for which original $n$-tuples of numbers on the blackboard is it possible to reach a point, after some number of moves, where $n-1$ of the numbers of the blackboard are zeroes.
Let $n$ be a positive integer and $d$ be the greatest common divisor of $n^2+1$ and $(n + 1)^2 + 1$. Find all the possible values of $d$. Justify your answer.
$ ABCD$ is a square of side length $ \sqrt{3} + 1 $. Point $ P $ is on $ \overline{AC} $ such that $ AP = \sqrt{2} $. The square region bounded by $ ABCD $ is rotated $ 90^{\circ} $ counterclockwise with center $ P $, sweeping out a region whose area is $ \frac{1}{c} (a \pi + b) $, where $a $, $b$, and $ c $ are positive integers and $ \text{gcd}(a,b,c) = 1 $. What is $ a + b + c $?
$\textbf{(A)} \ 15 \qquad \textbf{(B)} \ 17 \qquad \textbf{(C)} \ 19 \qquad \textbf{(D)} \ 21 \qquad \textbf{(E)} \ 23 $
Let $S$ be the set of all pairs $(a,b)$ of real numbers satisfying $1+a+a^2+a^3 = b^2(1+3a)$ and $1+2a+3a^2 = b^2 - \frac{5}{b}$. Find $A+B+C$, where \[
A = \prod_{(a,b) \in S} a
, \quad
B = \prod_{(a,b) \in S} b
, \quad \text{and} \quad
C = \sum_{(a,b) \in S} ab.
\][i]Proposed by Evan Chen[/i]
Suppose that the natural number $a, b, c, d$ satisfy the equation $a^ab^{a + b} = c^cd^{c + d}$.
(a) If gcd $(a, b) = $ gcd $(c, d) = 1$, prove that $a = c$ and $b = d$.
(b) Does the conclusion $a = c$ and $b = d$ apply, without the condition gcd $(a, b) = $ gcd $(c, d) = 1$?
Let $d$ be the greatest common divisor of $2^{30^{10}}-2$ and $2^{30^{45}}-2$. Find the remainder when $d$ is divided by $2013$.
Determine if there exist positive integer pairs $(m,n)$, such that
(i) the greatest common divisor of m and $n$ is $1$, and $m \le 2007$,
(ii) for any $k=1,2,..., 2007$, $\big[\frac{nk}{m}\big]=\big[\sqrt2 k\big]$ .
(Here $[x]$ stands for the greatest integer less than or equal to $x$.)
At the vertices of a cube are written eight pairwise distinct natural numbers, and on each of its edges is written the greatest common divisor of the numbers at the endpoints of the edge. Can the sum of the numbers written at the vertices be the same as the sum of the numbers written at the edges?
[i]A. Shapovalov[/i]
Do there exist postive integers $a_1<a_2<\cdots<a_{100}$ such that for $2\le k\le100$ the greatest common divisor of $a_{k-1}$ and $a_k$ is greater than the greatest common divisor of $a_k$ and $a_{k+1}$?
Find all pairs of integers $(m,n)$ such that $m^6 = n^{n+1} + n -1$.
Let $f : \mathbb{Z} \rightarrow \mathbb{Z}^+$ be a function, and define $h : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}^+$ by $h(x, y) = \gcd (f(x), f(y))$. If $h(x, y)$ is a two-variable polynomial in $x$ and $y$, prove that it must be constant.
[b]2.[/b] Let $n \geq 3$ be an integer. Prove that for all integers $k$, with $1 \leq k \leq \binom{n}{2}$, there exists a set $A$ with $n$ distinct positive integer elements such that the set $B = \{\gcd(x, y): x, y \in A, x \neq y \}$ (gotten from the greatest common divisor of all pairs of distinct elements from $A$) contains exactly $k$ distinct elements.