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.

Let $m,n$ be natural numbers and let $d = gcd(m,n)$. Let $x = 2^{m} -1$ and $y= 2^n +1$ (a) If $\frac{m}{d}$ is odd, prove that $gcd(x,y) = 1$ (b) If $\frac{m}{d}$ is even, Find $gcd(x,y)$

[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?

Let $G$ be a hyper elementary abelian $p-$group and let $f : G \rightarrow G$ be a homomorphism. Then prove that $\ker f$ is isomorphic to $\mathrm{coker} f$.

Given $T_1 =2, T_{n+1}= T_{n}^{2} -T_n +1$ for $n>0.$ Prove: (i) If $m \ne n,$ $T_m$ and $T_n$ have no common factor greater than $1.$ (ii) $\sum_{i=1}^{\infty} \frac{1}{T_i }=1.$

Let $p$ be a prime number. Let $\mathbb F_p$ denote the integers modulo $p$, and let $\mathbb F_p[x]$ be the set of polynomials with coefficients in $\mathbb F_p$. Define $\Psi : \mathbb F_p[x] \to \mathbb F_p[x]$ by \[ \Psi\left( \sum_{i=0}^n a_i x^i \right) = \sum_{i=0}^n a_i x^{p^i}. \] Prove that for nonzero polynomials $F,G \in \mathbb F_p[x]$, \[ \Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G)). \] Here, a polynomial $Q$ divides $P$ if there exists $R \in \mathbb F_p[x]$ such that $P(x) - Q(x) R(x)$ is the polynomial with all coefficients $0$ (with all addition and multiplication in the coefficients taken modulo $p$), and the gcd of two polynomials is the highest degree polynomial with leading coefficient $1$ which divides both of them. A non-zero polynomial is a polynomial with not all coefficients $0$. As an example of multiplication, $(x+1)(x+2)(x+3) = x^3+x^2+x+1$ in $\mathbb F_5[x]$. [i]Proposed by Mark Sellke[/i]

Let $S$ be the set of integers which are both a multiple of $70$ and a factor of $630{,}000$. A random element $c$ of $S$ is selected. If the probability that there exists an integer $d$ with $\gcd (c,d) = 70$ and $\operatorname{lcm} (c,d) = 630{,}000$ is $\frac mn$ for some relatively prime integers $m$ and $n$, compute $100m+n$. [i]Proposed by Eugene Chen[/i]

$ f(x)$ and $ g(x)$ are two polynomials with nonzero degrees and integer coefficients, such that $ g(x)$ is a divisor of $ f(x)$ and the polynomial $ f(x)\plus{}2009$ has $ 50$ integer roots. Prove that the degree of $ g(x)$ is at least $ 5$.

All the species of plants existing in Russia are catalogued (numbered by integers from $2$ to $2000$ ; one after another, without omissions or repetitions). For any pair of species the gcd of their catalogue numbers was calculated and recorded but the catalogue numbers themselves were lost. Is it possible to restore the catalogue numbers from the data in hand?

A natural number is written on the blackboard. Whenever number $ x$ is written, one can write any of the numbers $ 2x \plus{} 1$ and $ \frac {x}{x \plus{} 2}$. At some moment the number $ 2008$ appears on the blackboard. Show that it was there from the very beginning.

Let $c$ be the least common multiple of positive integers $a$ and $b$, and $d$ be the greatest common divisor of $a$ and $b$. How many pairs of positive integers $(a,b)$ are there such that \[ \dfrac {1}{a} + \dfrac {1}{b} + \dfrac {1}{c} + \dfrac {1}{d} = 1? \] $ \textbf{(A)}\ 6 \qquad\textbf{(B)}\ 5 \qquad\textbf{(C)}\ 4 \qquad\textbf{(D)}\ 3 \qquad\textbf{(E)}\ 2 $

There are 2010 boxes labeled $B_1,B_2,\dots,B_{2010},$ and $2010n$ balls have been distributed among them, for some positive integer $n.$ You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving [i]exactly[/i] $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?

A rectangle can be divided by parallel lines to its sides into 200 congruent squares, and also in 288 congruent squares. Prove that the rectangle can also be divided into 392 congruent squares.

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

For $m$ and $n$ positive integers that are prime to each other, determine the possible values ​​of $$\gcd (5^m + 7^m, 5^n + 7^n)$$

Suppose that $a_0, a_1, \cdots $ and $b_0, b_1, \cdots$ are two sequences of positive integers such that $a_0, b_0 \ge 2$ and \[ a_{n+1} = \gcd{(a_n, b_n)} + 1, \qquad b_{n+1} = \operatorname{lcm}{(a_n, b_n)} - 1. \] Show that the sequence $a_n$ is eventually periodic; in other words, there exist integers $N \ge 0$ and $t > 0$ such that $a_{n+t} = a_n$ for all $n \ge N$.

Let $n$ be an arbitrary positive integer. (a) For every positive integers $a$ and $b$, show that $gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1$. (b) Show that there exist infinitely many composite pairs ($a, b)$, such that each of them is not a multiply of the other number and equality holds in (a).

Let $\text{lcm} (a,b)$ denote the least common multiple of $a$ and $b$. Find the sum of all positive integers $x$ such that $x\le 100$ and $\text{lcm}(16,x) = 16x$. [i]Ray Li.[/i]

Prove that the equation $3y^2 = x^4 + x$ has no positive integer solutions.

Let $f_n$ be the Fibonacci numbers, defined by $f_0 = 1$, $f_1 = 1$, and $f_n = f_{n-1}+f_{n-2}$. For each $i$, $1 \le i \le 200$, we calculate the greatest common divisor $g_i$ of $f_i$ and $f_{2007}$. What is the sum of the distinct values of $g_i$?

Given an integer $ n > 3.$ Prove that there exists a set $ S$ consisting of $ n$ pairwisely distinct positive integers such that for any two different non-empty subset of $ S$:$ A,B, \frac {\sum_{x\in A}x}{|A|}$ and $ \frac {\sum_{x\in B}x}{|B|}$ are two composites which share no common divisors.

Of the vertices of a cube, $7$ of them have assigned the value $0$, and the eighth the value $1$. A [i]move[/i] is selecting an edge and increasing the numbers at its ends by an integer value $k > 0$. Prove that after any finite number of [i]moves[/i], the g.c.d. of the $8$ numbers at vertices is equal to $1$. Russian M.O.

Two farmers agree that pigs are worth $ \$300$ and that goats are worth $ \$210$. When one farmer owes the other money, he pays the debt in pigs or goats, with ``change'' received in the form of goats or pigs as necessary. (For example, a $ \$390$ debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way? $ \textbf{(A) } \$5\qquad \textbf{(B) } \$10\qquad \textbf{(C) } \$30\qquad \textbf{(D) } \$90\qquad \textbf{(E) } \$210$

For positive integers $a$ and $b$, $gcd (a, b)$ denote their greatest common divisor and $lcm (a, b)$ their least common multiple. Determine the number of ordered pairs (a,b) of positive integers satisfying the equation $ab + 63 = 20\, lcm (a, b) + 12\, gcd (a,b)$

For any integer $n$ we define the numbers $a = n^5 + 6n^3 + 8n$ ¸ $b = n^4 + 4n^2 + 3$. Prove that the numbers $a$ and $b$ are relatively prime or have the greatest common factor of $3$.