Olympiad problems

2003 France Team Selection Test, 2

A lattice point in the coordinate plane with origin $O$ is called invisible if the segment $OA$ contains a lattice point other than $O,A$. Let $L$ be a positive integer. Show that there exists a square with side length $L$ and sides parallel to the coordinate axes, such that all points in the square are invisible.

2011 Federal Competition For Advanced Students, Part 1, 1

Tags: calculus , modular arithmetic , integration , quadratic , prime factorization , number theory

Determine all integer triplets $(x,y,z)$ such that \[x^4+x^2=7^zy^2\mbox{.}\]

2006 Estonia National Olympiad, 3

Tags: number theory , modular arithmetic

Prove or disprove the following statements. a) For every integer $ n \ge 3$, there exist $ n$ pairwise distinct positive integers such that the product of any two of them is divisible by the sum of the remaining $ n \minus{} 2$ numbers. b) For some integer $ n \ge 3$, there exist $ n$ pairwise distinct positive integers, such that the sum of any $ n \minus{} 2$ of them is divisible by the product of the remaining two numbers.

PEN A Problems, 37

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

If $n$ is a natural number, prove that the number $(n+1)(n+2)\cdots(n+10)$ is not a perfect square.

1998 Nordic, 4

Tags: modular arithmetic , binomial coefficient , combinatorics

Let $n$ be a positive integer. Count the number of numbers $k \in \{0, 1, 2, . . . , n\}$ such that $\binom{n}{k}$ is odd. Show that this number is a power of two, i.e. of the form $2^p$ for some nonnegative integer $p$.

2024 Nigerian MO Round 3, Problem 1

Tags: number theory , algebra , mod , modular arithmetic

Find the value of $$(2^{40}+12^{41}+23^{42}+67^{43}+87^{44})^{45!+46}\mod11$$ (variation but same answer) [hide=Answer]3[/hide]

2021 Bolivia Ibero TST, 3

Tags: modular arithmetic , number theory , prime number

Let $p=ab+bc+ac$ be a prime number where $a,b,c$ are different two by two, show that $a^3,b^3,c^3$ gives different residues modulo $p$

2014 Online Math Open Problems, 23

Tags: number theory , modular arithmetic , greatest common divisor , quadratic , law of cosines

For a prime $q$, let $\Phi_q(x)=x^{q-1}+x^{q-2}+\cdots+x+1$. Find the sum of all primes $p$ such that $3 \le p \le 100$ and there exists an odd prime $q$ and a positive integer $N$ satisfying \[\dbinom{N}{\Phi_q(p)}\equiv \dbinom{2\Phi_q(p)}{N} \not \equiv 0 \pmod p. \][i]Proposed by Sammy Luo[/i]

2017 South East Mathematical Olympiad, 3

Tags: modular arithmetic , number theory

For any positive integer $n$, let $D_n$ denote the set of all positive divisors of $n$, and let $f_i(n)$ denote the size of the set $$F_i(n) = \{a \in D_n | a \equiv i \pmod{4} \}$$ where $i = 1, 2$. Determine the smallest positive integer $m$ such that $2f_1(m) - f_2(m) = 2017$.

2013 ELMO Shortlist, 8

Tags: number theory , modular arithmetic , algebra , counting , function , distinguishability , polynomial

We define the [i]Fibonacci sequence[/i] $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the [i]Stirling number of the second kind[/i] $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets. For every positive integer $n$, let $t_n = \sum_{k=1}^{n} S(n,k) F_k$. Let $p\ge7$ be a prime. Prove that \[ t_{n+p^{2p}-1} \equiv t_n \pmod{p} \] for all $n\ge1$. [i]Proposed by Victor Wang[/i]

1957 AMC 12/AHSME, 32

Tags: modular arithmetic , greatest common divisor , number theory

The largest of the following integers which divides each of the numbers of the sequence $ 1^5 \minus{} 1,\, 2^5 \minus{} 2,\, 3^5 \minus{} 3,\, \cdots, n^5 \minus{} n, \cdots$ is: $ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 60 \qquad \textbf{(C)}\ 15 \qquad \textbf{(D)}\ 120\qquad \textbf{(E)}\ 30$

PEN D Problems, 10

Tags: congruence , quadratic , modular arithmetic

Let $p$ be a prime number of the form $4k+1$. Suppose that $2p+1$ is prime. Show that there is no $k \in \mathbb{N}$ with $k<2p$ and $2^k \equiv 1 \; \pmod{2p+1}$.

2012 ELMO Shortlist, 5

Tags: modular arithmetic , quadratic , combinatorics

Form the infinite graph $A$ by taking the set of primes $p$ congruent to $1\pmod{4}$, and connecting $p$ and $q$ if they are quadratic residues modulo each other. Do the same for a graph $B$ with the primes $1\pmod{8}$. Show $A$ and $B$ are isomorphic to each other. [i]Linus Hamilton.[/i]

2012 All-Russian Olympiad, 1

Tags: modular arithmetic , number theory

Let $a_1,\ldots a_{11}$ be distinct positive integers, all at least $2$ and with sum $407$. Does there exist an integer $n$ such that the sum of the $22$ remainders after the division of $n$ by $a_1,a_2,\ldots ,a_{11},4a_1,4a_2,\ldots ,4a_{11}$ is $2012$?

2005 AMC 10, 11

Tags: algebra , sequence , recursion , modular arithmetic

The first term of a sequence is 2005. Each succeeding term is the sum of the cubes of the digits of the previous terms. What is the 2005th term of the sequence? $ \textbf{(A)}\ 29\qquad \textbf{(B)}\ 55\qquad \textbf{(C)}\ 85\qquad \textbf{(D)}\ 133\qquad \textbf{(E)}\ 250$

2005 Georgia Team Selection Test, 6

Tags: modular arithmetic , number theory , combinatorics , induction

Let $ A$ be the subset of the set of positive integers, having the following $ 2$ properties: 1) If $ a$ belong to $ A$,than all of the divisors of $ a$ also belong to $ A$; 2) If $ a$ and $ b$, $ 1 < a < b$, belong to $ A$, than $ 1 \plus{} ab$ is also in $ A$; Prove that if $ A$ contains at least $ 3$ positive integers, than $ A$ contains all positive integers.

2008 ITest, 61

Tags: modular arithmetic , ceiling function

Find the units digit in the decimal expansion of \[\left(2008+\sqrt{4032000}\right)^{2000}+\left(2008+\sqrt{4032000}\right)^{2001}+\left(2008+\sqrt{4032000}\right)^{2002}+\]\[\cdots+\left(2008+\sqrt{4032000}\right)^{2007}+\left(2008+\sqrt{4032000}\right)^{2008}.\]

2008 IMS, 8

Tags: modular arithmetic , number theory

Find all natural numbers such that \[ n\sigma(n)\equiv 2\pmod {\phi( n)}\]

1996 IMO, 1

Tags: graph theory , modular arithmetic , combinatorics , rectangle

We are given a positive integer $ r$ and a rectangular board $ ABCD$ with dimensions $ AB \equal{} 20, BC \equal{} 12$. The rectangle is divided into a grid of $ 20 \times 12$ unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is $ \sqrt {r}$. The task is to find a sequence of moves leading from the square with $ A$ as a vertex to the square with $ B$ as a vertex. (a) Show that the task cannot be done if $ r$ is divisible by 2 or 3. (b) Prove that the task is possible when $ r \equal{} 73$. (c) Can the task be done when $ r \equal{} 97$?

2011 India IMO Training Camp, 2

Tags: number theory , modular arithmetic , 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]

2022 Moldova EGMO TST, 4

Tags: polynomial , algebra , modular arithmetic , abstract algebra

Prove that there exists an integer polynomial $P(X)$ such that $P(n)+4^n \equiv 0 \pmod {27}$. for all $n \geq 0$.

1999 Dutch Mathematical Olympiad, 2

Tags: modular arithmetic , geometry , rectangle

A $9 \times 9$ square consists of $81$ unit squares. Some of these unit squares are painted black, and the others are painted white, such that each $2 \times 3$ rectangle and each $3 \times 2$ rectangle contain exactly 2 black unit squares and 4 white unit squares. Determine the number of black unit squares.

2008 Czech-Polish-Slovak Match, 3

Tags: modular arithmetic , quadratic , prime number , number theory

Find all primes $p$ such that the expression \[\binom{p}1^2+\binom{p}2^2+\cdots+\binom{p}{p-1}^2\] is divisible by $p^3$.

2009 Belarus Team Selection Test, 2

Tags: modular arithmetic , number theory , sequence , divisibility

Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i \plus{} a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$. [i]Proposed by Mohsen Jamaali, Iran[/i]

1987 Romania Team Selection Test, 10

Tags: modular arithmetic , number theory , algebra , function , induction , polynomial

Let $a,b,c$ be integer numbers such that $(a+b+c) \mid (a^{2}+b^{2}+c^{2})$. Show that there exist infinitely many positive integers $n$ such that $(a+b+c) \mid (a^{n}+b^{n}+c^{n})$. [i]Laurentiu Panaitopol[/i]