Found problems: 583
Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that for any pair of naturals $m,n$,
$$\gcd(f(m),n) = \gcd(m,f(n)).$$
Determine all positive integers $n$ less than $2024$ such that for all positive integers $x$, the greatest common divisor of $9x + 1$ and $nx+1$ is $1$.
How many ordered pairs $(a, b)$ of positive integers satisfy the equation
$$a\cdot b + 63 = 20\cdot \text{lcm}(a, b) + 12\cdot\text{gcd}(a,b),$$
where $\text{gcd}(a,b)$ denotes the greatest common divisor of $a$ and $b$, and $\text{lcm}(a,b)$ denotes their least common multiple?
$\textbf{(A)}\ 0\qquad\textbf{(B)}\ 2\qquad\textbf{(C)}\ 4\qquad\textbf{(D)}\ 6\qquad\textbf{(E)}\ 8$
Suppose that $a_0, a_1, \cdots $ and $b_0, b_1, \cdots$ are two sequences of positive integers such that $a_0, b_0 \ge 2$ and \[ a_{n+1} = \gcd{(a_n, b_n)} + 1, \qquad b_{n+1} = \operatorname{lcm}{(a_n, b_n)} - 1. \] Show that the sequence $a_n$ is eventually periodic; in other words, there exist integers $N \ge 0$ and $t > 0$ such that $a_{n+t} = a_n$ for all $n \ge N$.
Find the sum of the greatest common factor and the least common multiple of $12$ and $18$.
What is the largest possible value of the expression $$gcd \,\,\, (n^2 + 3, (n + 1)^2 + 3 )$$ for naturals $n$?
[hide]original wording]Kāda ir izteiksmes LKD (n2 + 3, (n + 1)2 + 3) lielākā iespējamā vērtība naturāliem n? [/hide]
Let $ A$ be a subset of the set $ \{1, 2,\ldots,2006\}$, consisting of $ 1004$ elements.
Prove that there exist $ 3$ distinct numbers $ a,b,c\in A$ such that $ gcd(a,b)$:
a) divides $ c$
b) doesn't divide $ c$
Nadya has $2022$ cards, each with a number one or seven written on it. It is known that there are both cards.Nadya looked at all possible $2022$-digit numbers that can be composed from all these cards. What is the largest value that can take the greatest common divisor of all these numbers?
For each positive integer $n$, define \[g(n) = \gcd\left\{0! n!, 1! (n-1)!, 2 (n-2)!, \ldots, k!(n-k)!, \ldots, n! 0!\right\}.\] Find the sum of all $n \leq 25$ for which $g(n) = g(n+1)$.
Find all pairs of integers $(a,b)$ such that $a^2+ab+1\mid b^2+ab+a+b-1$.
Find all Arithmetic progressions $a_{1},a_{2},...$ of natural numbers for which there exists natural number $N>1$ such that for every $k\in \mathbb{N}$:
$a_{1}a_{2}...a_{k}\mid a_{N+1}a_{N+2}...a_{N+k}$
Let $\mathbb{Z}_{>0}$ denote the set of positive integers. For any positive integer $k$, a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is called [i]$k$-good[/i] if $\gcd(f(m) + n, f(n) + m) \le k$ for all $m \neq n$. Find all $k$ such that there exists a $k$-good function.
[i]Proposed by James Rickards, Canada[/i]
We color numbers $1,2,3,...,20$ in two colors, blue and yellow, such that both colors are used (not all numbers are colored in one color). Determine number of ways we can color those numbers, such that product of all blue numbers and product of all yellow numbers have greatest common divisor $1$.
Let us consider a set $S = \{ a_1 < a_2 < \ldots < a_{2004}\}$, satisfying the following properties: $f(a_i) < 2003$ and $f(a_i) = f(a_j) \quad \forall i, j$ from $\{1, 2,\ldots , 2004\}$, where $f(a_i)$ denotes number of elements which are relatively prime with $a_i$. Find the least positive integer $k$ for which in every $k$-subset of $S$, having the above mentioned properties there are two distinct elements with greatest common divisor greater than 1.
Let $m,n$ be natural numbers and let $d = gcd(m,n)$. Let $x = 2^{m} -1$ and $y= 2^n +1$
(a) If $\frac{m}{d}$ is odd, prove that $gcd(x,y) = 1$
(b) If $\frac{m}{d}$ is even, Find $gcd(x,y)$
Determine the greatest common divisor of the numbers:
$$5^5-5, 7^7-7, 9^9-9 ,..., 2017^{2017}-2017,$$
Let $n$ be a positive integer. Prove that there exist polynomials$f(x)$and $g(x$) with integer coefficients such that
\[f(x)\left(x + 1 \right)^{2^n}+ g(x) \left(x^{2^n}+ 1 \right) = 2.\]
The function $f$ from the set $\mathbb{N}$ of positive integers into itself is defined by the equality \[f(n)=\sum_{k=1}^{n} \gcd(k,n),\qquad n\in \mathbb{N}.\]
a) Prove that $f(mn)=f(m)f(n)$ for every two relatively prime ${m,n\in\mathbb{N}}$.
b) Prove that for each $a\in\mathbb{N}$ the equation $f(x)=ax$ has a solution.
c) Find all ${a\in\mathbb{N}}$ such that the equation $f(x)=ax$ has a unique solution.
Alice and Bob are playing a guessing game. Bob is thinking of a number n of the form $2^a3^b$, where a and b are positive integers between $ 1$ and $2020$, inclusive. Each turn, Alice guess a number m, and Bob will tell her either $\gcd (m, n)$ or $lcm (m, n)$ (letting her know that he is saying that $gcd$ or $lcm$), as well as whether any of the respective powers match up in their prime factorization. In particular, if $m = n$, Bob will let Alice know this, and the game is over. Determine the smallest number $k$ so that Alice is always able to find $n$ within $k$ guesses, regardless of Bob’s number or choice of revealing either the $lcm$, or the $gcd$ .
Prove that the equation $3y^2 = x^4 + x$ has no positive integer solutions.
Let $A,B,C$ be $3$ points on the plane with integral coordinates. Prove that there exists a point $P$ with integral coordinates distinct from $A,B$ and $C$ such that the interiors of the segments $PA,PB$ and $PC$ do not contain points with integral coordinates.
Consider the triangular array of numbers with $0,1,2,3,...$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows $1$ through $6$ are shown.
\begin{tabular}{ccccccccccc} & & & & & 0 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 2 & & 2 & & 2 & & & \\ & & 3 & & 4 & & 4 & & 3 & & \\ & 4 & & 7 & & 8 & & 7 & & 4 & \\ 5 & & 11 & & 15 & & 15 & & 11 & & 5 \end{tabular}
Let $f(n)$ denote the sum of the numbers in row $n$. What is the remainder when $f(100)$ is divided by $100$?
$\textbf{(A)}\ 12\qquad
\textbf{(B)}\ 30 \qquad
\textbf{(C)}\ 50 \qquad
\textbf{(D)}\ 62 \qquad
\textbf{(E)}\ 74$
Let $k>2$ be a positive integer. Elise and Xavier play a game that has four steps, in this order.
[list=1]
[*]Elise picks $2$ nonzero digits $(1-9)$, called $e$ and $f$.
[*]Xavier then picks $k$ nonzero digits $(1-9)$, called $x_1,\cdots,x_k$.
[*]Elise picks any positive integer $d$.
[*]Xaiver picks an integer $b>10$.[/list]
Each player's choices are known to the other player when the choices are made.
The winner is determined as follows. Elise writes down the two-digit base $b$ number $ef_b$. Next, Xavier writes the $k$-digit base $b$ number that is constructed by concatenating his digits,
\[(x_1\cdots x_k)_b.\]
They then compute the greatest common divisor (gcd) of these two numbers. If this gcd is greater than or equal to the integer $d$ then Xavier wins. Otherwise Elise wins.
(As an example game for $k=3$, Elise chooses the digits $(e, f) = (2, 4)$, Xavier chooses $(4, 4, 8)$, and then Elise picks $d = 100$. Xavier picks base $b = 25$. The base-25 numbers $2425$ and $44825$ are, respectively, equal to $54$ and $2608$. The greatest common divisor of these two is $2$, which is much less than $100$, so Elise wins handily.)
Find all $k$ for which Xavier can force a win, no matter how Elise plays.
Determine all pairs $(n,m)$ of positive integers for which there exists an infinite sequence $\{x_k\}$ of $0$'s and $1$'s with the properties that if $x_i=0$ then $x_{i+m}=1$ and if $x_i = 1$ then $x_{i+n} = 0.$
There are 2010 boxes labeled $B_1,B_2,\dots,B_{2010},$ and $2010n$ balls have been distributed among them, for some positive integer $n.$ You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving [i]exactly[/i] $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?