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

PEN J Problems, 6
Tags: divisor function , modular arithmetic , quadratic , number theory , relatively prime , prime factorization
Show that if $m$ and $n$ are relatively prime positive integers, then $\phi( 5^m -1) \neq 5^{n}-1$.

2010 Contests, 1
Tags: modular arithmetic , number theory
Find all $ 3$-digit numbers such that placing to the right side of the number its successor we get a $ 6$-digit number which is a perfect square.

Math Hour Olympiad, Grades 8-10, 2014.7
Tags: floor function , modular arithmetic
If $a$ is any number, $\lfloor a \rfloor$ is $a$ rounded down to the nearest integer. For example, $\lfloor \pi \rfloor =$ $3$. Show that the sequence $\lfloor \frac{2^{1}}{17} \rfloor$, $\lfloor \frac{2^{2}}{17} \rfloor$, $\lfloor \frac{2^{3}}{17} \rfloor$, $\dots$ contains infinitely many odd numbers.

1999 Putnam, 3
Tags: limit , algebra , polynomial , modular arithmetic
Let $A=\{(x,y): 0\le x,y < 1\}.$ For $(x,y)\in A,$ let \[S(x,y)=\sum_{\frac12\le\frac mn\le2}x^my^n,\] where the sum ranges over all pairs $(m,n)$ of positive integers satisfying the indicated inequalities. Evaluate \[\lim_{(x,y)\to(1,1),(x,y)\in A}(1-xy^2)(1-x^2y)S(x,y).\]

1984 IMO Longlists, 24
Tags: modular arithmetic , combinatorics , chessboard
(a) Decide whether the fields of the $8 \times 8$ chessboard can be numbered by the numbers $1, 2, \dots , 64$ in such a way that the sum of the four numbers in each of its parts of one of the forms [list][img]http://www.artofproblemsolving.com/Forum/download/file.php?id=28446[/img][/list] is divisible by four. (b) Solve the analogous problem for [list][img]http://www.artofproblemsolving.com/Forum/download/file.php?id=28447[/img][/list]

2006 Estonia National Olympiad, 3
Tags: modular arithmetic , number theory
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.

2009 USA Team Selection Test, 8
Tags: modular arithmetic , algebra , polynomial , calculus , number theory
Fix a prime number $ p > 5$. Let $ a,b,c$ be integers no two of which have their difference divisible by $ p$. Let $ i,j,k$ be nonnegative integers such that $ i \plus{} j \plus{} k$ is divisible by $ p \minus{} 1$. Suppose that for all integers $ x$, the quantity \[ (x \minus{} a)(x \minus{} b)(x \minus{} c)[(x \minus{} a)^i(x \minus{} b)^j(x \minus{} c)^k \minus{} 1]\] is divisible by $ p$. Prove that each of $ i,j,k$ must be divisible by $ p \minus{} 1$. [i]Kiran Kedlaya and Peter Shor.[/i]

2008 IMO Shortlist, 5
Tags: function , number theory , modular arithmetic , divisor , functional equation
For every $ n\in\mathbb{N}$ let $ d(n)$ denote the number of (positive) divisors of $ n$. Find all functions $ f: \mathbb{N}\to\mathbb{N}$ with the following properties: [list][*] $ d\left(f(x)\right) \equal{} x$ for all $ x\in\mathbb{N}$. [*] $ f(xy)$ divides $ (x \minus{} 1)y^{xy \minus{} 1}f(x)$ for all $ x$, $ y\in\mathbb{N}$.[/list] [i]Proposed by Bruno Le Floch, France[/i]

2006 India IMO Training Camp, 1
Tags: greatest common divisor , modular arithmetic , symmetry , number theory
Find all triples $(a,b,c)$ such that $a,b,c$ are integers in the set $\{2000,2001,\ldots,3000\}$ satisfying $a^2+b^2=c^2$ and $\text{gcd}(a,b,c)=1$.

1996 Romania Team Selection Test, 12
Tags: function , modular arithmetic , algebra , domain , combinatorics
Let $ n\geq 3 $ be an integer and let $ p\geq 2n-3 $ be a prime number. For a set $ M $ of $ n $ points in the plane, no 3 collinear, let $ f: M\to \{0,1,\ldots, p-1\} $ be a function such that (i) exactly one point of $ M $ maps to 0, (ii) if a circle $ \mathcal{C} $ passes through 3 distinct points of $ A,B,C\in M $ then $ \sum_{P\in M\cap \mathcal{C}} f(P) \equiv 0 \pmod p $. Prove that all the points in $ M $ lie on a circle.

2014 Indonesia MO Shortlist, N6
Tags: modular arithmetic , number theory
A positive integer is called [i]beautiful[/i] if it can be represented in the form $\dfrac{x^2+y^2}{x+y}$ for two distinct positive integers $x,y$. A positive integer that is not beautiful is [i]ugly[/i]. a) Prove that $2014$ is a product of a beautiful number and an ugly number. b) Prove that the product of two ugly numbers is also ugly.

2006 China Team Selection Test, 2
Tags: modular arithmetic , number theory
Prove that for any given positive integer $m$ and $n$, there is always a positive integer $k$ so that $2^k-m$ has at least $n$ different prime divisors.

2010 Baltic Way, 18
Tags: modular arithmetic , number theory
Let $p$ be a prime number. For each $k$, $1\le k\le p-1$, there exists a unique integer denoted by $k^{-1}$ such that $1\le k^{-1}\le p-1$ and $k^{-1}\cdot k=1\pmod{p}$. Prove that the sequence \[1^{-1},\quad 1^{-1}+2^{-1},\quad 1^{-1}+2^{-1}+3^{-1},\quad \ldots ,\quad 1^{-1}+2^{-1}+\ldots +(p-1)^{-1} \] (addition modulo $p$) contains at most $\frac{p+1}{2}$ distinct elements.

1977 IMO Longlists, 12
Tags: modular arithmetic , relatively prime , number theory
Let $z$ be an integer $> 1$ and let $M$ be the set of all numbers of the form $z_k = 1+z + \cdots+ z^k, \ k = 0, 1,\ldots$. Determine the set $T$ of divisors of at least one of the numbers $z_k$ from $M.$

2001 CentroAmerican, 3
Tags: modular arithmetic
In a circumference of a circle, $ 10000$ points are marked, and they are numbered from $ 1$ to $ 10000$ in a clockwise manner. $ 5000$ segments are drawn in such a way so that the following conditions are met: 1. Each segment joins two marked points. 2. Each marked point belongs to one and only one segment. 3. Each segment intersects exactly one of the remaining segments. 4. A number is assigned to each segment that is the product of the number assigned to each end point of the segment. Let $ S$ be the sum of the products assigned to all the segments. Show that $ S$ is a multiple of $ 4$.

2002 Flanders Junior Olympiad, 2
Tags: modular arithmetic
Prove that there are no perfect squares in the array below: \[\begin{array}{cccc}11&111&1111&...\\22&222&2222&...\\33&333&3333&...\\44&444&4444&...\\55&555&5555&... \\66&666&6666&...\\77&777&7777&...\\88&888&8888&...\\99&999&9999&...\end{array}\]

2007 Korea - Final Round, 4
Tags: modular arithmetic , number theory
Find all pairs $ (p, q)$ of primes such that $ {p}^{p}\plus{}{q}^{q}\plus{}1$ is divisible by $ pq$.

2014 Junior Balkan MO, 1
Tags: diophantine equation , modular arithmetic
Find all triples of primes $(p,q,r)$ satisfying $3p^{4}-5q^{4}-4r^{2}=26$.

2021 Bolivia Ibero TST, 3
Tags: number theory , modular arithmetic , 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$

2011 AIME Problems, 7
Tags: modular arithmetic , algebra , polynomial , function , number theory
Find the number of positive integers $m$ for which there exist nonnegative integers $x_0,x_1,\ldots,x_{2011}$ such that \[ m^{x_0}=\sum_{k=1}^{2011}m^{x_k}. \]

2001 USAMO, 5
Tags: modular arithmetic , number theory
Let $S$ be a set of integers (not necessarily positive) such that (a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$; (b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$. Prove that $S$ is the set of all integers.

1983 IMO Longlists, 13
Tags: modular arithmetic , number theory
Let $p$ be a prime number and $a_1, a_2, \ldots, a_{(p+1)/2}$ different natural numbers less than or equal to $p.$ Prove that for each natural number $r$ less than or equal to $p$, there exist two numbers (perhaps equal) $a_i$ and $a_j$ such that \[p \equiv a_i a_j \pmod r.\]

2002 China Western Mathematical Olympiad, 2
Tags: modular arithmetic , inequalities , number theory
Given a positive integer $ n$, find all integers $ (a_{1},a_{2},\cdots,a_{n})$ satisfying the following conditions: $ (1): a_{1}\plus{}a_{2}\plus{}\cdots\plus{}a_{n}\ge n^2;$ $ (2): a_{1}^2\plus{}a_{2}^2\plus{}\cdots\plus{}a_{n}^2\le n^3\plus{}1.$

1999 Harvard-MIT Mathematics Tournament, 2
Tags: modular arithmetic
For what single digit $n$ does $91$ divide the $9$-digit number $12345n789$?

2010 Romania Team Selection Test, 1
Tags: calculus , integration , algebra , polynomial , modular arithmetic , induction , arithmetic sequence
A nonconstant polynomial $f$ with integral coefficients has the property that, for each prime $p$, there exist a prime $q$ and a positive integer $m$ such that $f(p) = q^m$. Prove that $f = X^n$ for some positive integer $n$. [i]AMM Magazine[/i]