Let \( n \) be a natural number. The numbers \( 1, 2, \ldots, n \) are written in a row in some order. For each pair of adjacent numbers, their greatest common divisor (GCD) is calculated and written on a sheet. What is the maximum possible number of distinct values among the \( n - 1 \) GCDs obtained? \\

For each integer $n$ ($n \ge 2$), let $f(n)$ denote the sum of all positive integers that are at most $n$ and not relatively prime to $n$. Prove that $f(n+p) \neq f(n)$ for each such $n$ and every prime $p$.

Let $19$ integer numbers are given. Let Hamza writes on the paper the greatest common divisor for each pair of numbers. It occurs that the difference between the biggest and smallest numbers written on the paper is less than $180$. Prove that not all numbers on the paper are different.

$n > 1$ is an odd number and $a_1, a_2, . . . , a_n$ are positive integers such that $gcd(a_1, a_2, . . . , a_n) = 1$. If $d = gcd (a_1^n + a_1.a_2. . . a_n, a_2^n + a_1.a_2. . . a_n, . . . , a_n^n + a_1.a_2. . . a_n) $ find all possible values of $d$.

Let $n$ be integer, $n>1.$ An element of the set $M=\{ 1,2,3,\ldots,n^2-1\}$ is called [i]good[/i] if there exists some element $b$ of $M$ such that $ab-b$ is divisible by $n^2.$ Furthermore, an element $a$ is called [i]very good[/i] if $a^2-a$ is divisible by $n^2.$ Let $g$ denote the number of [i]good[/i] elements in $M$ and $v$ denote the number of [i]very good[/i] elements in $M.$ Prove that \[v^2+v \leq g \leq n^2-n.\]

Consider a sequence $(a_k)_{k \ge 1}$ of natural numbers defined as follows: $a_1=a$ and $a_2=b$ with $a,b>1$ and $\gcd(a,b)=1$ and for all $k>0$, $a_{k+2}=a_{k+1}+a_k$. Prove that for all natural numbers $n$ and $k$, $\gcd(a_n,a_{n+k}) <\frac{a_k}{2}$.

Let $S$ be the set of positive integers. For any $a$ and $b$ in the set we have $GCD(a, b)>1$. For any $a$, $b$ and $c$ in the set we have $GCD(a, b, c)=1$. Is it possible that $S$ has $2012$ elements? [i]Proposed by Ognjen Stipetić.[/i]

Let $A$ be a set of positive integers with at least 2 elements. It is given that for any numbers $a>b$, $a,b \in A$ we have $\frac{ [a,b] }{ a- b } \in A$, where by $[a,b]$ we have denoted the least common multiple of $a$ and $b$. Prove that the set $A$ has [i]exactly[/i] two elements. [i]Marius Gherghu, Slatina[/i]

Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i \plus{} 1}) > a_{i \minus{} 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$. [i]Proposed by Morteza Saghafian, Iran[/i]

Solve the equation $mn =$ (gcd($m,n$))$^2$ + lcm($m, n$) in positive integers, where gcd($m, n$) – greatest common divisor of $m,n$, and lcm($m, n$) – least common multiple of $m,n$.

What is that largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$?

Let $x$ and $y$ be positive integers such that $2(x+y)=gcd(x,y)+lcm(x,y)$. Find $\frac{lcm(x,y)}{gcd(x,y)}$.

For each positive integer $ n$, let $ f(n)$ denote the greatest common divisor of $ n!\plus{}1$ and $ (n\plus{}1)!$. Find, without proof, a formula for $ f(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.

A set of five different positive integers is called [i]virtual[/i] if the greatest common divisor of any three of its elements is greater than $1$, but the greatest common divisor of any four of its elements is equal to $1$. Prove that, in any virtual set, the product of its elements has at least $2020$ distinct positive divisors. [i]Proposed by Víctor Almendra[/i]

Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i \plus{} 1}) > a_{i \minus{} 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$. [i]Proposed by Morteza Saghafian, Iran[/i]

Consider the set $S= \{(a + b)^7 - a^7 - b^7 : a,b \in Z\}$. Find the greatest common divisor of all members in $S$.

For each integer $n$ ($n \ge 2$), let $f(n)$ denote the sum of all positive integers that are at most $n$ and not relatively prime to $n$. Prove that $f(n+p) \neq f(n)$ for each such $n$ and every prime $p$.

Let $a, b, c,$ and $d$ be positive integers such that $\gcd(a, b)=24$, $\gcd(b, c)=36$, $\gcd(c, d)=54$, and $70<\gcd(d, a)<100$. Which of the following must be a divisor of $a$? $\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}$

[b]Q11.[/b] Let be given a sequense $a_1=5, \; a_2=8$ and $a_{n+1}=a_n+3a_{n-1}, \qquad n=1,2,3,...$ Calculate the greatest common divisor of $a_{2011}$ and $a_{2012}$.

Let $B=\{2^1,2^2,2^3,\dots,2^{21}\}.$ Find the remainder when \[ \sum_{m, n \in B: \ m<n}\gcd(m,n) \] is divided by $1000,$ where the sum is taken over all pairs of elements $(m,n)$ of $B$ such that $m<n.$

The polynomial $P(x)$ is cubic. What is the largest value of $k$ for which the polynomials $Q_{1}(x) = x^{2}+(k-29)x-k$ and $Q_{2}(x) = 2x^{2}+(2k-43)x+k$ are both factors of $P(x)$?

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?

Let $X$ be the set of natural numbers whose all digits in the decimal representation are different. For $n \in N$, denote by $A_n$ the set of numbers whose digits are a permutation of the digits of $n$, and $d_n$ be the greatest common divisor of the numbers in $A_n$. (For example, $A_{1120} =\{112,121,...,2101,2110\}$, so $d_{1120} = 1$.) Find the maximum possible value of $d_n$.

Denote the set of all positive integers by $\mathbb{N}$, and the set of all ordered positive integers by $\mathbb{N}^2$. For all non-negative integers $k$, define [i]good functions of order k[/i] recursively for all non-negative integers $k$, among all functions from $\mathbb{N}^2$ to $\mathbb{N}$ as follows: (i) The functions $f(a,b)=a$ and $f(a,b)=b$ are both good functions of order $0$. (ii) If $f(a,b)$ and $g(a,b)$ are good functions of orders $p$ and $q$, respectively, then $\gcd(f(a,b),g(a,b))$ is a good function of order $p+q$, while $f(a,b)g(a,b)$ is a good function of order $p+q+1$. Prove that, if $f(a,b)$ is a good function of order $k\leq \binom{n}{3}$ for some positive integer $n\geq 3$, then there exist a positive integer $t\leq \binom{n}{2}$ and $t$ pairs of non-negative integers $(x_1,y_1),\ldots,(x_n,y_n)$ such that $$f(a,b)=\gcd(a^{x_1}b^{y_1},\ldots,a^{x_t}b^{y_t})$$ holds for all positive integers $a$ and $b$. [i]Proposed by usjl[/i]