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: 2008

2007 National Olympiad First Round, 2
Tags: modular arithmetic
What is the last three digits of base-4 representation of $10\cdot 3^{195}\cdot 49^{49}$? $ \textbf{(A)}\ 112 \qquad\textbf{(B)}\ 130 \qquad\textbf{(C)}\ 132 \qquad\textbf{(D)}\ 212 \qquad\textbf{(E)}\ 232 $

2003 IMO Shortlist, 6
Tags: modular arithmetic , combinatorics , decimal representation , counting , function
Let $f(k)$ be the number of integers $n$ satisfying the following conditions: (i) $0\leq n < 10^k$ so $n$ has exactly $k$ digits (in decimal notation), with leading zeroes allowed; (ii) the digits of $n$ can be permuted in such a way that they yield an integer divisible by $11$. Prove that $f(2m) = 10f(2m-1)$ for every positive integer $m$. [i]Proposed by Dirk Laurie, South Africa[/i]

2021 China Team Selection Test, 4
Tags: algebra , polynomial , number theory , modular arithmetic
Let $f(x),g(x)$ be two polynomials with integer coefficients. It is known that for infinitely many prime $p$, there exist integer $m_p$ such that $$f(a) \equiv g(a+m_p) \pmod p$$ holds for all $a \in \mathbb{Z}.$ Prove that there exists a rational number $r$ such that $$f(x)=g(x+r).$$

2012 Brazil National Olympiad, 3
Tags: modular arithmetic , induction , number theory
Find the least non-negative integer $n$ such that exists a non-negative integer $k$ such that the last 2012 decimal digits of $n^k$ are all $1$'s.

2013 Romanian Master of Mathematics, 1
Tags: floor function , modular arithmetic , quadratic , number theory
For a positive integer $a$, define a sequence of integers $x_1,x_2,\ldots$ by letting $x_1=a$ and $x_{n+1}=2x_n+1$ for $n\geq 1$. Let $y_n=2^{x_n}-1$. Determine the largest possible $k$ such that, for some positive integer $a$, the numbers $y_1,\ldots,y_k$ are all prime.

2014 Contests, 2
Tags: modular arithmetic , number theory
Find all all positive integers x,y,and z satisfying the equation $x^3=3^y7^z+8$

2007 QEDMO 5th, 1
Tags: modular arithmetic
Let $ a$, $ b$ and $ k$ be three positive integers. We define two sequences $ \left( a_{n}\right)$ and $ \left( b_{n}\right)$ by the starting values $ a_{1}\equal{}a$ and $ b_{1}\equal{}b$ and the recurrent equations $ a_{n\plus{}1}\equal{}ka_{n}\plus{}b_{n}$ and $ b_{n\plus{}1}\equal{}kb_{n}\plus{}a_{n}$ for each positive integer $ n$. Prove that if $ a_{1}\perp b_{1}$, $ a_{2}\perp b_{2}$ and $ a_{3}\perp b_{3}$ hold, then $ a_{n}\perp b_{n}$ holds for every positive integer $ n$. Here, the abbreviation $ x\perp y$ stands for "the numbers $ x$ and $ y$ are coprime".

2007 ITest, 29
Tags: modular arithmetic
Let $S$ be equal to the sum \[1+2+3+\cdots+2007.\] Find the remainder when $S$ is divided by $1000$.

2007 ITAMO, 2
Tags: polynomial , modular arithmetic , algebra
We define two polynomials with integer coefficients P,Q to be similar if the coefficients of P are a permutation of the coefficients of Q. a) if P,Q are similar, then $P(2007)-Q(2007)$ is even b) does there exist an integer $k > 2$ such that $k \mid P(2007)-Q(2007)$ for all similar polynomials P,Q?

2001 Romania Team Selection Test, 1
Tags: modular arithmetic , number theory , polynomial congruence
Find all pairs $\left(m,n\right)$ of positive integers, with $m,n\geq2$, such that $a^n-1$ is divisible by $m$ for each $a\in \left\{1,2,3,\ldots,n\right\}$.

2009 Miklós Schweitzer, 2
Tags: modular arithmetic , number theory , prime number , combinatorics
Let $ p_1,\dots,p_k$ be prime numbers, and let $ S$ be the set of those integers whose all prime divisors are among $ p_1,\dots,p_k$. For a finite subset $ A$ of the integers let us denote by $ \mathcal G(A)$ the graph whose vertices are the elements of $ A$, and the edges are those pairs $ a,b\in A$ for which $ a \minus{} b\in S$. Does there exist for all $ m\geq 3$ an $ m$-element subset $ A$ of the integers such that (i) $ \mathcal G(A)$ is complete? (ii) $ \mathcal G(A)$ is connected, but all vertices have degree at most 2?

2006 Taiwan TST Round 1, 3
Tags: modular arithmetic , number theory , divisibility , chinese remainder theorem
Let $a$, $b$ be positive integers such that $b^n+n$ is a multiple of $a^n+n$ for all positive integers $n$. Prove that $a=b$. [i]Proposed by Mohsen Jamali, Iran[/i]

MathLinks Contest 7th, 7.1
Tags: modular arithmetic , quadratic , vieta , number theory , relatively prime , algebra
Find all pairs of positive integers $ a,b$ such that \begin{align*} b^2 + b+ 1 & \equiv 0 \pmod a \\ a^2+a+1 &\equiv 0 \pmod b . \end{align*}

2002 ITAMO, 1
Tags: modular arithmetic , number theory
Find all $3$-digit positive integers that are $34$ times the sum of their digits.

2012 Spain Mathematical Olympiad, 1
Tags: modular arithmetic , inequalities , number theory
Find all positive integers $n$ and $k$ such that $(n+1)^n=2n^k+3n+1$.

2004 Vietnam National Olympiad, 3
Tags: calculus , integration , quadratic , modular arithmetic , number theory
Let $ S(n)$ be the sum of decimal digits of a natural number $ n$. Find the least value of $ S(m)$ if $ m$ is an integral multiple of $ 2003$.

2005 Taiwan TST Round 3, 3
Tags: modular arithmetic , number theory , divisibility , remainder
Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$. [i]Proposed by John Murray, Ireland[/i]

2010 IMO Shortlist, 7
Tags: number theory , modular arithmetic , combinatorics , arithmetic sequence , sequence
Let $P_1, \ldots , P_s$ be arithmetic progressions of integers, the following conditions being satisfied: [b](i)[/b] each integer belongs to at least one of them; [b](ii)[/b] each progression contains a number which does not belong to other progressions. Denote by $n$ the least common multiple of the ratios of these progressions; let $n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ its prime factorization. Prove that \[s \geq 1 + \sum^k_{i=1} \alpha_i (p_i - 1).\] [i]Proposed by Dierk Schleicher, Germany[/i]

2006 Germany Team Selection Test, 2
Tags: modular arithmetic , invariant , combinatorics
There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n \minus{} 1$ is not divisible by $ 3$. [i]Proposed by Dusan Dukic, Serbia[/i]

2016 Iran MO (3rd Round), 3
Tags: modular arithmetic , combinatorics , table , coloring
A $30\times30$ table is given. We want to color some of it's unit squares such that any colored square has at most $k$ neighbors. ( Two squares $(i,j)$ and $(x,y)$ are called neighbors if $i-x,j-y\equiv0,-1,1 \pmod {30}$ and $(i,j)\neq(x,y)$. Therefore, each square has exactly $8$ neighbors) What is the maximum possible number of colored squares if$:$ $a) k=6$ $b)k=1$

2008 Korea - Final Round, 4
Tags: modular arithmetic , number theory
For any positive integer $m\ge2$ define $A_m=\{m+1, 3m+2, 5m+3, 7m+4, \ldots, (2k-1)m + k, \ldots\}$. (1) For every $m\ge2$, prove that there exists a positive integer $a$ that satisfies $1\le a<m$ and $2^a\in A_m$ or $2^a+1\in A_m$. (2) For a certain $m\ge2$, let $a, b$ be positive integers that satisfy $2^a\in A_m$, $2^b+1\in A_m$. Let $a_0, b_0$ be the least such pair $a, b$. Find the relation between $a_0$ and $b_0$.

2001 IMO Shortlist, 2
Tags: modular arithmetic , combinatorics , factorial , global
Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$, define $S(a) = \sum_{i=1}^n c_i a_i$. Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$.

2014 BMO TST, 5
Tags: modular arithmetic , number theory
Find all non-negative integers $k,n$ which satisfy $2^{2k+1} + 9\cdot 2^k+5=n^2$.

2011 Ukraine Team Selection Test, 7
Tags: modular arithmetic , number theory , equation , lte lemma
Find all pairs $(m,n)$ of nonnegative integers for which \[m^2 + 2 \cdot 3^n = m\left(2^{n+1} - 1\right).\] [i]Proposed by Angelo Di Pasquale, Australia[/i]

2015 AIME Problems, 3
Tags: number theory , modular arithmetic
Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.