Olympiad problems

2011 National Olympiad First Round, 10

How many interger tuples $(x,y,z)$ are there satisfying $0\leq x,y,z < 2011$, $xy+yz+zx \equiv 0 \pmod{2011}$, and $x+y+z \equiv 0 \pmod{2011}$ ? $\textbf{(A)}\ 2010 \qquad\textbf{(B)}\ 2011 \qquad\textbf{(C)}\ 2012 \qquad\textbf{(D)}\ 4021 \qquad\textbf{(E)}\ 4023$

2002 Moldova National Olympiad, 1

Tags: modular arithmetic

Find all triplets of primes in the form $ (p, 2p\plus{}1, 4p\plus{}1)$.

1997 Romania Team Selection Test, 2

Tags: number theory , divisibility , multiplicative nt , multiplicative order , modular arithmetic

Suppose that $A$ be the set of all positive integer that can write in form $a^2+2b^2$ (where $a,b\in\mathbb {Z}$ and $b$ is not equal to $0$). Show that if $p$ be a prime number and $p^2\in A$ then $p\in A$. [i]Marcel Tena[/i]

1974 IMO Longlists, 13

Tags: modular arithmetic

Prove that $2^{147} - 1$ is divisible by $343.$

2013 India Regional Mathematical Olympiad, 6

Tags: modular arithmetic , function , combinatorics

For a natural number $n$, let $T(n)$ denote the number of ways we can place $n$ objects of weights $1,2,\cdots, n$ on a balance such that the sum of the weights in each pan is the same. Prove that $T(100) > T(99)$.

2013 AMC 10, 25

Tags: search , modular arithmetic

Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer $S$. For example, if $N=749$, Bernardo writes the numbers 10,444 and 3,245, and LeRoy obtains the sum $S=13,689$. For how many choices of $N$ are the two rightmost digits of $S$, in order, the same as those of $2N$? ${ \textbf{(A)}\ 5\qquad\textbf{(B)}\ 10\qquad\textbf{(C)}\ 15\qquad\textbf{(D}}\ 20\qquad\textbf{(E)}\ 25 $

1985 ITAMO, 5

Tags: modular arithmetic

A sequence of integers $a_1$, $a_2$, $a_3$, $\ldots$ is chosen so that $a_n = a_{n - 1} - a_{n - 2}$ for each $n \ge 3$. What is the sum of the first 2001 terms of this sequence if the sum of the first 1492 terms is 1985, and the sum of the first 1985 terms is 1492?

1998 IMO Shortlist, 5

Tags: divisibility , number theory , modular arithmetic

Determine all positive integers $n$ for which there exists an integer $m$ such that ${2^{n}-1}$ is a divisor of ${m^{2}+9}$.

2011 USAJMO, 6

Tags: modular arithmetic

Consider the assertion that for each positive integer $n\geq2$, the remainder upon dividing $2^{2^n}$ by $2^n-1$ is a power of $4$. Either prove the assertion or find (with proof) a counterexample.

2009 Czech and Slovak Olympiad III A, 1

Tags: number theory , modular arithmetic

Knowing that the numbers $p, 3p+2, 5p+4, 7p+6, 9p+8$, and $11p+10$ are all primes, prove that $6p+11$ is a composite number.

2014 Tuymaada Olympiad, 1

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

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]

2008 Germany Team Selection Test, 2

Tags: modular arithmetic , triplets , counting , combinatorics

Find all positive integers $ n$ for which the numbers in the set $ S \equal{} \{1,2, \ldots,n \}$ can be colored red and blue, with the following condition being satisfied: The set $ S \times S \times S$ contains exactly $ 2007$ ordered triples $ \left(x, y, z\right)$ such that: [b](i)[/b] the numbers $ x$, $ y$, $ z$ are of the same color, and [b](ii)[/b] the number $ x \plus{} y \plus{} z$ is divisible by $ n$. [i]Author: Gerhard Wöginger, Netherlands[/i]

2007 Greece Junior Math Olympiad, 2

Tags: number theory , modular arithmetic

If $n$ is is an integer such that $4n+3$ is divisible by $11,$ find the form of $n$ and the remainder of $n^{4}$ upon division by $11$.

2000 Macedonia National Olympiad, 4

Tags: modular arithmetic , number theory

Let $a,b$ be coprime positive integers. Show that the number of positive integers $n$ for which the equation $ax+by=n$ has no positive integer solutions is equal to $\frac{(a-1)(b-1)}{2}-1$.

1974 IMO Shortlist, 6

Tags: summation , divisibility , binomial coefficient , number theory , modular arithmetic

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

1969 IMO Shortlist, 13

Tags: number theory , modular arithmetic , divisibility , additive number theory

$(CZS 2)$ Let $p$ be a prime odd number. Is it possible to find $p-1$ natural numbers $n + 1, n + 2, . . . , n + p -1$ such that the sum of the squares of these numbers is divisible by the sum of these numbers?

2011 ELMO Shortlist, 1

Tags: function , combinatorics , modular arithmetic

Let $S$ be a finite set, and let $F$ be a family of subsets of $S$ such that a) If $A\subseteq S$, then $A\in F$ if and only if $S\setminus A\notin F$; b) If $A\subseteq B\subseteq S$ and $B\in F$, then $A\in F$. Determine if there must exist a function $f:S\to\mathbb{R}$ such that for every $A\subseteq S$, $A\in F$ if and only if \[\sum_{s\in A}f(s)<\sum_{s\in S\setminus A}f(s).\] [i]Evan O'Dorney.[/i]

2013 Taiwan TST Round 1, 5

Tags: modular arithmetic , equation , number theory

An integer $a$ is called friendly if the equation $(m^2+n)(n^2+m)=a(m-n)^3$ has a solution over the positive integers. [b]a)[/b] Prove that there are at least $500$ friendly integers in the set $\{ 1,2,\ldots ,2012\}$. [b]b)[/b] Decide whether $a=2$ is friendly.

2010 USAMO, 5

Tags: partial fractions , modular arithmetic

Let $q = \frac{3p-5}{2}$ where $p$ is an odd prime, and let\[ S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)} \]Prove that if $\frac{1}{p}-2S_q = \frac{m}{n}$ for integers $m$ and $n$, then $m - n$ is divisible by $p$.

2010 Stars Of Mathematics, 1

Tags: combinatorics , modular arithmetic , floor function

Let $D$ be the set of all pairs $(i,j)$, $1\le i,j\le n$. Prove there exists a subset $S \subset D$, with $|S|\ge\left \lfloor\frac{3n(n+1)}{5}\right \rfloor$, such that for any $(x_1,y_1), (x_2,y_2) \in S$ we have $(x_1+x_2,y_1+y_2) \not \in S$. (Peter Cameron)

1994 Balkan MO, 2

Tags: calculus , integration , modular arithmetic , polynomial , algebra

Let $n$ be an integer. Prove that the polynomial $f(x)$ has at most one zero, where \[ f(x) = x^4 - 1994 x^3 + (1993+n)x^2 - 11x + n . \] [i]Greece[/i]

2014 India Regional Mathematical Olympiad, 6

Tags: inequalities , number theory , modular arithmetic

For any natural number, let $S(n)$ denote sum of digits of $n$. Find the number of $3$ digit numbers for which $S(S(n)) = 2$.

2014 NIMO Problems, 1

Tags: modular arithmetic , geometry , logarithm , 3d geometry , prime factorization , number theory , function

Let $\eta(m)$ be the product of all positive integers that divide $m$, including $1$ and $m$. If $\eta(\eta(\eta(10))) = 10^n$, compute $n$. [i]Proposed by Kevin Sun[/i]

2021 China Team Selection Test, 4

Tags: modular arithmetic , algebra , polynomial , number theory

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

2007 Greece National Olympiad, 1

Tags: quadratic , modular arithmetic

Find all positive integers $n$ such that $4^{n}+2007$ is a perfect square.