Found problems: 583
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.
For every natural number $a$ and $b$, define the notation $[a,b]$ as the least common multiple of $a $ and $b$ and the notation $(a,b)$ as the greatest common divisor of $a$ and $b$. Find all $n \in \mathbb{N}$ that satisfies
\[
4 \sum_{k=1}^{n} [n,k] = 1 + \sum_{k=1}^{n} (n,k) + 2n^2 \sum_{k=1}^{n} \frac{1}{(n,k)}
\]
Let $a_{i}$ and $b_{i}$ ($i=1,2, \cdots, n$) be rational numbers such that for any real number $x$ there is:
\[x^{2}+x+4=\sum_{i=1}^{n}(a_{i}x+b)^{2}\]
Find the least possible value of $n$.
For any positive integer $n$, we define the integer $P(n)$ by :
$P(n)=n(n+1)(2n+1)(3n+1)...(16n+1)$.
Find the greatest common divisor of the integers $P(1)$, $P(2)$, $P(3),...,P(2016)$.
Let $H_1, H_2,\ldots, H_m$ be non-empty subsets of the positive integers, and let $S$ denote their union. Prove that
\[\sum_{i=1}^m \sum_{(a,b)\in H_i^2}\gcd(a,b)\ge\frac1m \sum_{(a,b)\in S^2}\gcd(a,b).\]
[i]Proposed by Dávid Matolcsi, Berkeley[/i]
A finite set $S$ of positive integers has the property that, for each $s \in S,$ and each positive integer divisor $d$ of $s$, there exists a unique element $t \in S$ satisfying $\text{gcd}(s, t) = d$. (The elements $s$ and $t$ could be equal.)
Given this information, find all possible values for the number of elements of $S$.
Determine all positive integers $n$ for which there exists a polynomial $f(x)$ with real coefficients, with the following properties:
(1) for each integer $k$, the number $f(k)$ is an integer if and only if $k$ is not divisible by $n$;
(2) the degree of $f$ is less than $n$.
[i](Hungary) Géza Kós[/i]
Find all $m,n\in\mathbb N$ and primes $p\geq 5$ satisfying
\[m(4m^2+m+12)=3(p^n-1).\]
Let $m,n$ are positive integers.
a)Prove that $(m,n)=2\sum_{k=0}^{m-1}[\frac{kn}{m}]+m+n-mn$.
b)If $m,n\geq 2$, prove that $\sum_{k=0}^{m-1}[\frac{kn}{m}]=\sum_{k=0}^{n-1}[\frac{km}{n}]$.
Find the smallest positive integer $n$ for which there exist $n$ different positive integers $a_{1}, a_{2}, \cdots, a_{n}$ satisfying [list] [*] $\text{lcm}(a_1,a_2,\cdots,a_n)=1985$,[*] for each $i, j \in \{1, 2, \cdots, n \}$, $gcd(a_i,a_j)\not=1$, [*] the product $a_{1}a_{2} \cdots a_{n}$ is a perfect square and is divisible by $243$, [/list] and find all such $n$-tuples $(a_{1}, \cdots, a_{n})$.
Find all positive integer triples $(x,y,z)$ such that
$x<y<z$, $\gcd (x,y)=6$, $\gcd (y,z)=10$, $\gcd (x,z)=8$, and lcm$(x,y,z)=2400$.
Note that the problems of the TST are not arranged in difficulty (Problem 1 of day 1 was probably the most difficult!)
The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $\gcd (F_{m}, F_{n})=F_{\gcd (m, n)}$ for all $m, n \in \mathbb{N}$.
Prove that if coefficients of the quadratic equation $ ax^2\plus{}bx\plus{}c\equal{}0$ are odd integers, then the roots of the equation cannot be rational numbers.
How many ordered pairs of positive integers $(m, n)$ satisfy the system
\begin{align*}
\gcd (m^3, n^2) & = 2^2 \cdot 3^2,
\\ \text{LCM} [m^2, n^3] & = 2^4 \cdot 3^4 \cdot 5^6,
\end{align*}
where $\gcd(a, b)$ and $\text{LCM}[a, b]$ denote the greatest common divisor and least common multiple of $a$ and $b$, respectively?
Find the greatest common divisor of the numbers \[ 2^{561}\minus{}2, 3^{561}\minus{}3, \ldots, 561^{561}\minus{}561.\]
Given integer $a_1\geq 2$. For integer $n\geq 2$, define $a_n$ to be the smallest positive integer which is not coprime to $a_{n-1}$ and not equal to $a_1,a_2,\cdots, a_{n-1}$. Prove that every positive integer except 1 appears in this sequence $\{a_n\}$.
Find all triples $(a,b,c)$ of positive integers such that
(i) $a \leq b \leq c$;
(ii) $\text{gcd}(a,b,c)=1$; and
(iii) $a^3+b^3+c^3$ is divisible by each of the numbers $a^2b, b^2c, c^2a$.
Let $a_1,a_2,\dots, a_n$ be positive integers with product $P,$ where $n$ is an odd positive integer. Prove that $$\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\le 2\gcd(a_1,\dots, a_n)^n.$$
[i]Proposed by Daniel Liu[/i]
Determine all pairs $ (n,p)$ of positive integers, where $ p$ is prime, such that $ 3^p\minus{}np\equal{}n\plus{}p$.
Suppose $a$, $b$, and $c$ are positive integers such that \[\frac{a}{14}+\frac{b}{15}=\frac{c}{210}.\] Which of the following statements are necessarily true?
I. If $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both, then $\gcd(c,210)=1$.
II. If $\gcd(c,210)=1$, then $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both.
III. $\gcd(c,210)=1$ if and only if $\gcd(a,14)=\gcd(b,15)=1$.
$\textbf{(A)}~\text{I, II, and III}\qquad\textbf{(B)}~\text{I only}\qquad\textbf{(C)}~\text{I and II only}\qquad\textbf{(D)}~\text{III only}\qquad\textbf{(E)}~\text{II and III only}$
Let $n$ be a positive integer and let $A_n$ respectively $B_n$ be the set of nonnegative integers $k<n$ such that the number of distinct prime factors of $\gcd(n,k)$ is even (respectively odd). Show that $|A_n|=|B_n|$ if $n$ is even and $|A_n|>|B_n|$ if $n$ is odd.
Example: $A_{10} = \left\{ 0,1,3,7,9 \right\}$, $B_{10} = \left\{ 2,4,5,6,8 \right\}$.
For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.
Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.
[b]Note: Graph-Definition[/b]. A [b]graph[/b] consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x \equal{} v_{0},v_{1},v_{2},\cdots ,v_{m} \equal{} y\,$ such that each pair $ \,v_{i},v_{i \plus{} 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.
For positive integers $m$ and $n$ we define $T(m,n) = gcd \left(m, \frac{n}{gcd(m,n)} \right)$
(a) Prove that there are infinitely many pairs $(m,n)$ of positive integers for which $T(m,n) > 1$ and $T(n,m) > 1$.
(b) Do there exist positive integers $m,n$ such that $T(m,n) = T(n,m) > 1$?
For the positive integers $x , y$ and $z$ apply $\frac{1}{x}+\frac{1}{y}=\frac{1}{z}$ .
Prove that if the three numbers $x , y,$ and $z$ have no common divisor greater than $1$, $x + y$ is the square of an integer.