This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 583

2012 Portugal MO, 3
Tags: greatest common divisor , combinatorics , floor function , ceiling function , number theory
Isabel wants to partition the set $\mathbb{N}$ of the positive integers into $n$ disjoint sets $A_{1}, A_{2}, \ldots, A_{n}$. Suppose that for each $i$ with $1\leq i\leq n$, given any positive integers $r, s\in A_{i}$ with $r\neq s$, we have $r+s\in A_{i}$. If $|A_{j}|=1$ for some $j$, find the greatest positive integer that may belong to $A_{j}$.

2007 USA Team Selection Test, 3
Tags: algebra , polynomial , algorithm , greatest common divisor , trigonometry , induction , number theory
Let $ \theta$ be an angle in the interval $ (0,\pi/2)$. Given that $ \cos \theta$ is irrational, and that $ \cos k \theta$ and $ \cos[(k \plus{} 1)\theta ]$ are both rational for some positive integer $ k$, show that $ \theta \equal{} \pi/6$.

2013 Gulf Math Olympiad, 4
Tags: number theory , greatest common divisor
Let $m,n$ be integers. It is known that there are integers $a,b$ such that $am+bn=1$ if, and only if, the greatest common divisor of $m,n$ is 1. [i]You are not required to prove this[/i]. Now suppose that $p,q$ are different odd primes. In each case determine if there are integers $a,b$ such that $ap+bq=1$ so that the given condition is satisfied: [list] a. $p$ divides $b$ and $q$ divides $a$; b. $p$ divides $a$ and $q$ divides $b$; c. $p$ does not divide $a$ and $q$ does not divide $b$. [/list]

2010 Tournament Of Towns, 5
Tags: number theory , greatest common divisor , mathcamp , least common multiple , linear algebra , matrix
$33$ horsemen are riding in the same direction along a circular road. Their speeds are constant and pairwise distinct. There is a single point on the road where the horsemen can surpass one another. Can they ride in this fashion for arbitrarily long time ?

2008 ISI B.Math Entrance Exam, 10
Tags: greatest common divisor , number theory
If $p$ is a prime number and $a>1$ is a natural number , then show that the greatest common divisor of the two numbers $a-1$ and $\frac{a^p-1}{a-1}$ is either $1$ or $p$ .

2009 USAMO, 6
Tags: number theory , greatest common divisor
Let $s_1, s_2, s_3, \dots$ be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that $s_1 = s_2 = s_3 = \dots.$ Suppose that $t_1, t_2, t_3, \dots$ is also an infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$ is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that $(s_i - s_j)r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.

2015 China Team Selection Test, 3
Tags: greatest common divisor , number theory , modular arithmetic
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.

2007 Tournament Of Towns, 1
Tags: least common multiple , greatest common divisor
[b](a)[/b] Each of Peter and Basil thinks of three positive integers. For each pair of his numbers, Peter writes down the greatest common divisor of the two numbers. For each pair of his numbers, Basil writes down the least common multiple of the two numbers. If both Peter and Basil write down the same three numbers, prove that these three numbers are equal to each other. [b](b)[/b] Can the analogous result be proved if each of Peter and Basil thinks of four positive integers instead?

1966 Dutch Mathematical Olympiad, 2
Tags: greatest common divisor , gcd , recurrence relation , number theory
For all $n$, $t_{n+1} = 2(t_n)^2 - 1$. Prove that gcd $(t_n,t_m) = 1$ if $n \ne m$.

2012 JBMO ShortLists, 5
Tags: greatest common divisor , algebra , number theory , modular arithmetic
Find all positive integers $x,y,z$ and $t$ such that $2^x3^y+5^z=7^t$.

2002 Bosnia Herzegovina Team Selection Test, 3
Tags: greatest common divisor , relatively prime , modular arithmetic , divisibility theory , number theory
If $n$ is a natural number, prove that the number $(n+1)(n+2)\cdots(n+10)$ is not a perfect square.

2019 Romania Team Selection Test, 2
Tags: greatest common divisor , algebra , number theory , modular arithmetic , polynomial
Find all pairs of integers $(m,n)$ such that $m^6 = n^{n+1} + n -1$.

2007 Serbia National Math Olympiad, 3
Tags: greatest common divisor , quadratic , number theory , modular arithmetic , inequalities
Determine all pairs of natural numbers $(x; n)$ that satisfy the equation \[x^{3}+2x+1 = 2^{n}.\]

2017 CMIMC Number Theory, 2
Tags: least common multiple , greatest common divisor , number theory
Determine all possible values of $m+n$, where $m$ and $n$ are positive integers satisfying \[\operatorname{lcm}(m,n) - \gcd(m,n) = 103.\]

2004 Postal Coaching, 14
Tags: number theory , greatest common divisor
Find the greatest common divisor of all number in the set $( a^{41} - a | a \in \mathbb{N} and \geq 2 )$ . What is your guess if 41 is replaced by a natural number $n$

PEN R Problems, 10
Tags: analytic geometry , greatest common divisor , the geometry of numbers , geometry , number theory
Prove that if a lattice triangle has no lattice points on its boundary in addition to its vertices, and one point in its interior, then this interior point is its center of gravity.

2017 China Team Selection Test, 5
Tags: greatest common divisor , number theory
Show that there exists a positive real $C$ such that for any naturals $H,N$ satisfying $H \geq 3, N \geq e^{CH}$, for any subset of $\{1,2,\ldots,N\}$ with size $\lceil \frac{CHN}{\ln N} \rceil$, one can find $H$ naturals in it such that the greatest common divisor of any two elements is the greatest common divisor of all $H$ elements.

2014 India PRMO, 11
Tags: greatest common divisor , number theory
For natural numbers $x$ and $y$, let $(x,y)$ denote the greatest common divisor of $x$ and $y$. How many pairs of natural numbers $x$ and $y$ with $x \le y$ satisfy the equation $xy = x + y + (x, y)$?

2016 Iran Team Selection Test, 2
Tags: combinatorics , greatest common divisor
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.

2015 IMO Shortlist, N7
Tags: greatest common divisor , function , number theory
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]

2014 Contests, 1
Tags: function , polynomial , greatest common divisor , algebra , number theory
Let $f : \mathbb{Z} \rightarrow \mathbb{Z}^+$ be a function, and define $h : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}^+$ by $h(x, y) = \gcd (f(x), f(y))$. If $h(x, y)$ is a two-variable polynomial in $x$ and $y$, prove that it must be constant.

2016 Indonesia TST, 5
Tags: combinatorics , greatest common divisor
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.

2011 Saint Petersburg Mathematical Olympiad, 2
Tags: greatest common divisor , least common multiple , number theory
$a,b$ are naturals and $$a \times GCD(a,b)+b \times LCM(a,b)<2.5 ab$$. Prove that $b|a$

2009 Saint Petersburg Mathematical Olympiad, 1
Tags: greatest common divisor , number theory
$x,y$ are naturals. $GCM(x^7,y^4)*GCM(x^8,y^5)=xy$ Prove that $xy$ is cube

2006 Estonia Math Open Senior Contests, 4
Tags: algorithm , greatest common divisor , combinatorics
Martin invented the following algorithm. Let two irreducible fractions $ \frac{s_1}{t_1}$ and $ \frac{s_2}{t_2}$ be given as inputs, with the numerators and denominators being positive integers. Divide $ s_1$ and $ s_2$ by their greatest common divisor $ c$ and obtain $ a_1$ and $ a_2$, respectively. Similarily, divide $ t_1$ and $ t_2$ by their greatest common divisor $ d$ and obtain $ b_1$ and $ b_2$, respectively. After that, form a new fraction $ \frac{a_1b_2 \plus{} a_2b_1}{t_1b_2}$, reduce it, and multiply the numerator of the result by $ c$. Martin claims that this algorithm always finds the sum of the original fractions as an irreducible fraction. Is his claim correct?