Found problems: 97
For any two positive integers $n>m$ prove the following inequality:
$$[m,n]+[m+1,n+1]\geq \dfrac{2nm}{\sqrt{m-n}}$$
As always, $[x,y]$ means the least common multiply of $x,y$.
[I]Proposed by A. Golovanov[/i]
For $m$ and $n$ positive integers that are prime to each other, determine the possible values of
$$\gcd (5^m + 7^m, 5^n + 7^n)$$
For all $n$, $t_{n+1} = 2(t_n)^2 - 1$. Prove that gcd $(t_n,t_m) = 1$ if $n \ne m$.
Suppose $a,b,c$ are positive integers such that \[\gcd(a,b)+\gcd(a,c)+\gcd(b,c)=b+c+2023\] Prove that $\gcd(b,c)=2023$.
[i]Remark.[/i] For positive integers $x$ and $y$, $\gcd(x,y)$ denotes their greatest common divisor.
[i]Ivan Novak[/i]
Let $ \left( s_n \right)_{n\ge 1 } $ be a sequence with $ s_1 $ and defined recursively as $ s_{n+1}=s_n^2-s_n+1. $
Prove that any two terms of this sequence are coprime.
[i]Dan Nedeianu[/i]
The positive integers $a, b, c$ are such that
$$gcd \,\,\, (a, b, c) = 1,$$
$$gcd \,\,\,(a, b + c) > 1,$$
$$gcd \,\,\,(b, c + a) > 1,$$
$$gcd \,\,\,(c, a + b) > 1.$$
Determine the smallest possible value of $a + b + c$.
Clarification: gcd stands for greatest common divisor.
Let $n$ be an arbitrary positive integer.
(a) For every positive integers $a$ and $b$, show that $gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1$.
(b) Show that there exist infinitely many composite pairs ($a, b)$, such that each of them is not a multiply of the other number and equality holds in (a).
For which positive integer couples $(k,n)$, the equality
$\Bigg|\Bigg\{{a \in \mathbb{Z}^+: 1\leq a\leq(nk)!, gcd \left(\binom{a}{k},n\right)=1}\Bigg\}\Bigg|=\frac{(nk)!}{6}$
holds?
We are given a non-infinite sequence $a_1,a_2…a_n$ of natural numbers. While it is possible, on each turn are chosen two arbitrary indexes $i<j$ such that $a_i \nmid a_j$, and then $a_i$ and $a_j$ are changed with their $gcd$ and $lcm$. Prove that this process is non-infinite and the created sequence doesn’t depend on the made choices.
Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ for which these two conditions hold simultaneously
(i) For all $m,n \in \mathbb{N}$ we have:
$$ \frac{f(mn)}{\gcd(m,n)} = \frac{f(m)f(n)}{f(\gcd(m,n))};$$
(ii) For all prime numbers $p$, there exists a prime number $q$ such that $f(p^{2025})=q^{2025}$.
Find all possible pairs of integers $ a$ and $ b$ such that $ab = 160 + 90 (a,b)$, where $(a, b)$ is the greatest common divisor of $ a$ and $ b$.
Find all positive integers $x, y, z$ that satisfy the conditions: $$[x,y,z] =(x,y)+(y,z) + (z,x), x\le y\le z, (x,y,z) = 1$$
The symbols $[m,n]$ and $(m,n)$ respectively represent positive integers, the least common multiple and the greatest common divisor of $m$ and $n$.
For arbitrary positive integers $a, b$, denote $a @ b =\frac{a-b}{gcd(a,b)}$
Let $n$ be a positive integer. Prove that the following conditions are equivalent:
(i) $gcd(n, n @ m) = 1$ for every positive integer $m < n$,
(ii) $n = p^k$ where $p$ is a prime number and $k$ is a non-negative integer.
One hundred balls labelled $1$ to $100$ are to be put into two identical boxes so that each box contains at least one ball and the greatest common divisor of the product of the labels of all the balls in one box and the product of the labels of all the balls in the other box is $1$. Determine the number of ways that this can be done.
Do there exist a positive integer $k$ and a non-constant sequence $a_1, a_2, a_3, ...$ of positive integers such that $a_n = gcd(a_{n+k}, a_{n+k+1})$ for all positive integers $n$?
Let a, b, and c be nonzero integers. Show that there exists an integer k such that
$$gcd\left(a+kb, c\right) = gcd\left(a, b, c\right)$$
Find all possible triples $(a, b, c)$ of positive integers with the following properties:
• $gcd(a, b) = gcd(a, c) = gcd(b, c) = 1$,
• $a$ is a divisor of $a + b + c$,
• $b$ is a divisor of $a + b + c$,
• $c$ is a divisor of $a + b + c$.
(Here $gcd(x,y)$ is the greatest common divisor of $x$ and $y$.)
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]
Let $a, b, c$ be positive integers such that one of the values $$gcd(a,b) \cdot lcm(b,c), \,\,\,\, gcd(b,c)\cdot lcm(c,a), \,\,\,\, gcd(c,a)-\cdot lcm(a,b)$$
is equal to the product of the remaining two. Prove that one of the numbers $a, b, c$ is a multiple of another of them.
Find all triples of positive integers $(x, y, z)$ satisfying $x < y < z$, $gcd(x, y) = 6, gcd(y, z) = 10, gcd(z, x) = 8$ and $lcm(x, y,z) = 2400$.
For each pair of positive integers $m$ and $n$, we define $f_m(n)$ as follows:
$$ f_m(n) = \gcd(n, d_1) + \gcd(n, d_2) + \cdots + \gcd(n, d_k), $$
where $1 = d_1 < d_2 < \cdots < d_k = m$ are all the positive divisors of $m$. For example,
$f_4(6) = \gcd(6,1) + \gcd(6,2) + \gcd(6,4) = 5$.
$a)\:$ Find all positive integers $n$ such that $f_{2017}(n) = f_n(2017)$.
$b)\:$ Find all positive integers $n$ such that $f_6(n) = f_n(6)$.
Determine all pairs of natural numbers $ (x, y)$ for which it holds that $$x^2 = 4y + 3gcd (x, y).$$
For arbitrary natural number $a$, show that $\gcd(a^3+1, a^7+1)=a+1$.
Let $a$ be an integer and $n$ a positive integer . Show that the sum :
$$\sum_{k=1}^{n} a^{(k,n)}$$ is divisible by $n$ , where $(x,y)$ is the greatest common divisor of the numbers $x$ and $y$ .
Given an integer $a>1$. Prove that there exists a sequence of positive integers
\[ n_1, n_2, n_3, \ldots \]
Such that
\[ \gcd(a^{n_i+1} + a^{n_i} - 1, \ a^{n_j + 1} + a^{n_j} - 1) =1 \] For every $i \neq j$.