Search

Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

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.

[A graph 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 = v_0, v_1, v_2, \ldots, v_m = y$ such that each pair $v_i, v_{i+1}$ ($0 \leq i < m$) is joined by an edge of $G$.]

Let $n \geq 3$ be an integer, and consider a circle with $n + 1$ equally spaced points marked on it. Consider all labellings of these points with the numbers $0, 1, \ldots, n$ such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels $a < b < c < d$ with $a + d = b + c$, the chord joining the points labelled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.

Let $M$ be the number of beautiful labellings, and let $N$ be the number of ordered pairs $(x,y)$ of positive integers such that $x + y \leq n$ and $\gcd(x,y) = 1$. Prove that

$$M = N + 1.$$

An ordered pair $(x, y)$ of integers is a primitive point if the greatest common divisor of $x$ and $y$ is 1. Given a finite set $S$ of primitive points, prove that there exist a positive integer $n$ and integers $a_0, a_1, \ldots, a_n$ such that, for each $(x, y)$ in $S$, we have:

$$a_0 x^n + a_1 x^{n-1} y + a_2 x^{n-2} y^2 + \cdots + a_{n-1} x y^{n-1} + a_n y^n = 1.$$

Determine all pairs $(a, b)$ of positive integers for which there exist positive integers $g$ and $N$ such that $$\gcd(a^n + b, b^n + a) = g$$ holds for all integers $n \geq N$. (Note that $\gcd(x, y)$ denotes the greatest common divisor of integers $x$ and $y$.)

We call a positive integer $n$ amazing if there exist positive integers $a,b,c$ such that the equality $$n=(b,c)(a,bc)+(c,a)(b,ca)+(a,b)(c,ab)$$ holds. Prove that there exist $2011$ consecutive positive integers which are amazing.

(By $(m,n)$ we denote the greatest common divisor of positive integers $m$ and $n$.)

Initially, two positive integers $a$ and $b$ with $a \neq b$ are written on a blackboard. At each step, Andrea picks two numbers $x$ and $y$ on the blackboard with $x \neq y$ and writes the number

$$\gcd(x, y) + \operatorname{lcm}(x, y)$$

on the blackboard as well. Let $n$ be a positive integer. Prove that, regardless of the values of $a$ and $b$, Andrea can perform a finite number of steps such that a multiple of $n$ appears on the blackboard.

Remark. If $x$ and $y$ are two positive integers, then $\gcd(x, y)$ denotes their greatest common divisor and $\operatorname{lcm}(x, y)$ their least common multiple.

Let $A$ and $B$ be positive integers. Consider a sequence of positive integers $(x_{n})_{n\geq 1}$ such that

$$x_{n+1} = A \cdot \gcd(x_{n}, x_{n-1}) + B \quad \text{for every } n \geq 2.$$

Prove that the sequence attains only finitely many different values.

Remark. We denote by $\gcd(a, b)$ the greatest common divisor of positive integers $a$ and $b$.

Nadite sve prirodne brojeve koji su najveća zajednička mjera brojeva oblika $5n + 6$ i $8n + 7$ za neko $n \in \mathbf{N}$.

Odredi sve uređene parove $(a,b)$ prirodnih brojeva takve da je $V(a,b) - D(a,b) = \dfrac{ab}{5}$.

Žaba Žana nalazi se ishodištu brojevnog pravca, te u svakom koraku skače za jedan ulijevo, za jedan udesno ili ostaje na mjestu. Lina i Dina izabrale su relativno proste brojeve $m$ i $n$, gdje je $m > n$. Nakon svakih $n$ koraka Lina zapovijeda: „Lijevo!", a nakon svakih $m$ koraka Dina zapovijeda: „Desno!" Žana miruje dok ne čuje prvu zapovijed, a nakon toga počinje (ili nastavlja) skakati u smjeru prema zapovijedi. Zaustavlja se u prvom koraku u kojem čuje obje zapovijedi. U ovisnosti o brojevima $m$ i $n$ odredi na kojoj se udaljenosti od ishodišta Žana zaustavila.

Neka je $f(x) = x^{2002} - x^{2001} + 1$. Dokazati da su za svaki prirodan broj $m$ brojevi $m$, $f(m)$, $f(f(m))$, $f(f(f(m)))$, ..., u parovima relativno prosti, tj. da nikoja dva među njima nemaju zajednički djelitelj veći od $1$.

Za uređenu trojku prirodnih brojeva $(a, b, c)$ kažemo da je morska ako su $a$, $b$ i $c$ međusobno različiti, te je broj $ac$ djeljiv brojevima $a + b$ i $b + c$. Dokaži da

a) za svaki prirodni broj $d > 1$ postoji morska trojka $(a, b, c)$ za koju je $M(a, b, c) = d$.

b) ne postoji morska trojka $(a, b, c)$ za koju je $M(a, b, c) = 1$.

Napomena. $M(a, b, c)$ označava najveći zajednički djelitelj brojeva $a$, $b$ i $c$.

Odredi sve trojke prirodnih brojeva $(m, n, k)$ za koje vrijedi $$D(m, 20) = n, \quad D(n, 15) = k \quad \text{i} \quad D(m, k) = 5,$$ gdje je $D(a, b)$ najveći zajednički djelitelj brojeva $a$ i $b$.