Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1. [b]Note: Graph-Definition[/b]. A [b]graph[/b] consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x \equal{} v_{0},v_{1},v_{2},\cdots ,v_{m} \equal{} y\,$ such that each pair $ \,v_{i},v_{i \plus{} 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.

Let $f(n)$ be the number of ordered pairs $(k, \ell)$ of positive integers such that $n = (2\ell-1)\cdot 2^k - k$, and let $g(n)$ be the number of ordered pairs $(k, \ell)$ of positive integers such that $n = \ell \cdot 2^{k+1}-k$. Compute $\sum_{i=1}^{\infty}\frac{f(i) - g(i)}{2^i}$. .

Let $p$ be an odd prime number. Let $S$ be the sum of all primitive roots modulo $p$. Show that if $p-1$ isn't squarefree (i. e., if there exist integers $k$ and $m$ with $k>1$ and $p-1=k^2m$), then $S \equiv 0 \mod p$. If not, then what is $S$ congruent to $\mod p$ ?

Let $c$ be a positive real and $a_1, a_2, \dots$ be a sequence of nonnegative integers satisfying the following conditions for every positive integer $n$: [b](i)[/b]$\frac{2^{a_1}+2^{a_2}+\cdots+2^{a_n}}{n}$ is an integer; [b](ii)[/b]$\textbullet 2^{a_n}\leq cn$. Prove that the sequence $a_1, a_2, \dots$ is eventually constant.

Find all pairs $(p,q)$ of prime numbers, such that $2p-1$, $2q-1$, $2pq-1$ are perfect square. F. Petrov, A. Smirnov

Find all positive integers $n, n>1$ for wich holds : If $a_1, a_2 ,\dots ,a_k$ are all numbers less than $n$ and relatively prime to $n$ , and holds $a_1<a_2<\dots <a_k $, then none of sums $a_i+a_{i+1}$ for $i=1,2,3,\dots k-1 $ are divisible by $3$.

Two different $3$ digit numbers are picked and then for every of them is calculated sum of all $5$ numbers which are getting when digits of picked number change place (etc. if one of the number is $707$, the sum is $2401=770+77+77+770+707$). Do the given results must be different?

For any positive integer $n$, consider its binary representation. Denote by $f(n)$ the number we get after removing all the $0$'s in its binary representation, and $g(n)$ the number of $1$'s in the binary representation. For example, $f(19) = 7$ and $g(19) = 3.$ Find all positive integers $n$ that satisfy $$n = f(n)^{g(n)}.$$ [i] Proposed by usjl[/i]

Let $n$ be a given positive integer. (a) Do there exist $2n+1$ consecutive positive integers $a_0,a_1,\ldots,a_{2n}$ in the ascending order such that $a_0+a_1+\ldots+a_n=a_{n+1}+\ldots+a_{2n}$? (b) Do there exist consecutive positive integers $a_0,a+1,\ldots,a_{2n}$ in ascending order such that $a_0^2+a_1^2+\ldots+a_n^2=a_{n+1}^2+\ldots+a_{2n}^2$? (c) Do there exist consecutive positive integers $a_0,a_1,\ldots,a_{2n}$ in ascending order such that $a_0^3+a_1^3+\ldots+a_n^3=a_{n+1}^3+\ldots+a_{2n}^3$? [hide=Official Hint]You may study the function $f(x)=(x-n)^3+\ldots+x^3-(x+1)^3-\ldots-(x+n)^3$ and prove that the equation $f(x)=0$ has a unique solution $x_n$ with $3n(n+1)<x_n<3n(n+1)+1$. You may use the identity $1^3+2^3+\ldots+n^3=\frac{n^2(n+1)^2}2$.[/hide]

Find all numbers $n$ that can be expressed in the form $n=k+2\lfloor\sqrt{k}\rfloor+2$ for some nonnegative integer $k$.

Consider the sequence in which $a_1 = 1$ and $a_n$ is obtained by juxtaposing the decimal representation of $n$ at the end of the decimal representation of $a_{n-1}$. That is, $a_1 = 1$, $a_2 = 12$, $a_3 = 123$, $\dots$ , $a_9 = 123456789$, $a_{10} = 12345678910$ and so on. Prove that infinitely many numbers of this sequence are multiples of $7$.

In a deck of cards, there are $kn$ cards numbered from $1$ to $n$ and there are $k$ cards of each number. Now, divide this deck into $k$ sub-decks with equal sizes. Prove that if $\gcd(k,n)=1$, then one could always pick $n$ cards, one from each sub-deck, such that the sum of those cards is divisible by $n$.

The number $60$ is written on a blackboard. In every move, Andris wipes the numbers on the board one by one, and writes all its divisors in its place (including itself). After $10$ such moves, how many times will $1$ appear on the board?

Let $p_1$, $p_2$ be two odd prime numbers and $\alpha $, $n$ be positive integers with $\alpha >1$, $n>1$. Prove that if the equation $\left (\frac{p_2 -1}{2} \right )^{p_1} + \left (\frac{p_2 +1}{2} \right )^{p_1} = \alpha^n$ does not have integer solutions for both $p_1 =p_2$ and $p_1 \neq p_2$.

Find all the natural numbers $m,n$ such that $1+5 \cdot 2^m=n^2$.

[b]p1.[/b] Twenty five horses participate in a competition. The competition consists of seven runs, five horse compete in each run. Each horse shows the same result in any run it takes part. No two horses will give the same result. After each run you can decide what horses participate in the next run. Could you determine the three fastest horses? (You don’t have stopwatch. You can only remember the order of the horses.) [b]p2.[/b] Prove that the equation $x^6-143x^5-917x^4+51x^3+77x^2+291x+1575=0$ does not have solutions in integer numbers. [b]p3.[/b] Show how we can cut the figure shown in the picture into two parts for us to be able to assemble a square out of these two parts. Show how we can assemble a square. [img]https://cdn.artofproblemsolving.com/attachments/7/b/b0b1bb2a5a99195688638425cf10fe4f7b065b.png[/img] [b]p4.[/b] The city of Vyatka in Russia produces local drink, called “Vyatka Cola”. «Vyatka Cola» is sold in $1$, $3/4$, and $1/2$-gallon bottles. Ivan and John bought $4$ gallons of “Vyatka Cola”. Can we say for sure, that they can split the Cola evenly between them without opening the bottles? [b]p5.[/b] Positive numbers a, b and c satisfy the condition $a + bc = (a + b)(a + c)$. Prove that $b + ac = (b + a)(b + c)$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A subset $S$ of the natural numbers is called [i]dense [/i] for every $7$ consecutive natural numbers, at least $5$ of them are in $S$. Show that there exists a dense subset for which the equation $a^2+b^2=c^2$ has no solution for $a,b,c \in S$.

Let $n$ be an integer, $n \ge 2$. Find the remainder of the division of the number $n(n + 1)(n + 2)$ by $n - 1$.

Show that there are infinitely many positive integers n such that $2\underbrace{555...55}_{n}3$ is divisible by $2553$.

Let $a > b > c > d$ be positive integers and suppose that \[ ac + bd = (b+d+a-c)(b+d-a+c). \] Prove that $ab + cd$ is not prime.

Solve the equation \[(a^{2},b^{2})+(a,bc)+(b,ac)+(c,ab)=199.\] in positive integers. (Here $(x,y)$ denotes the greatest common divisor of $x$ and $y$.) [i]Proposed by S. Berlov[/i]

It is desired to choose $n$ integers from the collection of $2n$ integers, namely, $0,0,1,1,2,2,\ldots,n-1,n-1$ such that the average of these $n$ chosen integers is itself an integer and as minimum as possible. Show that this can be done for each positive integer $n$ and find this minimum value for each $n$.

Find all integers $k{}$ for which there are infinitely many triples of integers $(a,b,c)$ such that \[(a^2-k)(b^2-k)=c^2-k.\]

Find n such that $36^n-6$ is the product of three consecutive natural numbers

Among the $2n$ numbers $1, 2, 3, . . . , 2n$ are chosen in any way $n + 1$ different numbers. Prove that among the chosen numbers there are at least two, such that one divides the other.