Olympiad problems

2020 Estonia Team Selection Test, 1

For every positive integer $x$, let $k(x)$ denote the number of composite numbers that do not exceed $x$. Find all positive integers $n$ for which $(k (n))! $ lcm $(1, 2,..., n)> (n - 1) !$ .

2006 Stanford Mathematics Tournament, 16

Tags: number theory , least common multiple

Points $ A_1$, $ A_2$, $ ...$ are placed on a circle with center $ O$ such that $ \angle OA_n A_{n\plus{}1}\equal{}35^\circ$ and $ A_n\neq A_{n\plus{}2}$ for all positive integers $ n$. What is the smallest $ n>1$ for which $ A_n\equal{}A_1$?

1994 AMC 8, 1

Tags: least common multiple

Which of the following is the largest? $\text{(A)}\ \dfrac{1}{3} \qquad \text{(B)}\ \dfrac{1}{4} \qquad \text{(C)}\ \dfrac{3}{8} \qquad \text{(D)}\ \dfrac{5}{12} \qquad \text{(E)}\ \dfrac{7}{24}$

2011 Kyiv Mathematical Festival, 1

Tags: greatest common divisor , least common multiple , number theory

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$.

2008 India Regional Mathematical Olympiad, 2

Tags: number theory , least common multiple , inequalities , algorithm

Prove that there exist two infinite sequences $ \{a_n\}_{n\ge 1}$ and $ \{b_n\}_{n\ge 1}$ of positive integers such that the following conditions hold simultaneously: $ (i)$ $ 0 < a_1 < a_2 < a_3 < \cdots$; $ (ii)$ $ a_n < b_n < a_n^2$, for all $ n\ge 1$; $ (iii)$ $ a_n \minus{} 1$ divides $ b_n \minus{} 1$, for all $ n\ge 1$ $ (iv)$ $ a_n^2 \minus{} 1$ divides $ b_n^2 \minus{} 1$, for all $ n\ge 1$ [19 points out of 100 for the 6 problems]

2010 Indonesia TST, 3

Tags: least common multiple , function , relatively prime , number theory

For every natural number $ n $, define $ s(n) $ as the smallest natural number so that for every natural number $ a $ relatively prime to $n$, this equation holds: \[ a^{s(n)} \equiv 1 (mod n) \] Find all natural numbers $ n $ such that $ s(n) = 2010 $

2014 Contests, 1

Tags: modular arithmetic , greatest common divisor , least common multiple , relatively prime , number theory

Four consecutive three-digit numbers are divided respectively by four consecutive two-digit numbers. What minimum number of different remainders can be obtained? [i](A. Golovanov)[/i]

1989 IMO Shortlist, 27

Tags: modular arithmetic , number theory , least common multiple , divisibility

Let $ m$ be a positive odd integer, $ m > 2.$ Find the smallest positive integer $ n$ such that $ 2^{1989}$ divides $ m^n \minus{} 1.$

1982 IMO Longlists, 1

Tags: induction , least common multiple , number theory

[b](a)[/b] Prove that $\frac{1}{n+1} \cdot \binom{2n}{n}$ is an integer for $n \geq 0.$ [b](b)[/b] Given a positive integer $k$, determine the smallest integer $C_k$ with the property that $\frac{C_k}{n+k+1} \cdot \binom{2n}{n}$ is an integer for all $n \geq k.$

2005 China Girls Math Olympiad, 4

Tags: number theory , least common multiple , ceiling function , combinatorics

Determine all positive real numbers $ a$ such that there exists a positive integer $ n$ and sets $ A_1, A_2, \ldots, A_n$ satisfying the following conditions: (1) every set $ A_i$ has infinitely many elements; (2) every pair of distinct sets $ A_i$ and $ A_j$ do not share any common element (3) the union of sets $ A_1, A_2, \ldots, A_n$ is the set of all integers; (4) for every set $ A_i,$ the positive difference of any pair of elements in $ A_i$ is at least $ a^i.$

1995 Tournament Of Towns, (464) 2

Tags: least common multiple , number theory

Do there exist $100$ positive integers such that their sum is equal to their least common multiple? (S Tokarev)

1994 All-Russian Olympiad, 5

Tags: least common multiple , inequality , number theory

Prove that, for any natural numbers $k,m,n$: $[k,m] \cdot [m,n] \cdot [n,k] \ge [k,m,n]^2$

2011 Cuba MO, 7

Tags: number theory , lcm , least common multiple

Find a set of positive integers with the greatest possible number of elements such that the least common multiple of all of them is less than $2011$.

2003 Germany Team Selection Test, 3

Tags: floor function , inequalities , least common multiple , ceiling function , number theory

Let $N$ be a natural number and $x_1, \ldots , x_n$ further natural numbers less than $N$ and such that the least common multiple of any two of these $n$ numbers is greater than $N$. Prove that the sum of the reciprocals of these $n$ numbers is always less than $2$: $\sum^n_{i=1} \frac{1}{x_i} < 2.$

2017 CMIMC Number Theory, 2

Tags: number theory , greatest common divisor , least common multiple

Determine all possible values of $m+n$, where $m$ and $n$ are positive integers satisfying \[\operatorname{lcm}(m,n) - \gcd(m,n) = 103.\]

1959 AMC 12/AHSME, 42

Tags: number theory , relatively prime , greatest common divisor , least common multiple

Given three positive integers $a,b,$ and $c$. Their greatest common divisor is $D$; their least common multiple is $m$. Then, which two of the following statements are true? $ \text{(1)}\ \text{the product MD cannot be less than abc} \qquad$ $\text{(2)}\ \text{the product MD cannot be greater than abc}\qquad$ $\text{(3)}\ \text{MD equals abc if and only if a,b,c are each prime}\qquad$ $\text{(4)}\ \text{MD equals abc if and only if a,b,c are each relatively prime in pairs}$ $\text{ (This means: no two have a common factor greater than 1.)}$ $ \textbf{(A)}\ 1,2 \qquad\textbf{(B)}\ 1,3\qquad\textbf{(C)}\ 1,4\qquad\textbf{(D)}\ 2,3\qquad\textbf{(E)}\ 2,4 $

1989 AMC 8, 2

Tags: number theory , least common multiple

$\frac{2}{10}+\frac{4}{100}+\frac{6}{1000} =$ $\text{(A)}\ .012 \qquad \text{(B)}\ .0246 \qquad \text{(C)}\ .12 \qquad \text{(D)}\ .246 \qquad \text{(E)}\ 246$

2013 Korea National Olympiad, 5

Tags: greatest common divisor , least common multiple , function , number theory

Find all functions $f : \mathbb{N} \rightarrow \mathbb{N} $ satisfying \[ f(mn) = \operatorname{lcm} (m,n) \cdot \gcd( f(m), f(n) ) \] for all positive integer $m,n$.

2009 Romanian Master of Mathematics, 1

Tags: floor function , inequalities , number theory , greatest common divisor , least common multiple , triangle inequality , algebra

For $ a_i \in \mathbb{Z}^ \plus{}$, $ i \equal{} 1, \ldots, k$, and $ n \equal{} \sum^k_{i \equal{} 1} a_i$, let $ d \equal{} \gcd(a_1, \ldots, a_k)$ denote the greatest common divisor of $ a_1, \ldots, a_k$. Prove that $ \frac {d} {n} \cdot \frac {n!}{\prod\limits^k_{i \equal{} 1} (a_i!)}$ is an integer. [i]Dan Schwarz, Romania[/i]

2001 ITAMO, 4

Tags: least common multiple , number theory

A positive integer is called [i]monotone[/i] if has at least two digits and all its digits are nonzero and appear in a strictly increasing or strictly decreasing order. (a) Compute the sum of all monotone five-digit numbers. (b) Find the number of final zeros in the least common multiple of all monotone numbers (with any number of digits).

2020 China Team Selection Test, 3

Tags: number theory , algebra , least common multiple

For a non-empty finite set $A$ of positive integers, let $\text{lcm}(A)$ denote the least common multiple of elements in $A$, and let $d(A)$ denote the number of prime factors of $\text{lcm}(A)$ (counting multiplicity). Given a finite set $S$ of positive integers, and $$f_S(x)=\sum_{\emptyset \neq A \subset S} \frac{(-1)^{|A|} x^{d(A)}}{\text{lcm}(A)}.$$ Prove that, if $0 \le x \le 2$, then $-1 \le f_S(x) \le 0$.

2003 Iran MO (3rd Round), 8

Tags: induction , least common multiple , arithmetic sequence , number theory

A positive integer $n$ is said to be a [i]perfect power[/i] if $n=a^b$ for some integers $a,b$ with $b>1$. $(\text{a})$ Find $2004$ perfect powers in arithmetic progression. $(\text{b})$ Prove that perfect powers cannot form an infinite arithmetic progression.

2023 AMC 12/AHSME, 24

Tags: number theory , least common multiple , greatest common divisor

Integers $a, b, c, d$ satisfy the following: $abcd=2^6\cdot 3^9\cdot 5^7$ $\text{lcm}(a,b)=2^3\cdot 3^2\cdot 5^3$ $\text{lcm}(a,c)=2^3\cdot 3^3\cdot 5^3$ $\text{lcm}(a,d)=2^3\cdot 3^3\cdot 5^3$ $\text{lcm}(b,c)=2^1\cdot 3^3\cdot 5^2$ $\text{lcm}(b,d)=2^2\cdot 3^3\cdot 5^2$ $\text{lcm}(c,d)=2^2\cdot 3^3\cdot 5^2$ Find $\text{gcd}(a,b,c,d)$ $\textbf{(A)}~30\qquad\textbf{(B)}~45\qquad\textbf{(C)}~3\qquad\textbf{(D)}~15\qquad\textbf{(E)}~6$

2021 Bangladeshi National Mathematical Olympiad, 2

Tags: number theory , greatest common divisor , least common multiple

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)}$.

2003 Flanders Math Olympiad, 4

Tags: analytic geometry , parameterization , number theory , least common multiple , ratio , calculus , integration

Consider all points with integer coordinates in the carthesian plane. If one draws a circle with M(0,0) and a well-chose radius r, the circles goes through some of those points. (like circle with $r=2\sqrt2$ goes through 4 points) Prove that $\forall n\in \mathbb{N}, \exists r$ so that the circle with midpoint 0,0 and radius $r$ goes through at least $n$ points.